Codeforces Round #330 (Div. 1) D. REQ

問題

codeforces.com

解法

φ(n)=nΠ(p-1)/pなので、区間内にどんな素因数かがあるかが重要になる。Π(p-1)/pを取得するクエリを頑張って作ればいい。

クエリを右端でソートしておいて、適当なタイミングで計算する。素因数をとにかく右端に寄せていくとうまい感じになる。実際には素因数ではなく(p-1)/pをBITに入れておけばいい。

素因数はエラトステネスの篩でO(n loglog n)で調べておくと早いと思ってるけど、毎回O(√n)でも間に合うのかな？

サンプル1の場合はこんな感じにBITを更新していく。

ソースコード

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;

const ll mod = 1e9 + 7;

ll modpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) (res *= a) %= mod;
        (a *= a) %= mod;
        b /= 2;
    }
    return res;
}

ll modinv(ll a) {
    return modpow(a, mod - 2);
}

struct BIT {
    int size;
    vector<ll> bit;
    BIT(int size) : size(size), bit(size + 1, 1) {}
    void update(int k, ll x) {
        k++;
        while (k <= size) {
            (bit[k] *= x) %= mod;
            k += k & -k;
        }
    }
    ll query(int k) {
        k++;
        ll res = 1;
        while (k > 0) {
            (res *= bit[k]) %= mod;
            k -= k & -k;
        }
        return res;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep (i, n) scanf("%d", &a[i]);

    vector<vector<int>> pf(1010101);
    for (int i = 2; i < pf.size(); i++) {
        if (pf[i].empty()) {
            for (int j = i; j < pf.size(); j += i) {
                pf[j].push_back(i);
            }
        }
    }

    int q;
    cin >> q;
    vector<int> l(q), r(q), index(q);
    vector<tuple<int, int, int>> rli(q);
    rep (i, q) {
        scanf("%d %d", &l[i], &r[i]);
        l[i]--; r[i]--;
        rli[i] = make_tuple(r[i], l[i], i);
    }
    sort(rli.begin(), rli.end());
    rep (i, q) tie(r[i], l[i], index[i]) = rli[i];

    vector<int> ans(q), last(1010101, -1);
    BIT bit(202020), bit2(202020);
    int k = 0;
    rep (i, n) {
        bit.update(i, a[i]);
        for (int p : pf[a[i]]) {
            ll x = (p - 1) * modinv(p) % mod;
            if (last[p] != -1) bit.update(last[p], modinv(x));
            last[p] = i;
            bit.update(last[p], x);
        }
        while (k < q && r[k] == i) {
            ll x = bit.query(r[k]) * modinv(bit.query(l[k] - 1)) % mod;
            ll y = bit2.query(r[k]) * modinv(bit2.query(l[k] - 1)) % mod;
            ans[index[k]] = x * y % mod;
            k++;
        }
    }

    rep (i, q) printf("%d\n", ans[i]);
    return 0;
}

コメント

解説見たらなるほどと思う問題。本番中もクエリ先読みは考えていたんだけれどこの方法は思いつかなかった。応用が効きそう。