SRM 657 Div2 1000 PolynomialRemainder

問題

a, b, cが与えられる。

a x^2 + b x + c = 0 (mod 1,000,000,000)

となるようなxを求めよ。

解法

10^9で割って0になるので、

2^9で割って0、5^9で割って0となるようなxを求めて、中国剰余定理をすればよい。

実装

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

long long extgcd(long long a, long long b, long long &x, long long &y) {
  long long d = a;
  if (b != 0) {
    d = extgcd(b, a%b, y, x);
    y -= a/b * x;
  } else {
    x = 1;
    y = 0;
  }
  return d;
}

pair<long long, long long> crm(long long a, long long n, long long b, long long m) {
  a %= n;
  b %= m;
  long long p, q;
  extgcd(n, m, p, q);
  long long mod = n * m;
  long long x = (a * q  * m) % mod + (b * p * n) % mod;
  x = (x % mod + mod) % mod;
  return make_pair(x, mod);
}

long long calc(long long a, long long b, long long c, long long x, long long mod) {
  long long ret = ((a % mod * x) % mod) * x % mod;
  ret = (ret + b * x) % mod;
  ret = (ret + c) % mod;
  return ret;
}

class PolynomialRemainder {
public:
  int findRoot(int a, int b, int c) {
    long long s, t;

    int n = 1;
    REP (i, 9) n *= 2;
    for (s = 0; s < n; s++) {
      if (calc(a,b,c,s,n) == 0)
        break;
    }
    if (s == n)
      return -1;

    int m = 1;
    REP (i, 9) m *= 5;
    for (t = 0; t < m; t++) {
      if (calc(a,b,c,t,m) == 0)
        break;
    }
    if (t == m)
      return -1;

    cout << s << " " << t << endl;
    auto ret = crm(s, n, t, m);
    return ret.first;
  }
};