题解 | #漂亮数#

题解说的好玄乎,其实就是分配律 该题数据范围过大,直接快速幂会超时,所以我们预处理质数的快速幂,利用线性筛和算术基本定理快速求出某个数的i^N

#include <bits/stdc++.h>

using namespace std;

using ll=long long;
const int N=2e7+10,mod=1e9+7;
ll f[N],p[N],cnt;
bool st[N];
ll n,ans;

ll qmi(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}//快速幂模板

void init(){
    f[1]=1;//初始化f[1]=1,
    for(int i=2;i<=n;i++){
        if(!st[i]){
            p[cnt++]=i;
            f[i]=qmi(i,n);//求出质数的N次方
        }
        for(int j=0;p[j]<=n/i;j++){
            st[i*p[j]]=1;
            f[i*p[j]]=f[i]*f[p[j]]%mod;
            //f[i]相当于小于p[j]的所有质数的N次方的乘积
            if(i%p[j]==0) break;
        }
    }
}//线性筛模板

int main(){
    cin >> n;
    init();
    for(int i=1;i<=n;i++) ans^=f[i];
    cout << ans << endl;
}