自动搬运

查看原文

来自洛谷，原作者为

	Pengzt 自己选择的路，跪着也要走完。

搬运于2025-08-24 23:08:06，当前版本为作者最后更新于2025-01-08 17:10:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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 & 暴力