#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+7,mod=1e9+7;
ll n,c[N];
int m,sz,s,b[N],p[N],s1[N],s2[N],g1[N],g2[N],id1[N],id2[N];
int gt(ll x) {return x<=m?id1[x]:id2[n/x];}
ll f1(ll x) {x%=mod;return x*(x+1)/2%mod;}
ll f2(ll x) {x%=mod;return x*(x+1)%mod*(x*2+1)%mod*166666668%mod;}
int solve(ll x,int j){
if(p[j]>x) return 0;
//printf("%d %d\n",x,j);
int res=((g2[gt(x)]-g1[gt(x)]-s2[j]+s1[j])%mod+mod)%mod;
for(int i=j+1;i<=sz&&1ll*p[i]*p[i]<=x;i++)
for(ll e=1,ml=p[i];ml<=x;ml*=p[i],e++) (res+=ml%mod*(ml%mod-1)%mod*(solve(x/ml,i)+(e>1))%mod)%=mod;
return res;
}
signed main(){
scanf("%lld",&n);m=sqrt(n);
for(int i=2;i<=m;i++){
if(!b[i]) p[++sz]=i;
for(int j=1;i*p[j]<=m&&j<=sz;j++){
b[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
for(int i=1;i<=sz;i++) s1[i]=(s1[i-1]+p[i])%mod,s2[i]=(s2[i-1]+1ll*p[i]*p[i]%mod)%mod;
for(ll l=1,r;l<=n;l=r+1){
r=n/(c[++s]=n/l);
g1[s]=f1(c[s])-1;g2[s]=f2(c[s])-1;
if(c[s]<=m) id1[c[s]]=s;else id2[n/c[s]]=s;
}
for(int i=1;i<=sz;i++)
for(int j=1;j<=s&&p[i]*p[i]<=c[j];j++){
g1[j]=(g1[j]-1ll*p[i]*(g1[gt(c[j]/p[i])]-s1[i-1])%mod+mod)%mod;
g2[j]=(g2[j]-1ll*p[i]*p[i]%mod*(g2[gt(c[j]/p[i])]-s2[i-1])%mod+mod)%mod;
}
printf("%d\n",(solve(n,0)+1)%mod);
return 0;
}
最后三个点都挂掉了
然后 #define int long long 就过了
大概是哪爆 int 了,不过我目光短浅没有看见……
谁能看看啊