N1 % M = k
N2 % M = k
N3 % M = k
N4 % M = k
...
N2 % M - N1 % M = 0
(N2 - N1) % M = 0
따라서 각 숫자의 차를 구하고, 그 차의 최대공약수를 구한 후, 구한 최대공약수의 약수를 전부 출력하면 된다!
또, gcd(a, b) = gcd(a+b, b) 이므로, 크기순으로 정렬한 후 인접 숫자간의 차이만 구해도 된다.
약수 구할 때 O(N)이 아니라 O(√N)으로 구해야함.
#include <bits/stdc++.h>
using namespace std;
int gcd (int a, int b) {
if (!b) return a;
return gcd(b, a%b);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> v(n), dif(n-1);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
sort(v.begin(), v.end());
for (int i = 0; i < n-1; i++) {
dif[i] = v[i+1] - v[i];
}
int g = dif[0];
for (int x : dif) {
g = gcd(g, x);
}
vector<int> div;
for (int i = 2; i*i <= g; i++) {
if (g%i == 0) {
div.push_back(i);
if (i*i != g) div.push_back(g/i);
}
}
sort(div.begin(), div.end());
for (int& x : div) cout << x << ' ';
cout << g;
return 0;
}
2년 전에 중도에서 열심히 풀다 포기한 문제.
아니 진짜 정수론 개어렵다. 공부 열심히 해야겠다.