解题思路类似莫比乌斯函数之和
题目大意:求[1,n]内的欧拉函数$varphi$之和。($n<=2*10^{9}$)
思路:令$ M(n)=sum_{i=1}^{n}varphi (i) $,题目所求即为$ M(n) $。
由于$ sum_{d|n} varphi (d)=n $ ,所以$ sum_{i=1}^{n} sum_{d|i} varphi (d)=frac{n(n+1)}{2} $
令$ i=kd $,则有$ sum_{i=1}^{n} sum_{d|i} varphi (d)= sum_{k=1}^{n} sum_{d=1}^{left lfloor n/k ight floor} varphi (d) = sum_{k=1}^{n} M(left lfloor n/k ight floor) =frac{n(n+1)}{2} $
那么$ M(n)=frac{n(n+1)}{2}-sum_{i=2}^{n} M(left lfloor n/i ight floor) $
由于$ left lfloor n/i ight floor $的取值只有$ O(sqrt{n}) $种,预处理出前$ n^{frac{2}{3}} $的$ M(n) $,然后记忆化搜索,可以证明总时间复杂度为$ O(n^{frac{2}{3}}) $。
#include<cstdio> #define ll long long #define MN 1600000 #define MOD 2333333 struct edge{edge*nx;ll f;int x;}*h[MOD]; ll f[MN+5]; int p[MN+5],pn; bool u[MN+5]; ll cal(int n) { if(n<=MN)return f[n]; for(edge*i=h[n%MOD];i;i=i->nx)if(i->x==n)return i->f; edge*np=new edge;*np=(edge){h[n%MOD],1LL*n*(n+1)>>1,n};h[n%MOD]=np; for(int i=2,ls;i<=n;i=ls+1)ls=n/(n/i),np->f-=(ls-i+1)*cal(n/i); return np->f; } int main() { int n,i,j; scanf("%d",&n); for(f[1]=1,i=2;i<=MN;++i) { if(!u[i])p[++pn]=i,f[i]=i-1; for(j=1;i*p[j]<=MN&&(u[i*p[j]]=1);++j) if(i%p[j])f[i*p[j]]=f[i]*(p[j]-1); else{f[i*p[j]]=f[i]*p[j];break;} f[i]+=f[i-1]; } printf("%lld",cal(n)); }