2981 검문

나머지가 같게 되는 M을 찾는 문제

 

느낌상 모두 M으로 나눠야 하니 M이 모든 수의 약수가 되어야 된다고 생각했는데 나머지가 있는 게 문제였다. 이전에 이런 숫자? 다루는 문제는 숫자끼리 빼야 한다는 걸 풀어봐서 뺐더니 나머지가 같다면 나머지가 없어진다는 것을 알 수 있었다. 

 

그래서 숫자를 뺀 후 그 수들의 최대공약수를 구하고 최대공약수의 약수를 출력하게 해서 풀 수 있었다. 

 

문제 풀면서 생각없이 인접한 수만 빼서 구했는데 사실 왜 전부를 빼서 구하지 않을까를 고민했어야 했다ㅋㅋ 

 

예를 들어 x2 - x1이 a 이고 x3 - x2가 b라면 a도 m의 배수이고 b도 m의 배수가 된다.

그럼 x3 - x1 = a + b가 돼서 이것 또한 m의 배수이다. 

 

그래서 m을 결정하는 최소 단위가 인전합 애들의 차라서 이것만 빼도 된다. 신기... 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int check[2005][2005];

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

int main() {
    int n;
    scanf("%d", &n);
    
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    sort(all(v));
    
    int g = v[1] - v[0];
    for (int i = 2; i < n; i++) {
        g = gcd(g, v[i] - v[i - 1]);
    }
    
    vector<int> ans;
    for (int i = 1; i*i <= g; i++)
    {
        if (g % i != 0)
            continue;
        if (i*i != g)
            ans.push_back(i);
        ans.push_back(g / i);
    }
    sort(all(ans));
    
    for (int i = 1; i < ans.size(); i++)
        printf("%d ", ans[i]);
    
    
    
    return 0;
}