백준 2981번: 검문

Seungil Kim·2022년 2월 23일
0

PS

목록 보기
175/206

검문

백준 2981번: 검문

아이디어

N1 % M = k
N2 % M = k
N3 % M = k
N4 % M = k
...

N2 % M - N1 % M = 0
(N2 - N1) % M = 0

따라서 각 숫자의 차를 구하고, 그 차의 최대공약수를 구한 후, 구한 최대공약수의 약수를 전부 출력하면 된다!

또, gcd(a, b) = gcd(a+b, b) 이므로, 크기순으로 정렬한 후 인접 숫자간의 차이만 구해도 된다.

약수 구할 때 O(N)이 아니라 O(√N)으로 구해야함.

코드

#include <bits/stdc++.h>

using namespace std;

int gcd (int a, int b) {
    if (!b) return a;
    return gcd(b, a%b);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> v(n), dif(n-1);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < n-1; i++) {
        dif[i] = v[i+1] - v[i];
    }

    int g = dif[0];
    for (int x : dif) {
        g = gcd(g, x);
    }

    vector<int> div;
    for (int i = 2; i*i <= g; i++) {
        if (g%i == 0) {
            div.push_back(i);
            if (i*i != g) div.push_back(g/i);
        }
    }
    sort(div.begin(), div.end());
    for (int& x : div) cout << x << ' ';
    cout << g;

    return 0;
}

여담

2년 전에 중도에서 열심히 풀다 포기한 문제.
아니 진짜 정수론 개어렵다. 공부 열심히 해야겠다.

profile
블로그 옮겼어용 https://ks1ksi.io/

0개의 댓글