C++14(g++5.4) 解法, 执行用时: 446ms, 内存消耗: 130280K, 提交时间: 2019-09-12 23:24:54

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e7+100;
const int mod=1000000007;
int inv[110];
int p[N],num[N];
ll ans[N];
bool vis[N];
int tot=0; 
int main()
{
	ll n,k;
	cin>>n>>k;
	k%=mod;
	inv[0]=1,inv[1]=1,ans[1]=1;
	for(int i=2;i<=100;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=n;i++)
	{
		if(vis[i]==0) p[++tot]=i,num[i]=1,ans[i]=k;
		for(int j=1;j<=tot&&i*p[j]<=n;j++)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0)
			{
				ans[i*p[j]]=1ll*ans[i]*(num[i]+k)%mod*inv[num[i]+1]%mod;
				num[i*p[j]]=num[i]+1;
				break;
			}
			ans[i*p[j]]=1ll*ans[i]*k%mod;
			num[i*p[j]]=1;
		}
	}	
	ll res=0;
	for(int i=1;i<=n;i++) res^=(ans[i]+i)%mod;
	cout<<res<<endl;
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 447ms, 内存消耗: 91048K, 提交时间: 2019-11-10 16:56:51

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

int MOD=1e9+7,num[10000005],T[1000005],inv[70],ans[10000005];
bool V[10000005]={0};
int main()
{
	int n,i,j,t=0;
	long long k;
	scanf("%d%lld",&n,&k);
	k%=MOD,inv[1]=ans[1]=1;
	for(i=2;i<70;i++)inv[i]=(long long)(MOD-MOD/i)*inv[MOD%i]%MOD;
	for(i=2;i<=n;i++)
	{
		if(!V[i])ans[i]=k,T[t++]=i,num[i]=1;
		for(j=0;j<t&&i*T[j]<=n;j++)
		{
			V[i*T[j]]=1;
			if(i%T[j]==0)
			{
				ans[i*T[j]]=(long long)ans[i]*(num[i]+k)%MOD*inv[num[i]+1]%MOD;
				num[i*T[j]]=num[i]+1;
				break;
			}
			ans[i*T[j]]=(long long)ans[i]*k%MOD;
			num[i*T[j]]=1;
		}
	}
	for(j=i=2;i<=n;i++)j^=(ans[i]+i)%MOD;
	printf("%d\n",j);
}