题解：P9060 [Ynoi2002] Goedel Machine

· · 题解

解析：

既然是乘法，对每个质数的次幂单独考虑。

尝试用莫队去维护质数的次幂。我们现在要知道 p^{2^i-1} 的值，这个可以用倍增弄出来。

但是转移的时候需要枚举所有质因数的次幂，但是复杂度一定超了，过不了。

有关因数的问题，考虑根号分治。把所有质数次幂按照质数大小分成 \le 320 和 >320 来考虑。对于的质数的次幂之和不超过 120，所以拿出去用前缀和处理就行了。每个数只有一个 大于等于的质数，在莫队的时候 O(1) 维护就可以了。

切记：不要开 long long ，否则会时间超限。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, P = 998244353, iv = P + 1 >> 1;
int n, id[N], sq, l[N], r[N], p = 1, q, pr[N], ps[N], ret = 1, k, pp[N], cn[N], a[N], to[N], m, ans[N], c[N], fr[N], s[N];
vector<int>g[N], h[N];
int read() {
    int s = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - 48, ch = getchar();
    return s;
}
int cmp(int x, int y) {
    if (l[x] / sq ^ l[y] / sq)
        return l[x] < l[y];
    return r[x] < r[y];
}
int pown(int x, int y) {
    if (!y)
        return 1;
    int t = pown(x, y >> 1);
    if (y & 1)
        return 1LL * t * t % P * x % P;
    return 1LL * t * t % P;
}
void add(int x, int y) {
    ret = 1LL * ret * h[x][c[x]] % P;
    c[x] += y;
    ret = 1LL * ret * g[x][c[x]] % P;
}
signed main() {
    n = read(), m = read();
    sq = sqrt(n);
    for (int i = 2; i <= 320; i++) {
        if (pr[i])
            continue;
        for (int j = i; j <= 100000; j *= i)
            ps[++k] = j, fr[k] = i;
        for (int j = 2; j * i <= 100000; j++)
            pr[i * j] = 1;
    }
    for (int i = 1; i <= 100000; i++)
        to[i] = 1;
    for (int i = 321; i <= 100000; i++) {
        if (!pr[i]) {
            g[i].push_back(i);
            h[i].push_back(pown(i, P - 2));
            for (int j = 1; j * i <= 100000; j++)
                to[i * j] = i, pr[i * j] = 1;
        }
    }
    g[1].push_back(1);
    h[1].push_back(1);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
        g[to[a[i]]].push_back(1LL * g[to[a[i]]].back()*g[to[a[i]]].back() % P);
        h[to[a[i]]].push_back(1LL * h[to[a[i]]].back()*h[to[a[i]]].back() % P);
    }
    for (int i = 1; i <= m; i++)
        l[i] = read(), r[i] = read(), id[i] = i, ans[i] = 1;
    for (int i = 1; i <= k; i++) {
        for (int j = pp[0] = 1; j <= n; j++)
            s[j] = a[j] % ps[i] == 0;
        int iv = pown(pp[0] = fr[i], P - 2);
        for (int j = 1; j <= n; j++)
            s[j] += s[j - 1], pp[j] = 1LL * pp[j - 1] * pp[j - 1] % P;
        for (int j = 1; j <= m; j++)
            ans[j] = 1LL * ans[j] * pp[s[r[j]] - s[l[j] - 1]] % P * iv % P;
    }
    sort(id + 1, id + m + 1, cmp);
    for (int i = 1; i <= m; i++) {
        while (p > l[id[i]])
            add(to[a[--p]], 1);
        while (q < r[id[i]])
            add(to[a[++q]], 1);
        while (p < l[id[i]])
            add(to[a[p++]], -1);
        while (q > r[id[i]])
            add(to[a[q--]], -1);
        ans[id[i]] = 1LL * ans[id[i]] * ret % P;
    }
    for (int i = 1; i <= m; i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}

完结撒花，谢谢