定义
如果(f:N ightarrow R),满足对任意互质的正整数(p,q),都有(f(qp)=f(q)f(p)),则称f(x)为积性函数
例子：
(1(n)=1)
(id(n)=n)
(epsilon(n)=[n=1],epsilon(1)=1,epsilon(n>1)=0)
(phi(n)=1···n中与n互质的个数)
(d(n)=n的正因子个数)
具体实现：
设f为积性函数，假设(n=p_1^{alpha 1}p_2^{alpha 2}···p_k^{alpha k})
则(f(n)=f(p_1^{alpha 1})f(p_2^{alpha 2})···f(p_k^{alpha k}))
用质因数分解求f(n)
点击查看代码
int solve(int x){
int ans=1;
for(int i=2;i<=sqrt(x);i++){
int cnt=0;
while(x%i==0){x/=i,cnt++;}
ans*=calc_f(i,cnt);
}
if(x>1)ans*=calc_f(x,1);
return ans;
}
点击查看代码
void init(){
f[1]=1;
for(int i=2;i<=maxn;i++){
if(!is[i])prime[++tot]=i,cnt[i]=1,f[i]=calc_f(i,1);
for(int j=1;j<=tot && i<=maxn/prime[j];j++){
is[i*prime[j]]=1;
if(i%prime[j]==0){
cnt[i*prime[j]]=cnt[i]+1;
f[i*prime[j]]=f[i]/calc_f(prime[j],cnt[i])*calc_f(prime[j],cnt[i]+1);
break;
}
cnt[i*prime[j]]=1;
f[i*prime[j]]=f[i]*calc_f(prime[j],1);
}
}
}
应用：
点击查看代码
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<deque>
#define ll long long
using namespace std;
const int maxn=10000000+101;
const int MOD=1000000007;
const ll inf=2147483647;
int read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
return x*f;
}
int q,f[maxn],cnt[maxn];
int tot,prime[maxn],is[maxn];
int calc_f(int x,int i){return i+1;}
void init(){
f[1]=1;
for(int i=2;i<=maxn;i++){
if(!is[i])prime[++tot]=i,cnt[i]=1,f[i]=calc_f(i,1);
for(int j=1;j<=tot && i<=maxn/prime[j];j++){
is[i*prime[j]]=1;
if(i%prime[j]==0){
cnt[i*prime[j]]=cnt[i]+1;
f[i*prime[j]]=f[i]/calc_f(prime[j],cnt[i])*calc_f(prime[j],cnt[i]+1);
break;
}
cnt[i*prime[j]]=1;
f[i*prime[j]]=f[i]*calc_f(prime[j],1);
}
}
}
int main(){
q=read();init();
for(int i=1;i<=q;i++){
int x=read();printf("%d
",f[x]);
}
return 0;
}
2.华华给月月出题
点击查看代码
#include<functional>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<deque>
#define ll long long
using namespace std;
const int maxn=14000000+101;
const int MOD=1e9+7;
const int inf=2147483647;
int read(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
return x*f;
}
ll f[maxn];
int n,tot,prime[maxn],is[maxn];
ll M(ll x){return (x%MOD+MOD)%MOD;}
ll power(ll x,ll y){
ll ans=1;
while(y){
if(y&1)ans=ans*x%MOD;
y>>=1;x=x*x%MOD;
}
return ans%MOD;
}
ll calc_f(int x,int i){return power((ll)x,(ll)i);}
void init(){
f[1]=1ll;
for(int i=2;i<=n;i++){
if(!is[i])prime[++tot]=i,f[i]=calc_f(i,n)%MOD;
for(int j=1;j<=tot && i<=n/prime[j];j++){
is[i*prime[j]]=1;f[i*prime[j]]=f[i]*f[prime[j]]%MOD;
if(i%prime[j]==0)break;
}
}
}
int main(){
n=read();init();ll ans=0;
for(int i=1;i<=n;i++)ans^=f[i];printf("%lld",ans);
return 0;
}