백준 2981번 검문 - C++ 풀이

---

 

1. 두 수 a, b를 M으로 나눈 나머지가 같다면 (a-b) % M = 0
2. 두 수 a, b를 M으로 나눈 나머지가 같다면 M의 약수로 나눈 나머지도 같다.
3. A[i+1] - A[i](0 ≤ i < N-1)의 최대 공약수의 약수들이 가능한 모든 M이 된다.

 

1. 두 수 a, b를 M으로 나눈 나머지가 같다면 (a-b) % M = 0

 두 수 a, b를 M으로 나눈 나머지가 r로 같다면, 두 수 a, b는 아래와 같이 나타낼 수 있다.

a = M*(a/M) + r
b = M*(b/M) + r

 위 식에서 아래를 빼면 a-b = M*(a/M-b/M)이므로 (a-b)는 M으로 나누어 떨어진다.

 

2. 두 수 a, b를 M으로 나눈 나머지가 같다면 M의 약수로 나눈 나머지도 같다.

 또한 두 수 a, b를 M으로 나눈 나머지가 같다면 M의 약수로 나눈 나머지도 같다.

 

3. A[i+1] - A[i](0 ≤ i < N-1)의 최대 공약수의 약수들이 가능한 모든 M이 된다.

 모든 수들을 M으로 나눈 나머지가 같아야 하므로 두 수의 차들, 즉 A[i+1]-A[i]들의 최대 공약수의 약수들이 가능한 모든 M이 된다.

반응형

---

#include <iostream>
#include <vector>
#include <set>

using namespace std;

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

set<int> findM(vector<int>& A) {
    int M;
    vector<int> gap;
    set<int>ret;
    
    // 두 수 a, b를 M으로 나눈 나머지가 같다면
    // a = M*(a/M) + r
    // b = M*(b/M) + r
    // a-b = M*(a/M-b/M), (a-b)%M = 0
    for (int i=0; i<A.size()-1; i++) {
        gap.push_back(abs(A[i]-A[i+1]));
    }
    
    M = gap[0];
    for (int i=1; i<gap.size(); i++) {
        M = gcd(max(M, gap[i]), min(M, gap[i]));
    }
    
    ret.insert(M);
    for (int i=2; i*i<=M; i++) {
        if (M % i == 0) {
            ret.insert(i);
            ret.insert(M/i);
        }
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int N;
    vector<int> A;
    set<int> ans;
    
    cin >> N;
    for (int i=0; i<N; i++) {
        int x; cin >> x;
        A.push_back(x);
    }
    
    ans = findM(A);
    for (auto x: ans) cout << x << "\n";

    return 0;
}