Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- #define ll long long
- template<typename T>
- inline void read(T&x){
- T k=1;char gc;x=0;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c))x=x*10+c-'0',gc;x*=k;
- }
- const int p=1e9+7;
- const int N=3e6+7;
- inline int add(int a,int b){
- return (a+=b)>=p?a-p:a;
- }
- inline int sub(int a,int b){
- return (a-=b)<0?a+p:a;
- }
- inline ll sqr(ll x){
- return x*x%p;
- }
- inline int calc(int n){
- int ans=0;
- for(int i=1,j;i<=n;i=j+1){
- j=n/(n/i);
- ans=add(ans,(ll)(j-i+1)*(n/i)%p);
- }
- return ans;
- }
- int tot;
- int mu[N];
- int pri[N];
- bool mark[N];
- inline void pre(int n){
- mu[1]=1;
- for(int i=2;i<=n;++i){
- if(!mark[i])pri[++tot]=i,mu[i]=-1;
- for(int j=1,tmp;j<=tot&&(tmp=i*pri[j])<=n;++j){
- mark[tmp]=1;
- if(i%pri[j]==0){
- mu[tmp]=0;
- break;
- }
- mu[tmp]=-mu[i];
- }
- }
- for(int i=1;i<=n;++i){
- mu[i]+=mu[i-1];
- }
- for(int i=1;i<=n;++i){
- mu[i]=sub(mu[i],0);
- }
- }
- map<int,int>f;
- inline int Sum(int n){
- if(n<N)return mu[n];
- if(f.count(n))return f[n];
- int ans=1;
- for(int i=2,j;i<=n;i=j+1){
- j=n/(n/i);
- ans=sub(ans,(ll)(j-i+1)*Sum(n/i)%p);
- }
- return f[n]=ans;
- }
- int main(){
- freopen("math.in","r",stdin);
- freopen("math.out","w",stdout);
- int n,ans=0;r(n);
- pre(min(N-1,n));
- for(int i=1,j;i<=n;i=j+1){
- j=n/(n/i);
- ans=add(ans,sub(Sum(j),Sum(i-1))*sqr(calc(n/i))%p);
- }
- printf("%d\n",ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement