自动搬运

查看原文

来自洛谷，原作者为

	Polarisx 一位努力不落后的 NPC

搬运于2025-08-24 23:07:09，当前版本为作者最后更新于2024-12-21 14:50:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目传送门。

思路

推式子，考虑从 $g(x)$ 推到 $g(x\times p^c),(p\bot x,p\in\mathbb{P})$，有

$$\begin{aligned} g(x\times p^c)&=\prod_{d\mid xp^c} f(d)\\ &-\prod_{k=0}^c \prod_{d\mid x}f(d)f(p^k)\\ &=\prod_{k=0}^c f(p^k)^{\sigma_0(x)}g(x)\\ &=g(x)^{c+1}g(p^c)^{\sigma_0(x)} \end{aligned} $$

空间只有 50MB，线性筛显然是行不通的，考虑枚举素数来获得合数，搜索过程中记录一下需要的值即可，但是我们发现 $g(p^c)^{\sigma_0(x)}$ 无法简单得到，因此时间复杂度必定带个 $\log$。

考虑空间换时间，5e7 的数组显然开不下，考虑分成两批来做，令 $\mathrm{mxp}(n)$ 表示 $n$ 的最大素因子，不妨将 $[1,n]$ 的数分成 $\mathrm{mxp}(i)\le \sqrt n$ 与 $\mathrm{mxp}(i)>\sqrt n$，对于第一批，搜索加上记忆化即可，对于第二批，由于它们至多只有一个大于 $\sqrt n$ 的素因子，单独计算这个素因子的贡献即可。

时间复杂度可近似看成 $\mathcal O (n)$。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int Mod=1e9+7;
const int Maxm=5e7+5,B=7200;
vector<int>prm;
bitset<Maxm>isp;
int ans;
int n,sz;
int mp[960][26][352];
int g[B+5],d[B+5];

inline ll ksm(ll a,int b,int mod){
	ll z=1;
	while(b){
		if(b&1) z=z*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return z;
}
void dfs(int p,int now,int G,int divs){
	ans^=G;
	if(now<=B){
		g[now]=1ll*G*G%Mod;d[now]=divs;
	}
	for(int i=p;i<sz;i++){
		int nz=now,nf=1,ng=1,nG=G;
		const int P=prm[i];
		if(1ll*nz*P>n) break;
		for(int c=1;;c++){
			if(1ll*nz*P>n) break;
			nz*=P; nf=1ll*nf*P%Mod*P%Mod; ng=1ll*ng*(nf+c)%Mod;
			nG=1ll*nG*G%Mod; int pw;
			if(!mp[i][c][divs]) mp[i][c][divs]=ksm(ng,divs,Mod);
			pw=mp[i][c][divs];
			dfs(i+1,nz,1ll*nG*pw%Mod,divs*(c+1));
		}
	}
}

int main(){
	scanf("%d",&n);
	for(int i=2;i<=min(n,B);i++){
		if(!isp.test(i)){
			prm.emplace_back(i);
			for(int j=i+i;j<=n;j+=i) isp.set(j);
		}
	}
	sz=prm.size();
	dfs(0,1,1,1);
	for(int i=B+1;i<=n;i+=2){
		if(!isp.test(i)){
			int v=(1ll*i*i+1)%Mod;
			for(int j=1;i*j<=n;j++){
				ans^=((1ll*g[j]*ksm(v,d[j],Mod))%Mod);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}