#积性函数 #线性筛 #快速幂

题意

• 给定n，求解
• n<=1.3e7

思路

• 满足积性函数
• 需要找到n以下每个数的n次方，可以用筛法，质数的用快速幂计算，合数的用质数递推
• 因为空间限制，无法记录每个数的最小质因子，但其实可以直接暴力的乘上每一个质因子，同时开一个bool的vis数组保证每一个数只计算一遍

代码

#include<iostream>
using namespace std;
using ll=long long ;
const int N=13e6+10;
const int p=1e9+7;
ll qpow(ll a,ll b){
    a%=p;
    ll res=1;
    while(b){
      if(b&1) res=res*a%p;
      a=a*a%p;
      b>>=1;
    }
    return res;
}
int prime[N];
bool v[N];
ll res[N];

int ans=1;
int cnt=0;

int main(){
    int n;
    cin >> n;
    for(int i=2;i<=n;i++){
        if(v[i]==0){
            prime[cnt++]=i;
            v[i]=1;
            res[i]=qpow(i,n);
        }
        for(int j=0;j<cnt;j++){
            if(prime[j]*i>n) break;
            v[i*prime[j]]=1;
            res[i*prime[j]]=res[i]*res[prime[j]]%p;
        }
        ans^=res[i];
    }
    cout << ans << endl;
    return 0;
}