首页 > 代码库 > BZOJ 4804: 欧拉心算
BZOJ 4804: 欧拉心算
Description
求\(\sum_{i=1}^n\sum_{i=1}^n\varphi(gcd(i,j)),T\leqslant 5\times 10^3,n\leqslant 10^7\)
Solution
数论分块+莫比乌斯反演.
化式子
\(\sum_{i=1}^n\sum_{i=1}^n\varphi(gcd(i,j))\)
\(=\sum_d\varphi(d)\sum_{i=1}^n\sum_{j=1}^n[(i,j)=d]\)
\(=\sum_d\varphi(d)(\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{d}\rfloor}[(i,j)=1])\)
\(=\sum_d\varphi(d)(\sum_{p}\mu(p)\sum_{i=1}^{\lfloor \frac{n}{pd}\rfloor}\sum_{j=1}^{\lfloor \frac{n}{pd}\rfloor})\)
\(\text{Let T=pd}\)
\(=\sum_{T}\lfloor \frac{n}{T}\rfloor\lfloor \frac{n}{T}\rfloor\sum_{p}\mu(p)\varphi(\frac{T}{p})\)
因为积性函数的狄利克雷前缀和也是积性函数，并且因为\(\mu\)的存在这个式子还是很好筛的.
Code
/************************************************************** Problem: 4804 User: BeiYu Language: C++ Result: Accepted Time:4272 ms Memory:128240 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; typedef long long LL;const int N = 10000050; int pr[N],cp;bool b[N];LL f[N]; void pre() { f[1]=1; for(int i=2;i<N;i++) { if(!b[i]) pr[++cp]=i,f[i]=i-2; for(int j=1;j<=cp && (LL)i*pr[j]<N;j++) { b[i*pr[j]]=1; if(i%pr[j]) f[i*pr[j]]=f[i]*f[pr[j]]; else { if(i/pr[j]%pr[j]) f[i*pr[j]]=f[i/pr[j]]*(pr[j]-1)*(pr[j]-1); else f[i*pr[j]]=f[i]*pr[j]; break; } } }for(int i=2;i<N;i++) f[i]+=f[i-1];}int T,n;int main() { pre(); for(scanf("%d",&T);T--;) { scanf("%d",&n); LL ans=0; for(int i=1,j;i<=n;i=j+1) { j=n/(n/i); ans+=1LL*(n/i)*(n/i)*(f[j]-f[i-1]); }printf("%lld\n",ans); } return 0;}
BZOJ 4804: 欧拉心算
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。