1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5+10;
const int md = 1e9+7;
ll g[N<<1],id,n,sn,sq,a[N<<1],h[N<<1],sum[N<<1];
int prime[N],cnt;
ll Id(ll x){return x<=sn?x:id-n/x+1;}
ll Solve(ll a,ll b)
{
if(a<prime[b])return 0;
ll ans = (g[Id(a)]-g[prime[b-1]]+md)%md;
for(ll i=b;i<=cnt&&1ll*prime[i]*prime[i]<=a;i++)
{
ans+=1ll*(prime[i]^1)*Solve(a/prime[i],i+1)+(prime[i]^2);
ans%=md;
for(ll x=1ll*prime[i]*prime[i],j=2;x*prime[i]<=a;x*=prime[i],j++)
{
ans+=1ll*(prime[i]^j)*Solve(a/x,i+1)+(prime[i]^(j+1));
}
}
return ans%md;
}
int main(){
scanf("%lld",&n);
sn =sqrt(n);
for(ll i=1;i<=n;i=a[id]+1)
{
a[++id]=n/(n/i);
ll tmp = a[id]%md;
g[id]=tmp*(tmp+1)/2%md-1;
h[id]=a[id]-1;
}
for(ll i=2;i<=sn;i++)if(h[i]!=h[i-1])
{
prime[++cnt]=i;
sq = 1ll*i*i;
for(int j=id;a[j]>=sq;j--)
{
ll t = Id(a[j]/i);
(g[j]-=i*(g[t]-g[i-1]))%=md;
h[j]-=h[t]-(cnt-1);
}
}
for(int i=1;i<=id;i++)(g[i]+=(i>1)*2-h[i]+md)%=md;
printf("%lld",(Solve(n,1)+1)%md);
}
|