51nod1244 欧拉函数之和 杜教筛

和上一题差不多，一个是μ*I=e，一个是φ*I=Id

稍改就得到了这题的代码

（我会告诉你我一开始逆元算错了吗）

 #include <bits/stdc++.h>

 #define MAX 5000000

 #define MOD 1000000007

 using namespace std;

 long long a,b,N;

 long long phi[MAX+],p[MAX],ans[MAX];

 bool bo[MAX+];

 long long work(long long n)

 {

     if(n<=MAX) return phi[n];

     if(ans[N/n]) return ans[N/n];

     long long ret=n%MOD*(n+)%MOD*%MOD;

     for(long long j=;j<=n;)

     {

         long long nex=n/(n/j);

         ret=(ret-(nex-j+)%MOD*work(n/j)%MOD+MOD)%MOD;

         j=nex+;

     }

     ans[N/n]=ret;

     return ret;

 }

 int main()

 {

     int sum=;phi[]=;

     for(int i=;i<=MAX;i++)

     {

         if(!bo[i])

             p[++sum]=i,phi[i]=i-;

         for(int j=;j<=sum && p[j]*i<=MAX;j++)

         {

             bo[p[j]*i]=;

             phi[i*p[j]]=phi[i]*((i%p[j])?phi[p[j]]:p[j]);

             if(i%p[j]==) break;

         }

     }

     for(int i=;i<=MAX;i++)

         phi[i]=(phi[i]+phi[i-])%MOD;

     scanf("%lld",&a);

     N=a;

     printf("%lld\n",work(a));

     return ;

 }