* 해결 방법

  사람들이 이 문제에서 챌린지/시스템 페일 을 많이 당한 이유는 크게 두 가지가 있습니다. 첫 번째 경우는 답에 0이 포함된 경우를 체크하지 않아서이고, 두 번째 경우는 계산 과정 도중 integer 범위를 넘어가버리는 경우입니다.

  제가 접근했던 방법은 "조립제법"을 거꾸로 계산해 나가는 방법을 사용하였습니다. (주어진 다항식) = (x + v) * (.... ) 꼴이라고 가정했을 때, (....) 에서의 상수항은 바로 계산할 수 있습니다. 주어진 다항식의 상수항에서 v로 나눈 값일 테니까요. 그러면 이제 (....)의 x의 계수를 구할 차례인데요, (주어진 다항식)의 x 계수를 A, (....)의 x의 계수를 B, (....)의 상수항을 C라고 할 때, 아래의 조건을 만족시켜야 합니다.

  좌변의 x의 계수는 A가 되고, 우변의 x의 계수는 Bv + C가 되기 때문인데요. 그러면 우리는 A와 C를 알기 때문에 B를 거꾸로 계산할 수가 있게 됩니다. 이 문제에서의 다항식은 모두 "정수 다항식"이기 때문에, B 역시 정수가 되어야 합니다. 이제 이러한 계산을 반복해서 v가 해가 되는지 되지 않는지를 검사하면 됩니다. 아래의 소스코드에서 check() 함수가 조립제법을 사용한 부분입니다. :-)

  그리고 위의 식을 잘 살펴보면, 정수해는 항상 a[i] (i는 a[i] != 0을 만족하는 제일 작은 수) 의 약수여야 한다는 사실을 알 수 있습니다. (두 상수항의 곱이 a[i]를 만족시켜야 하기 때문이지요.) 약수의 개수는 그다지 많지 않기 때문에, 충분히 시간안에 계산할 수 있습니다.

vector <int> getA(vector <int> X, vector <int> Y, int n) {     int lX = sz(X), lY = sz(Y);     vector <int> a;     for (int i = 0; i <= n; i++) {         int p = i % lX;         int q = (i + Y[i % lY]) % lX;         a.pb(X[p]);         X[p] = X[q];         X[q] = a[i];     }     return a; } vector <int> a, ret; void check(int v) {     long long last = a[0], l2;     for (int i = 1; i < sz(a); i++) {         if (abs(last) % abs(v) != 0) return;         l2 = last / v;         last = a[i] - l2;     }     if (last == 0) ret.pb(-v); } struct SolvePolynomial {     vector <int> integerRoots(vector <int> X, vector <int> Y, int n) {         a = getA(X, Y, n);         while (a.back() == 0) a.pop_back();                 int g = a[0];         FOR(i, 1, sz(a)) {             if (a[i] == 0 || g == 0) { g = 0; break; }             g = __gcd(g, a[i]);         }         if (g > 1) REP(i, sz(a)) a[i] /= g;         if (a.back() < 0) REP(i, sz(a)) a[i] *= -1;         if (a[0] == 0) {             ret.pb(0);             while (a[0] == 0) {                 FOR(i, 1, sz(a))                     a[i - 1] = a[i];                 a.pop_back();             }         }         int G = abs(a[0]);         for (int i = 1; i * i <= G; i++) {             if (G % i != 0) continue;             check(i);             check(-i);             if (i * i == G) break;             check(G / i);             check(-G / i);         }         sort(all(ret));         return ret;     } };