백준 2981번: 검문

문제 링크 : https://www.acmicpc.net/problem/2981

참고한 블로그 : https://kyunstudio.tistory.com/88

문제풀이를 하도 안했더니 머리가 굳긴 했나보다. 이제는 검색해보지 않으면 문제를 풀 수 없어..
주어진 N개의 수를 임의의 수 M으로 나누었을 때 나머지가 모두 같도록 하는 모든 M을 구하는 문제이다. 아무리 생각을 해봐도 풀 방법이 생각이 나지 않았다. 모든 수를 다 비교해보기에는 당연히 시간 초과가 뜰 것이고..
검색해본 블로그에서는 수학적 점화식으로 문제를 풀었다. 어떻게 저렇게 생각할 수 있지.. 대단하다.

모든 나머지가 같으므로 R이라고 둔다.
a[0] % M = R
a[1] % M = R ... 일 것이고, 나머지를 다른 식으로 표현하면

R = a[0] - (a[0] / M) x M
R = a[1] - (a[1] / M) x M 이기 때문에,

a[0] - (a[0] / M) x M = a[1] - (a[1] / M) x M,
a[1] - a[0] = (a[1] / M) x M - (a[0] / M) x M,
a[k] - a[k - 1] = (a[k] / M - a[k - 1] / M) x M 이 된다.
(a[k] / M - a[k - 1] / M)는 계산하면 어떤 수, 즉 상수이므로 M x C가 되고, 이 말은 M의 배수들이란 것을 알 수 있다.
따라서 이 a[k] - a[k - 1]들의 최대공약수를 구하고, 그 최대공약수의 약수들이 정답이 된다고 한다.

이해한 대로 적어보긴 했는데, 맞게 적었나도 모르겠다. 아무튼 위 식대로 코드를 작성하면 정답을 맞출 수 있다.
<작성한 코드>

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int arr[500];
vector<int> exist;

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

int main()
{
    int n, m;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    sort(arr, arr + n);
    
    int num = arr[1] - arr[0];
    for(int i = 2; i < n; i++){
        num = gcd(arr[i] - arr[i - 1], num);
    }
    // 최종으로 나온 num이 모든 arr[i] - arr[i - 1]들의 최대공약수
    
    exist.push_back(num);
    for(int i = 2; i * i <= num; i++){
        if(num % i == 0){
            exist.push_back(i);
            if(i * i != num)
                exist.push_back(num / i);
        }
    } // 최대공약수의 약수들 구하는 부분
    sort(exist.begin(), exist.end());
    for(int i = 0; i < exist.size(); i++)
        cout << exist[i] << " ";
}