waht 先生的法阵

题目链接。cnblogs。

Problem

给定数列 a。需要支持 Q 次操作，分为以下两种。

1. 区间乘 c（2 \le c \le 2.5\times 10^5）。
2. 给出 x，按以下方法得到答案：记答案为 ans，初始时为 0。从 x 开始，每次 ans \gets ans+a_x 后 x \gets x+\gcd(x, a_x)。当 x 大于 n 时结束。求出 ans 对 998244353 取模的值。

数据范围：1 \le n, Q \le 2.5\times 10^5, a_i \in [1, 998244353) \cap \mathbb{Z}。

Sol

这个东西和 CF1491H Yuezheng Ling and Dynamic Tree 这道题很像啊。不难发现，对于 i，\gcd(i, a_i) 的变化次数是非常有限的，可以直接均摊出来。直接考虑分块。

不妨记 to_i 和 sum_i 分别表示 i 跳出当前块的右端点时的位置和经过的权值和。对于散块可以暴力更新。对于整块：

• 如果块内所有 \gcd(i, a_i) = 1。跳过该块。
• 否则找到所有会被更改的点，暴力更新。

如果块长取 B，则一个点更改一次的时间复杂度是 \mathcal{O}(B) 的。判断整块是否需要更新可以枚举 c 的所有质因数，然后看这块中有没有数乘上这个质因数后 \gcd 会变化（这个可以对每个数记录还有那些质因数以及次数，然后就是查询区间是否有值）。

对于枚举质数的部分，时间复杂度为：\mathcal{O}(m \omega(c)\log n)。

查询的复杂度：\mathcal{O}(\frac nB)。

现在考虑一个数会修改多少次，显然当 a_i 都是 1 的时候变化次数最多。考虑质数 p 会产生多少的贡献，这个显然为 \sum\limits_{i=1}^{+\infty} \lfloor \frac{n}{p^i} \rfloor \le \sum\limits_{i=1}^{+\infty} \frac{n}{p^i} = \frac{n}{p - 1}，即所有数分解质因数后 p 的出现次数和。所以最后所有数的变化次数为 \sum_{p \in \text{prime}} \frac{n}{p-1}。clx 表示这是欧依的。根据埃氏筛的时间复杂度分析，这个是 \mathcal{O}(\ln \ln n) 的。

所以修改的时间是 \mathcal{O}(B n \ln \ln n)。

当 m\frac nB = Bn \ln \ln n 时，即 B = \sqrt{\frac{m}{\ln \ln n}} 时有最小值。时间复杂度为：\mathcal{O}(n\sqrt{m \ln \ln n})。题解有不对的地方欢迎大家指正！

Code

代码没有卡过常，跑得很慢。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
mt19937_64 eng(time(0) ^ clock());
template<typename T>
T rnd(T l, T r) { return eng() % (r - l + 1) + l; }
int pC, pri[250005];
bool vis[250005];
vector<int> d[250005];
void Init(int n) {
    for (int i = 2; i <= n; i++) {
        if (!vis[i])
            pri[++pC] = i;
        for (int j = 1; j <= pC && i * pri[j] <= n; ++j) {
            vis[i * pri[j]] = 1;
            if (i % pri[j] == 0)
                break;
        }
    }
    for (int i = 1; i <= pC && pri[i] <= n; i++)
        for (int j = pri[i]; j <= n; j += pri[i])
            d[j].emplace_back(i);
    memset(vis, 0, sizeof(vis));
}
const int B = 200, P = 998244353;
int n, m;
int bel[250005], L[250005], R[250005], g[250005], re[250005], to[250005];
ll a[250005], sum[250005], laz[250005];
set<int> s[250005];
int tpt, stkt[250005];
int tp, stk[250005];
void Calc(int i) {
    int x = i;
    sum[i] = 0;
    while (x <= R[bel[i]]) {
        (sum[i] += a[x]) %= P;
        x += g[x];
    }
    to[i] = x;
}
bool arv[250005];
void Update(int x) {
    for (int i = R[x]; i >= L[x]; i--) {
        sum[i] = a[i] % P;
        if (i + g[i] <= R[x]) {
            (sum[i] += sum[i + g[i]]) %= P, to[i] = to[i + g[i]];
        } else {
            to[i] = i + g[i];
        }
    }
}
void Modify(int l, int r, ll c) {
    int x = bel[l], y = bel[r];
    int now = c;
    for (int i : d[c]) {
        if ((int) s[i].size() == 0)
            continue;
        int cnt = 0;
        while (now % pri[i] == 0)
            now /= pri[i], cnt++;
        auto pl = s[i].lower_bound(l);
        auto pr = s[i].lower_bound(r + 1);
        for (auto it = pl; it != pr; it++) {
            int p = *it, tmp = cnt;
            while (re[p] % pri[i] == 0 && tmp > 0)
                re[p] /= pri[i], g[p] *= pri[i], tmp--;
            if (re[p] % pri[i])
                stkt[++tpt] = p;
            if (!vis[p])
                stk[++tp] = p, vis[p] = 1;
        }
        while (tpt)
            s[i].erase(stkt[tpt--]);
    }
    for (int i = 1; i <= tp; i++) {
        Calc(stk[i]);
        Update(bel[stk[i]]);
    }
    for (int i = 1; i <= tp; i++)
        vis[stk[i]] = 0;
    tp = 0;
    if (x == y) {
        for (int i = l; i <= r; i++)
            a[i] = a[i] * c % P;
        Update(x);
    } else {
        for (int i = l; i <= R[x]; i++)
            a[i] = a[i] * c % P;
        for (int i = L[y]; i <= r; i++)
            a[i] = a[i] * c % P;
        Update(x), Update(y);
        for (int i = x + 1; i < y; i++)
            laz[i] = laz[i] * c % P;
    }
}
int main() {
    scanf("%d%d", &n, &m);
    Init(250000);
    for (int i = 1; i <= n; i++)
        scanf("%lld", a + i);
    for (int i = 1; i <= n; i++)
        bel[i] = (i - 1) / B + 1;
    for (int i = 1; i <= bel[n]; i++)
        L[i] = (i - 1) * B + 1, R[i] = min(n, i * B);
    for (int i = 1; i <= bel[n]; i++)
        laz[i] = 1;
    for (int i = 1; i <= n; i++) {
        g[i] = __gcd((ll) i, a[i]);
        re[i] = i / g[i];
        for (int j : d[re[i]])
            s[j].emplace(i);
    }
    for (int i = 1; i <= n; i++)
        Calc(i);
    for (int _ = 1, op, x, y, z; _ <= m; _++) {
        scanf("%d%d", &op, &x);
        if (op == 1) {
            scanf("%d%d", &y, &z);
            Modify(x, y, z);
        } else {
            ll ans = 0;
            for (int i = x; i <= n; i = to[i])
                (ans += sum[i] * laz[bel[i]] % P) %= P;
            printf("%lld\n", ans);
        }
    }
    return 0;
}

原始代码 & gen & 暴力