結果

問題 No.2592 おでぶなおばけさん 2
コンテスト
ユーザー nu50218
提出日時 2023-12-05 16:55:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 504 ms / 2,500 ms
コード長 1,946 bytes
コンパイル時間 2,522 ms
コンパイル使用メモリ 197,024 KB
最終ジャッジ日時 2025-02-18 07:53:44
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 83
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

#include <atcoder/segtree.hpp>

using namespace std;
using ll = long long;

// [1e18, 5e18] からランダムな素数を取ってくる
// ミラーラビンとか使えば実行時にランダムに出来るのでハックありでも対応可能
// https://www.wolframalpha.com/input?i=RandomPrime%5B%7B10%5E18%2C+5*10%5E18%7D%5D
const ll MOD = 4554013204529924683;
static_assert(MOD < numeric_limits<ll>::max() / 2);

using S = ll;
S op(const S a, const S b) {
    return (a + b) % MOD;
}
S e() {
    return 0;
}
using segtree = atcoder::segtree<S, op, e>;

int main() {
    ll n, q, k;
    cin >> n >> q >> k;

    vector<ll> a(n);
    for (auto& x : a) {
        cin >> x;

        // 今後 % MOD の値しか使わないので、正の数にしておく
        x = (x + MOD) % MOD;
    }

    // b[i] := (a[i] * pow(k, i)) % MOD
    vector<ll> b(n);
    __uint128_t powk = 1;
    for (int i = 0; i < n; i++) {
        // a[i], powk ともに MOD < 2^63 以下なので、128ビットで十分
        b[i] = (a[i] * powk) % MOD;
        powk *= k;
        powk %= MOD;
    }

    segtree st(b);

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;

        // S = Σ_{i=l}^r (a_i k^{i-l}) として、
        // S = 0 かどうかを、S % MOD = 0 かどうかで判定する。
        // この方法で高い確率で正解できる。
        //
        // 判定が誤るのは S ≡ 0 かつ S > 0 のとき、すなわち S が MOD を素因数として含むとき。
        // しかしながら MOD として取りうる値は 10^16個ぐらいあり、
        // （ https://ja.wikipedia.org/wiki/素数定理 の π(10^18) あたりを参照）
        // S は高々 r-l <= 10^5 個程度しか 10^18 以上の素因数を含まないので、その確率は非常に低い。
        cout << (st.prod(l, r + 1) ? "Yes" : "No") << endl;
    }
}
0