fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int Mod=(int)1e9+7;
  27.  
  28. int n,m;
  29. //\sum_{d|n} phi(d) = n
  30. //对于任意一个元素，必然可以生成一个子群C_d，为n中mod d == 0的数的集合
  31. //对于一个子群，其生成元个数为phi(d)
  32. //而总数为n
  33. //得证
  34.  
  35. //g(n)=\sum_{d|n} phi(d)
  36. //G(n) = \sum_{i<=n} g(i) = \sum_{i<=n} \sum_{d|i} phi(d)
  37. //G(n) = \sum_{d<=n} \sum_{j<=n/d} phi(d)
  38. //在phi(d) 统计n/d次
  39. //G(n) = \sum_{j<=n} \sum_{d<=n/j} phi(d)
  40. //G(n) = \sum_{j<=n} S_{n/j}
  41. //so calc(n)=G(n)-\sum_{j<=n} S_{n/j}
  42. //and g(n)=n, G(n) = n*(n-1)/2
  43.  
  44. /*
  45.    以及对于squre-free number n
  46.  
  47.    phi(nk)=\sum_{d|(n,k)} phi(n/d) phi(k)
  48.    这个的证明：令g=(n,k)，则phi(nk)=phi(k) g phi(n)/phi(g)
  49.    g*phi(n)/phi(g) \sum_{d|g} phi(n)/phi(g/d) 得证
  50.  
  51.    calc(n,m)=\sum_{j<=m} phi(nj)=\sum phi(j) \sum_{d|(j,n)} phi(n/d)
  52.    =\sum_{d<=n} phi(n/d) \sum_{j<=m/d} phi(dj)
  53.    =\sum_{d<=n,d|n} phi(n/d) calc(d, m/d)
  54.  
  55.    若miu(n)==0
  56.    设miu(k)!=0,k|n，calc(n,m)=\frac{n}{k}calc(k,m)
  57.    */
  58.  
  59. const int MAX=1000000+10;
  60.  
  61. int prime[MAX],phi[MAX],K[MAX],mm[MAX];
  62. int q[MAX],top;
  63. vector<int> yueshu[MAX];
  64. map<int,int> S[MAX/10];
  65.  
  66. void update(int& a,int b)
  67. {
  68.     a+=b;
  69.     if(a>=Mod)
  70.         a-=Mod;
  71. }
  72.  
  73. LL calc(int n,int m)
  74. {
  75.     int t=K[n];
  76.     if(m==0)
  77.         return 0;
  78.     if(t!=n && n!=1)
  79.         return (n/t) * calc(t,m) % Mod;
  80.     if(S[n].find(m)!=S[n].end())
  81.         return S[n][m];
  82.     int& ans=S[n][m];
  83.     if(n==1)
  84.     {
  85.         int now=m,next,t;
  86.         for(;now>=2;now=next)
  87.         {
  88.             t=m/now;
  89.             next=m/(t+1);
  90.             update(ans,(now-next) * calc(1,t) % Mod);
  91.         }
  92.         return ans=( (LL)m*(m+1)/2-ans + Mod ) % Mod;
  93.     }
  94.     int i;
  95.     REP2(i,0,(int)yueshu[n].size())
  96.     {
  97.         int d=yueshu[n][i];
  98.         update(ans,phi[n/d] * calc(d,m/d)% Mod);
  99.     }
  100.     return ans;
  101. }
  102.  
  103. int main()
  104. {
  105. #ifndef ONLINE_JUDGE
  106.     freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  107. #endif
  108.     int i;
  109.     scanf("%d%d",&n,&m);
  110.     mm[1]=phi[1]=K[1]=1;
  111.     for(i=2;i<MAX;++i)
  112.     {
  113.         if(!mm[i])
  114.         {
  115.             mm[i]=i;
  116.             phi[i]=i-1;
  117.             K[i]=i;
  118.             q[++top]=i;
  119.         }
  120.         for(int j=1;j<=top && q[j]*i<MAX;++j)
  121.         {
  122.             int u=q[j]*i;
  123.             mm[u]=q[j];
  124.             phi[u]=phi[i];
  125.             K[u]=K[i];
  126.             if(i%q[j]==0)
  127.             {
  128.                 phi[u]*=q[j];
  129.                 break;
  130.             }
  131.             phi[u]*=(q[j]-1);
  132.             K[u]*=q[j];
  133.         }
  134.     }
  135.     for(i=1;i<=n;++i)
  136.         for(int j=i;j<=n;j+=i)
  137.             yueshu[j].pb(i);
  138.  
  139.     int now=0;
  140.     for(i=1;i<MAX;++i)
  141.     {
  142.         update(now,phi[i]);
  143.         S[1][i]=now;
  144.     }
  145.  
  146.     int ans=0;
  147.     REP(i,1,n)
  148.         update(ans,calc(i,m));
  149.     printf("%d\n",ans);
  150.     return 0;
  151. }
  152.  
Success #stdin #stdout 3.14s 40104KB
comments (?)
stdin
copy 
100000 1000000000
stdout
copy 
857275582
https://ideone.com/NbfRqZ
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!