BZOJ3560:DZY Loves Math V 数学
思路:
首先我们需要知道欧拉函数的计算方法:
n=pq11pq22...pqmm→ϕ(n)=np1−1p1p2−1p2...pm−1pm
ϕ(n)=pq11p1−1p1pq22p2−1p2...pqmmpm−1pm
这证明我们可以将所有的质因数分开考虑.
我们对于所有质因数计算其贡献,然后乘到一起.(这东西维护一个前缀和就行了)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include<cstdio>#include<cstring>#include<cctype>#include<iostream>#include<algorithm>#include<vector>using namespace std; #define N 10000010int p[N/10],ins[N],cnt;bool notp[N];vector<int>v[N/10];inline void pre(){ register int i,j; for(i=2;i<=10000000;++i){ if(!notp[i])p[++cnt]=i,ins[i]=cnt; for(j=1;j<=cnt&&i*p[j]<=10000000;++j){ notp[i*p[j]]=1; if(i%p[j]==0)break; } }} static const int mod=(1e9)+7;inline int ksm(int x,int y){ int t=x,res=1;for(;y;y>>=1,t=(long long)t*t%mod)if(y&1)res=(long long)res*t%mod;return res;}inline int inv(int x){ return ksm(x,mod-2);}inline void inc(int&x,int y){ if((x+=y)>=mod)x-=mod;} int seq[1000010],num;vector<int>vv[1000010]; int pref[40]; int main(){ pre(); int n;scanf("%d",&n);register int i,j,k; int x,nowadd; while(n--){ scanf("%d",&x);if(x==1)continue; for(i=1;i<=cnt&&p[i]*p[i]<=x;++i){ nowadd=0;while(x%p[i]==0)++nowadd,x/=p[i]; if(nowadd)v[i].push_back(nowadd); }if(x)v[ins[x]].push_back(1); } for(i=1;i<=cnt;++i)if((int)v[i].size()!=0){ seq[++num]=p[i]; for(j=0;j<(int)v[i].size();++j)vv[num].push_back(v[i][j]); } if(num==0)puts("1"); else{ int res=1,Mx,mi,tans; for(k=1;k<=num;++k){ for(Mx=0,i=0;i<vv[k].size();++i)Mx=max(Mx,vv[k][i]); for(pref[0]=1,mi=seq[k],i=1;i<=Mx;++i,mi=(long long)mi*seq[k]%mod)inc(pref[i]=pref[i-1],mi); for(tans=1,i=0;i<vv[k].size();++i)tans=(long long)tans*pref[vv[k][i]]%mod; tans=(long long)(tans+mod-1)*(seq[k]-1)%mod; tans=(long long)tans*inv(seq[k])%mod; res=(long long)res*(tans+1)%mod; } printf("%d",res); } return 0;} |
评论 (0)