SRM 657 div2 hard:PolynomialRemainder

いよいよ明日がCODE FESTIVAL2015予選A本番ですよ！むっちゃドキドキしてきた…。コンテスタントの皆さん、今日くらいは勉強は休んで明日に備えますよね？

あと 5 分です

問題

TopCoder Statistics - Problem Statement

解法

2^9 と 5^9 について余りが 0 になっていれば良いです。

そうなるように条件を揃えましょう。

int getRoot(int a, int b, int c, int mod) {
    for (ll x = 0; x < mod; x++) {
        ll p = (a*(x*x%mod)) % mod;
        ll q = (b*x)%mod;
        ll r = c;
        if ((p+q+r)%mod == 0) return (int)x;
    }
    return -1;
}

class PolynomialRemainder {
public:
    int findRoot(int a, int b, int c) {
        const int POW2 = 2*2*2 * 2*2*2 * 2*2*2;
        const int POW5 = 5*5*5 * 5*5*5 * 5*5*5;
        int x2 = getRoot(a, b, c, POW2);
        int x5 = getRoot(a, b, c, POW5);
        if (x2 == -1 || x5 == -1) return -1;
        int x = x5;
        while (x%POW2 != x2) {
            x += POW5;
        }
        return x;
    }
};