2981번 검문

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

(v.at(i) - v.at(i - 1))와 (v.at(i + 2) - v.at(i + 1))... 의 최대공약수(Max)를 구하여,

Max의 약수를 구한다.(1은 제외)

38 ~ 44번 째 줄의 테크닉(특히, 43번 째 줄)을 기억해두자.

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
 
vector<int> v, r;
 
int gcd(int p, int q)
{
    if (q == 0) return p;
    else return gcd(q, p % q);
}
 
int main(void)
{
    int num, Max = -1;
 
    scanf("%d", &n);
    
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &num);
        v.push_back(num);
    }
 
    sort(v.begin(), v.end());
 
    Max = v.at(1) - v.at(0);
 
    for (int i = 2; i < v.size(); i++)
        Max = gcd(Max, v.at(i) - v.at(i - 1));
    
    /*for(int i=1; i <= sqrt(Max); i++)
        if (!(Max % i))
            r.push_back(i);*/
 
    for (int i = 1; i <= sqrt(Max); i++)
        if (!(Max % i))
        {
            r.push_back(i);
 
            if (Max / i != i) r.push_back(Max / i); // 이 부분은 생각 못 했다.
        }
 
    sort(r.begin(), r.end());
 
    for (auto i : r)
        if (i != 1)
            printf("%d ", i);
    printf("\n");
 
    return 0;
}