自动搬运

查看原文

来自洛谷，原作者为

	Prean 不断倒下，不断站起来，不停地与自己作斗争

搬运于2025-08-24 22:31:14，当前版本为作者最后更新于2021-05-02 18:05:46，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

设：

那么很明显有：

再看一眼 $g$，我们发现 $g$ 是积性函数。

使用P5495的办法即可做到 $O(m+n\log \log n)$，轻松通过此题。

#include<cstdio>
const int M=1e7+5,mod=998244353;
typedef unsigned uint;
int n,m,top,f[24],g[M],pri[M],C[M];uint ans,b[M],a[M];
int fac[M],ifac[M];bool zhi[M];
uint seed;
inline int Add(const int&a,const int&b){
    return a+b>=mod?a+b-mod:a+b;
}
inline uint randomdigit(){
    seed^=seed<<13;
    seed^=seed>>17;
    seed^=seed<<5;
    return seed;
}
signed main(){
    register int i,j,x;
    scanf("%d%d%u",&n,&m,&seed);
    a[1]=randomdigit()%mod;
    fac[0]=ifac[0]=fac[1]=ifac[1]=1;
	fac[2]=2;ifac[2]=499122177;
	for(i=3;i<=m+24;++i){
		fac[i]=1ll*fac[i-1]*i%mod;
		ifac[i]=1ll*(mod-mod/i)*ifac[mod%i]%mod;
	}
	for(i=1;i<=m+24;++i)ifac[i]=1ll*ifac[i]*ifac[i-1]%mod;
    for(i=0;i<24;++i){
        f[i]=1ll*ifac[i]*ifac[m]%mod*fac[i+m]%mod;
    }
    for(i=2;i<=n;++i){
        a[i]=randomdigit()%mod;
        if(!zhi[i])pri[++top]=i;
        for(j=1;j<=top&&(x=i*pri[j])<=n;++j){
            zhi[x]=1;if(!(i%pri[j]))break;
        }
    }
    for(i=1;i<=top;++i){
        for(j=n/pri[i];j;--j){
        	for(long long x,k=pri[i],cnt=1;(x=j*k)<=n;++cnt,k*=pri[i]){
                a[x]=Add(a[x],1ll*a[j]*f[cnt]%mod);
            }
        }
    }
    for(i=1;i<=n;++i)ans^=a[i];
    printf("%u",ans);
}