C++14(g++5.4) 解法, 执行用时: 203ms, 内存消耗: 44792K, 提交时间: 2020-09-11 20:26:50

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 998244353;
const int maxn = 10010010;
int p[maxn],f[maxn],g[maxn];
int qpow(int a, int n) {
    int ans=1; for (;n;n>>=1,a=(ll)a*a%mod) if (n&1) ans=(ll)ans*a%mod;
    return ans;
}
int main(void) {
    //freopen("f.in","r",stdin);
    int n, P, Q; scanf("%d%d%d",&n,&P,&Q);
    memset(f,0xff,sizeof(f));
    f[1]=1;
    for (int i=2;i<=n;i++) {
        if (!~f[i]) {
            p[++p[0]] = i;
            g[p[0]]=qpow(i,Q);
            f[i]=(g[p[0]]-qpow(i,P)+mod)%mod;
        }
        for (int j=1;j<=p[0]&&p[j]*i<=n;j++) {
            if (i%p[j]==0) {
                f[i*p[j]]=f[i]*(ll)g[j]%mod;
                break;
            }
            f[i*p[j]]=f[i]*(ll)f[p[j]]%mod;
        }
    }
    int ans = 0;
    for (int i=1;i<=n;i++) ans ^= f[i];
    printf("%d\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 213ms, 内存消耗: 54520K, 提交时间: 2020-09-12 10:55:18

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

const int p=998244353,maxN=10000000;
int N,P,Q;
int qpow(int a,int k){
	int ans=1;
	while(k){
		if(k&1) ans=1LL*ans*a%p;
		a=1LL*a*a%p;
		k>>=1;
	}
	return ans;
}

bool flg[maxN+5];
int F[maxN+5],ans;
int d[maxN+5],dq[maxN+5],len;

int main(){
	scanf("%d%d%d",&N,&P,&Q);
	F[1]=1;ans=1;
	for(int i=2;i<=N;i++){
		if(!flg[i]){
			d[len]=i;int iq=qpow(i,Q);dq[len]=iq;len++;
			F[i]=(iq-qpow(i,P)+p)%p;
		}
		if(i<=N) ans^=F[i];
		for(int j=0;j<len&&i*d[j]<=N;j++)
			if(i%d[j]==0){F[i*d[j]]=1LL*F[i]*dq[j]%p;flg[i*d[j]]=1;break;}
			else F[i*d[j]]=1LL*F[i]*F[d[j]]%p,flg[i*d[j]]=1;
	}
	printf("%d\n",ans);
	
	return 0;
}