Advertisement
yicongli

BZ4176

Apr 3rd, 2019
176
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.38 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     T k=1;char gc;x=0;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c))x=x*10+c-'0',gc;x*=k;
  14. }
  15.  
  16. const int p=1e9+7;
  17. const int N=3e6+7;
  18.  
  19. inline int add(int a,int b){
  20.     return (a+=b)>=p?a-p:a;
  21. }
  22.  
  23. inline int sub(int a,int b){
  24.     return (a-=b)<0?a+p:a;
  25. }
  26.  
  27. inline ll sqr(ll x){
  28.     return x*x%p;
  29. }
  30.  
  31. inline int calc(int n){
  32.     int ans=0;
  33.     for(int i=1,j;i<=n;i=j+1){
  34.         j=n/(n/i);
  35.         ans=add(ans,(ll)(j-i+1)*(n/i)%p);
  36.     }
  37.     return ans;
  38. }
  39.  
  40. int tot;
  41. int mu[N];
  42. int pri[N];
  43. bool mark[N];
  44.  
  45. inline void pre(int n){
  46.     mu[1]=1;
  47.     for(int i=2;i<=n;++i){
  48.         if(!mark[i])pri[++tot]=i,mu[i]=-1;
  49.         for(int j=1,tmp;j<=tot&&(tmp=i*pri[j])<=n;++j){
  50.             mark[tmp]=1;
  51.             if(i%pri[j]==0){
  52.                 mu[tmp]=0;
  53.                 break;
  54.             }
  55.             mu[tmp]=-mu[i];
  56.         }
  57.     }
  58.     for(int i=1;i<=n;++i){
  59.         mu[i]+=mu[i-1];
  60.     }
  61.     for(int i=1;i<=n;++i){
  62.         mu[i]=sub(mu[i],0);
  63.     }
  64. }
  65.  
  66. map<int,int>f;
  67.  
  68. inline int Sum(int n){
  69.     if(n<N)return mu[n];
  70.     if(f.count(n))return f[n];
  71.     int ans=1;
  72.     for(int i=2,j;i<=n;i=j+1){
  73.         j=n/(n/i);
  74.         ans=sub(ans,(ll)(j-i+1)*Sum(n/i)%p);
  75.     }
  76.     return f[n]=ans;
  77. }
  78.  
  79. int main(){
  80.     freopen("math.in","r",stdin);
  81.     freopen("math.out","w",stdout);
  82.     int n,ans=0;r(n);
  83.     pre(min(N-1,n));
  84.     for(int i=1,j;i<=n;i=j+1){
  85.         j=n/(n/i);
  86.         ans=add(ans,sub(Sum(j),Sum(i-1))*sqr(calc(n/i))%p);
  87.     }
  88.     printf("%d\n",ans);
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement