自动搬运

查看原文

来自洛谷，原作者为

	DeepSkyCore bot @zwh2008 orz

搬运于2025-08-24 21:33:05，当前版本为作者最后更新于2025-03-22 12:31:42，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

此题解非正解，复杂度 $O(n\log n)$，但是进行了有效的常数优化。

显然有一个非常简单的做法：先筛出来 $\varphi(x)$，然后从小到大枚举 $i$，枚举 $ij=x$，把 $f_i$ 和 $\varphi(j)$ 转移到 $f_x$ 即可。由于因数数量是 $O(n\log n)$，所以这个复杂度也是 $O(n\log n)$。

不过如果真的就这么写，自然是过不去的。这里提供一个常数非常小的写法，似乎在这题数据范围下比正解还快很多。

先想想这个东西为什么会慢。算一算实际的转移次数，甚至都不到 $10^9$，而时限 $4$ 秒，所以问题出在内存访问不够快。

首先考虑分块转移，也就是从小到大枚举 $x\in [kB, (k+1)B)$，然后对这个区间再枚举 $ij=x$ 转移。这样我们扫描一个 200MB 的数组的次数减小了，就会快很多，大概只需要跑 3s。下面是一个参考实现，其中，计算除法的部分还用了一次整除分块：

constexpr int B = 2e6;
int n; cin>>n;
vector<u32> f(n+1), lst(n+1, 2);
f[1] = 1;
for(int l = 1, r = min(B, n); l <= n; l = r+1, r = min(l + B - 1, n)){
	for(u32 l0 = 1, r0, k; ; l0 = r0+1){
		k = r / l0, r0 = r / k;
		if(k == 1) break;
		rep(i,l0,r0){
			while(lst[i] <= k){
				f[i*lst[i]] += f[i] * phi[lst[i]];
				lst[i]++;
			}
		}
	}
}
u32 ans = 0;
rep(i,1,n){
	ans ^= f[i];
}
cout<< ans <<'\n';

不过就算这么搞，我们还是要多次扫描一遍 200MB 的数组，同时还需要在大概 8MB 的数组做随机访问，还能不能优化呢？

考虑一个非常简单的结论：设 $ij=x$，则 $\min(i,j)\le \sqrt x$。因此我们在分块后，区间转移的过程只需要枚举较小的那个因数就行了。

这么搞的话不需要多次扫 200MB 的数组，同时随机访问的内存也更密集。这样就跑得很快了，大概只需要 1.3s。同样给出参考实现：

constexpr int B = 65536
int n; cin>>n;
vector<u32> f(n+1);
f[1] = 1;

int l = 1, r = min(n, B);
rep(i,1,r/2){
	for(int j=2; j <= r/i; j++){
		f[j*i] += f[i] * phi[j];
	}
}
l = r+1, r = min(l + B - 1, n);
for(; l <= n; l = r+1, r = min(l + B - 1, n)){
	rep(j,l,r){
		f[j] += phi[j];
	}
	rep(i,2,B){
		rep(j, max(i, (l-1)/i+1), r/i){
			f[i*j] += f[i]*phi[j];
			if(i != j) f[i*j] += phi[i]*f[j];
		}
	}
}

u32 ans = 0;
rep(i,1,n){
	ans ^= f[i];
}
cout<< ans <<'\n';

在这题中，由于函数固定，我们还可以结合分段打表。

同时，上述解法的常数非常小。可以看出即使上面的参考实现仍有优化空间，这段代码仍然能在 P5495 取得优于一般 $O(n\log\log n)$ 写法的前缀和的结果。

虽然复杂度更劣，但是由于好写好调常数小，暴力仍然是一个不错的选择。希望大家能够学会这种写法。