yukicoder No.97 最大の値を求めるくえり

昨日のAtCoderのD問題の類題ということで解きました。

問題

No.97 最大の値を求めるくえり - yukicoder

解法

Nがそこそこ小さい時(3000未満)のときはそのまま計算しても間に合うので普通に計算する。

Nが大きい時を考える。100003は素数であることに注意すると(mod 100003は省略する),

と

は同値。

つまり,が配列Aに含まれていれば良いことになる。
Nが大きい時はmの値は100003に近くなることが予想されるのでmを大きい順に調べていけば計算量の期待値は少なそう。

unsigned xor128_x = 123456789, xor128_y = 362436069, xor128_z = 521288629, xor128_w = 88675123;
unsigned xor128() {
    unsigned t = xor128_x ^ (xor128_x << 11);
    xor128_x = xor128_y; xor128_y = xor128_z; xor128_z = xor128_w;
    return xor128_w = xor128_w ^ (xor128_w >> 19) ^ (t ^ (t >> 8));
}
void generateA(int N, int A[]) {
    for(int i = 0; i < N; ++ i)
        A[i] = xor128() % 100003;
}
int A[100007];
const ll MOD = 100003;

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    generateA(N, A);
    if (N < 3000) {
        while (Q--) {
            ll q;
            cin >> q;
            ll ans = 0;
            for (int i = 0; i < N; i++) {
                ans = max(ans, (q*A[i])%MOD);
            }
            cout << ans << endl;
        }
    } else {
        sort(A, A+N);
        while (Q--) {
            ll q;
            cin >> q;
            if (q == 0) {
                cout << 0 << endl;
                continue;
            }
            int ans = MOD-1;
            ll iq = mod_inverse(q);
            while (1) {
                ll p = (iq * ans) % MOD;
                if (binary_search(A, A+N, p)) {
                    cout << ans << endl;
                    break;
                }
                ans--;
            }
        }
    }
    return 0;
}