链接：https://ac.nowcoder.com/acm/contest/392/C
来源：牛客网
题目描述
华华刚刚帮月月完成了作业。为了展示自己的学习水平之高超，华华还给月月出了一道类似的题：
Ans=⊕Ni=1(iNmod(109+7))Ans=⊕i=1N(iNmod(109+7))
⊕⊕符号表示异或和，详见样例解释。
虽然月月写了个程序暴力的算出了答案，但是为了确保自己的答案没有错，希望你写个程序帮她验证一下。
Ans=⊕Ni=1(iNmod(109+7))Ans=⊕i=1N(iNmod(109+7))
⊕⊕符号表示异或和，详见样例解释。
虽然月月写了个程序暴力的算出了答案，但是为了确保自己的答案没有错，希望你写个程序帮她验证一下。
输入描述:
输入一个正整数N。
输出描述:
输出答案Ans。
备注:
1≤N≤1.3×1071≤N≤1.3×107 解题思路：因为f(x)=x^n是一个完全积性函数，所以用线筛即可,不过不能开long long，会爆内存
定义
积性函数：对于任意互质的整数a和b有性质f(ab)=f(a)f(b)的数论函数。
完全积性函数：对于任意整数a和b有性质f(ab)=f(a)f(b)的数论函数。
常见积性函数
μ(n)：莫比乌斯函数
φ(n)：欧拉函数
d(n)：一个数nn的约数个数
σ(n)：一个数n的约数和
f(x)=x^k(k∈N)
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+;
const int maxn=1.3e7+;
int n,prime[maxn],f[maxn];
ll ans;
int qpow(int a,int b){
int res=;
while(b){
if(b&)res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=;
}
return res;
}
int main(){
scanf("%d",&n);
int tot=;
ans=;
memset(prime,,sizeof(prime));
for(int i=;i<=n;i++){
if(!prime[i]){
prime[tot++]=i;
f[i]=qpow(i,n);
}
for(int j=;j<tot&&prime[j]*i<=n;j++){
prime[i*prime[j]]=;
f[i*prime[j]]=1ll*f[i]*f[prime[j]]%mod;
if(i%prime[j]==)break;
}
ans^=f[i];
}
printf("%lld\n",ans);
return ;
}