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