Please, another Queries on Array? [Codeforces Round #538 (Div. 2) F]

https://codeforces.com/contest/1114/problem/F

N要素の配列Aがある。
これについて以下のクエリをQ回行う。

操作1: "MULTIPLY l r x" A[l], A[l+1], ..., A[r]全てにxをかける
操作2: "TOTIENT l r" φ（A[l]*A[l+1]*..*A[r]) mod 10^9+7を答える
φ(x)はトーティエント関数である。

1≦N≦4*10^5
1≦Q≦2*10^5
1≦a[i]≦300

前提知識

• 遅延評価セグメントツリー
• トーティエント関数の知識

解説

https://codeforces.com/contest/1114/submission/49736772

トーティエント関数についてググろう。
nの素因数をp1,p2,...,pkとすると、φ(n) = n * (1-1/p1)*(1-1/p2)*...*(1-1/pk)
この知識を使って解く。
　
つまり、区間について総積と素因数の出現するかが高速に得られればいい。
どちらも遅延評価セグメントツリーによって解決することができる。
　
nの部分は、区間積・区間総積の遅延評価セグメントツリーを使えば高速に求まる。
　
(1-1/p1)*(1-1/p2)*...*(1-1/pk)の部分は、このまま遅延評価セグメントツリーに乗らないので、素因数が出現するかをbitsetにして、それを乗せることにする。
300以下の素因数は100未満であるため、bitset<100>を遅延評価セグメントツリーに乗せる。
1番目の素数があれば、1番目を１にする。のようにしてbitsetを作る。
すると、区間or・区間orの遅延評価セグメントツリーがあれば、高速に出現するかを得られる。
　
これで操作1は実現できた。
操作2も素因数が出現するかのbitsetを入手したあとに、1が立っている素数について(1-1/p)をかけていけばいい。
　
メモリもTLも厳しいので、うまく実装しよう。
（自分はmintをやめて実装した）

int N, Q, A[401010];
//---------------------------------------------------------------------------------------------------
LazySegTreeMul<1 << 19> lstMul;
LazySegTreeOr<1 << 19> lstOr;
vector<int> vp = makePrimes(300);
bitset<70> encode[301];
int d[301];
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];
    rep(x, 1, 301) rep(i, 0, vp.size()) if (x % vp[i] == 0) encode[x][i] = 1;
    rep(i, 0, N) {
        lstMul.update(i, i + 1, A[i]);
        lstOr.update(i, i + 1, encode[A[i]]);
    }
    rep(i, 0, vp.size()) d[i] = sub(1, mul(1, modinv(vp[i])));

    rep(q, 0, Q) {
        string t; cin >> t;
        if (t == "TOTIENT") {
            int l, r; cin >> l >> r; l--;
            int ans = lstMul.get(l, r);
            auto bs = lstOr.get(l, r);
            rep(i, 0, vp.size()) if (bs[i]) ans = mul(ans, d[i]);
            printf("%d\n", ans);
        }
        else {
            int l, r, x; cin >> l >> r >> x;
            l--;

            lstMul.update(l, r, x);
            lstOr.update(l, r, encode[x]);
        }
    }
}