求$sum_{i=1}^{n}varphi (i)$，$nleqslant 1e10$。
这里先把杜教筛的一般套路贴一下：
要求$S(n)=sum_{i=1}^{n}f(i)$，而现在有一数论函数$g(i)$，$g(i)$的前缀和很无脑，且$f$和$g$的狄利克雷卷积的前缀和很无脑（太巧了吧。。），那么由
$sum_{i=1}^{n}sum_{d|i}f(d)g(frac{i}{d})$
闪一句，常用套路：设$i=kd$，转而枚举$k$。
$=sum_{k=1}^{n}g(k)sum_{d=1}^{left lfloor frac{n}{k} ight floor}f(d)$
$=sum_{k=1}^{n}g(k)S(frac{n}{k})$
可得
$g(1)S(n)=sum_{i=1}^{n}sum_{d|i}f(d)g(frac{i}{d})-sum_{k=2}^{n}g(k)S(left lfloor frac{n}{k} ight floor)$
进而递推求S。
官方复杂度：（假如构造的卷积的前缀和和g的前缀和都是O(1)可知）由于S那个除法的取值范围：1，2，……，m-1，m，n/m，n/(m-1)，……，n，
可以想到预处理一部分再算一部分，假设预处理了$n^k$，那么总的复杂度就是：$max(n^k,没预处理的那一段)$，
没预处理的那段就是$sum_{i=1}^{n^{1-k}}sqrt{frac{n}{i}}=n^{frac{1}{2}}sum_{i=1}^{n^{1-k}}i^{-frac{1}{2}}approx n^{frac{1}{2}}n^frac{1-k}{2}$
所以总的复杂度就是$max(n^k,n^{frac{1}{2}}n^frac{1-k}{2})$，当$frac{1}{2}+frac{1-k}{2}=k$时取得最小复杂度，$k=frac{2}{3}$.
然而我这里有点不懂：因为没预处理的那段我们是直接递归+记忆化的，那记忆化的那部分复杂度怎么算？如何证明杜教筛过程中出现的数字个数的上限？暂不知。先用着。
好那这道题，我们要找一个前缀和无脑且和$varphi $乘起来无脑的一个函数--1！——就是f(x)=1不知道叫什么——因为有$varphi *1=Id$，$Id(x)=x$。
那就带进去玩一玩：
$sum_{i=1}^{n}sum_{d|i}varphi (d)=sum_{k=1}^{n}1sum_{d=1}^{left lfloor frac{n}{k} ight floor}varphi (d)= sum_{k=1}^{n}S(left lfloor frac{n}{k} ight floor)$
玩够一百下再玩一百下：
$S(n)=sum_{i=1}^{n}sum_{d|i}1*varphi (d)-sum_{k=2}^{n}S(left lfloor frac{n}{k} ight floor)=frac{n(n+1)}{2}-sum_{k=2}^{n}S(left lfloor frac{n}{k} ight floor)$。
OK丢去筛吧。
1 #include<string.h> 2 #include<stdlib.h> 3 #include<stdio.h> 4 #include<math.h> 5 //#include<assert.h> 6 #include<algorithm> 7 //#include<iostream> 8 //#include<bitset> 9 using namespace std; 10 11 #define LL long long 12 LL n,m; 13 #define maxn 5000011 14 const int mod=1e9+7; 15 int phi[maxn],sumphi[maxn],prime[maxn/10],lp; bool notprime[maxn]; 16 void pre(int n) 17 { 18 lp=0; phi[1]=1; sumphi[1]=1; 19 for (int i=2;i<=n;i++) 20 { 21 if (!notprime[i]) {prime[++lp]=i; phi[i]=i-1;} 22 sumphi[i]=sumphi[i-1]+phi[i]; 23 sumphi[i]-=sumphi[i]>=mod?mod:0; 24 for (int j=1,tmp;j<=lp && 1ll*prime[j]*i<=n;j++) 25 { 26 notprime[tmp=i*prime[j]]=1; 27 if (i%prime[j]) phi[tmp]=1ll*phi[i]*(prime[j]-1)%mod; 28 else {phi[tmp]=1ll*phi[i]*prime[j]%mod; break;} 29 } 30 } 31 } 32 33 struct Edge{LL to; int v,next;}; 34 #define maxh 1000007 35 struct Hash 36 { 37 int first[maxh],le;Edge edge[maxn]; 38 Hash() {le=2;} 39 void insert(LL y,int v) 40 {int x=y%maxh; Edge &e=edge[le]; e.to=y; e.v=v; e.next=first[x]; first[x]=le++;} 41 int find(LL y) 42 { 43 int x=y%maxh; 44 for (int i=first[x];i;i=edge[i].next) if (edge[i].to==y) return edge[i].v; 45 return -1; 46 } 47 }h; 48 49 int du(LL n) 50 { 51 if (n<=m) return sumphi[n]; 52 int tmp=h.find(n); if (tmp!=-1) return tmp; 53 LL tot=0; 54 for (LL i=2,last;i<=n;i=last+1) 55 { 56 last=n/(n/i); 57 tot+=(last-i+1)*du(n/i)%mod; 58 tot-=tot>=mod?mod:0; 59 } 60 LL ans=(n%mod)*((n+1)%mod)%mod*((mod+1)>>1)%mod-tot; 61 ans+=ans<0?mod:0; 62 h.insert(n,ans); 63 return ans; 64 } 65 66 int main() 67 { 68 scanf("%lld",&n); 69 m=(LL)pow(pow(n,1.0/3),2); pre(m); 70 printf("%d ",du(n)); 71 return 0; 72 }