BZOJ 4804: 欧拉心算（线性筛/莫比乌斯反演）
Posted On 2019年4月11日
4804: 欧拉心算
积性函数的狄利克雷卷积仍是积性函数，线性筛即可
复杂度\(O(maxn+Q\sqrt{n})\)
|
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 |
#include <cstdio> #include <bitset> #include <iostream> #include <cstdlib> typedef long long ll; using namespace std; inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=1e7+100,N=10000000; int prime[664579+10],miu[maxn],cnt,phi[maxn],mi[maxn],CNT; ll combine[maxn]; bitset<maxn>vis; inline void pre() { combine[1]=phi[1]=miu[1]=1; for (int i=2;i<=N;i++) { if (!vis[i])prime[++CNT]=i,miu[i]=-1,vis[i]=i,phi[i]=i-1,combine[i]=miu[i]*phi[1]+miu[1]*phi[i],mi[i]=i; for (int j=1;1ll*prime[j]*i<=N&&j<=CNT;j++) { vis[i*prime[j]]=prime[j]; if (i%prime[j]==0) { mi[i*prime[j]]=mi[i]*prime[j]; phi[i*prime[j]]=prime[j]*phi[i]; int remain=i/mi[i],left=mi[i*prime[j]]; combine[prime[j]*i]=(miu[1]*phi[left]+miu[prime[j]]*phi[left/prime[j]])*combine[remain]; break; } mi[i*prime[j]]=prime[j]; miu[prime[j]*i]=-miu[i]; phi[prime[j]*i]=phi[i]*phi[prime[j]]; combine[prime[j]*i]=combine[prime[j]]*combine[i]; } } for (int i=1;i<=N;i++)combine[i]+=combine[i-1]; } inline ll solve(int n) { ll ans=0; for (int l=1,r;l<=n;l=r+1) { r=n/(n/l);int v=n/l; ans+=1ll*v*v*(combine[r]-combine[l-1]); } return ans; } signed main() { pre(); int T=read(); while (T--)printf("%lld\n",solve(read())); } |
或
再推推
直接筛即可，复杂度\(O(n)\)
|
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 |
#include <cstdio> #include <bitset> #include <iostream> #include <cstdlib> typedef long long ll; using namespace std; inline int read() { int f=1,k=0;char c=getchar(); while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar(); return k*f; } const int maxn=1e7+100,siz=664579+10,sizq=5005; ll combine[maxn]; int prime[siz],cnt,mi[maxn],MI[maxn],CNT,N,phi[maxn]; bitset<maxn>vis; int q[sizq]; inline void pre() { mi[1]=combine[1]=phi[1]=1; for (int i=2;i<=N;i++) { if (!vis[i])prime[++CNT]=i,vis[i]=i,phi[i]=i-1,mi[i]=i,combine[i]=phi[i]*phi[1]*2,MI[i]=1; for (int j=1;prime[j]*i<=N&&j<=CNT;j++) { int too=i*prime[j]; vis[too]=prime[j]; if (i%prime[j]==0) { mi[too]=mi[i]*prime[j]; MI[too]=MI[i]+1; phi[too]=prime[j]*phi[i]; int remain=i/mi[i],left=mi[too]; ll LEFT=((MI[too]-1)*(phi[prime[j]]*phi[prime[j]])*mi[left/prime[j]/prime[j]]+phi[prime[j]]*2*mi[i]); combine[i*prime[j]]=LEFT*combine[remain]; break; } MI[too]=1; mi[too]=prime[j]; phi[too]=phi[i]*phi[prime[j]]; combine[too]=combine[prime[j]]*combine[i]; } } for (int i=1;i<=N;i++)combine[i]=combine[i]*2+combine[i-1]-phi[i]; } signed main() { int T=read(); for (int i=1;i<=T;i++)q[i]=read(),q[i]>N&&(N=q[i]); pre(); for (int i=1;i<=T;i++)printf("%lld\n",combine[q[i]]); } |
Subscribe
0 评论