[BOJ] 2981: 검문

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

2981번: 검문

---

접근 방법

어떻게 주어진 모든 수를 m으로 나눴을 때, 나머지가 같을 지 생각하다가, 떠오르는 것이 없어서, 알고리즘 분류를 보고 풀었다.

유클리드 호제법 을 보고 아 무언가의 최대공약수와 관련되어 있구나라는 생각을 하여 풀이했다.

---

풀이

어떤 수 \( x, y (x<y) \) 를 \( m \)으로 나눈 나머지가 같으려면, \( (y-x)\%m==0 \) 이어야 한다.

즉, \( x \)에서 \( y-x \)만큼 더해서 \( y \)를 만든다고 생각할 때, 더하는 수 \( y-x \) 를 \( m \)으로 나눈 나머지가 0이어야 한다는 뜻이다.

---

시간 복잡도

처음엔 모든 \( a[i]-a[i-1] (1 \leq i < n) \) 의 최대공약수의 1보다 큰 모든 약수를 구할 때에,

\( O(g) \) 로 구했었는데,  \( g \leq 10억 \) 이므로 TLE가 나온다.

따라서 for문을 \( \sqrt{g} \) 만큼만 돌면 \( O(\sqrt{g}) \) 로 시간 안에 해결할 수 있다.

---

코드

#include <bits/stdc++.h>
#define ll long long int
#define pll pair<ll, ll>
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
void solve()
{
    int n; cin>>n;
    ll a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    sort(a, a+n);
    ll g=a[1]-a[0];
    for(int i=2;i<n;i++) g=gcd(g, a[i]-a[i-1]);
    vector<int> ans;
    for(ll i=2;i*i<=g;i++) 
        if(g%i==0)
        {
            ans.push_back(i);
            if(i*i!=g) ans.push_back(g/i);
        }
    sort(ans.begin(), ans.end());
    ans.push_back(g);
    for(ll x:ans) cout<<x<<' ';
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int tc=1;
    while(tc--) solve();
    return 0;
}