BAEKJOON 2981번: 검문

https://www.acmicpc.net/problem/2981

2981번: 검문

일단 간단하게 2 개의 수가 있을 때를 생각해보자.

Let. \(A,\;B \in \mathcal{N}\), \(A \equiv B \pmod{M} \)

\(A \, = A \, - \, \lfloor \frac{A}{M} \rfloor \times M \, + R\) 이므로 (단,  \(A  \mod \, M \, = \, R\))

\( A \, - \, \lfloor \frac{A}{M} \rfloor \times M \, = \, B \, - \, \lfloor \frac{B}{M} \rfloor \times M \)이다.

위 식을 정리하면, \( A-B\, = \, (\lfloor \frac{A}{M} \rfloor  - \lfloor \frac{B}{M} \rfloor ) \times M \)

위 식에서 알 수 있는 것은 \(A-B\)는 \(M\)의 배수라는 것이다. 즉, 주이지는 N 개의 수들을 인접한 수들의 gcd를 구하고 그 gcd의 약수들을 출력하면 AC를 받을 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll gcd(ll a,ll b){
    ll c=a%b;
    while(c){
        a=b;b=c;
        c=a%b;
    }
    return b;
}
ll A[103];
set<ll>ans;
int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int N;cin>>N;
    for(int i=1;i<=N;i++)cin>>A[i];
    ll GCD=abs(A[1]-A[2]);
    for(int i=3;i<=N;i++)GCD=gcd(GCD,abs(A[i]-A[i-1]));
    ans.insert(GCD);
    for(int i=2;i*i<=GCD;i++){
        if(GCD%i==0){
            ans.insert(i);
            ans.insert(GCD/i);
        }
    }
    for(auto it=ans.begin();it!=ans.end();it++)cout<<*it<<" ";
    return 0;
}