C++ 解法, 执行用时: 748ms, 内存消耗: 7060K, 提交时间: 2022-01-20 18:10:11

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,mod=1e9+7;
bool v[N];
ll primes[N],sp1[N],sp2[N],id1[N],id2[N],w[N],sq;
ll g1[N],g2[N],n;
ll cnt,tot;
void init()
{
	for(int i=2;i<=sq;i++)
	{
		if(!v[i])
		{
			v[i]=true;
			primes[++cnt]=i;
			sp1[cnt]=(sp1[cnt-1]+i)%mod;
			sp2[cnt]=(sp2[cnt-1]+1ll*i*i%mod)%mod;
		}
		for(int j=1;i*primes[j]<=sq;j++)
		{
			v[i*primes[j]]=true;
			if(i%primes[j]==0) break;
		}
	}
}
ll power(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
ll inv2=power(2,mod-2),inv6=power(6,mod-2);
ll g(ll n,ll x)
{
	return n/(n/x);
}
ll S(ll i,ll j)
{
	if(primes[j]>=i) return 0;
	ll p= i<=sq?id1[i]:id2[n/i];
	ll ans=((g2[p]-g1[p]+mod)%mod-(sp2[j]-sp1[j]+mod)%mod+mod)%mod;
	for(int k=j+1;1ll*primes[k]*primes[k]<=i&&k<=cnt;k++)
	{
		ll pe=primes[k];
		for(int e=1;pe<=i;++e,pe=pe*primes[k])
		{
			ll x=pe%mod;
			ans=(ans+x*(x-1)%mod*(S(i/pe,k)+(e!=1)%mod))%mod;
		}
	}
	return ans;
}
int main()
{
	cin>>n;
	sq=sqrt(n);
	init();
	for(ll l=1,r;l<=n;l=r+1)
	{
		r=min(n,g(n,l));
		w[++tot]=n/l%mod;
		g1[tot]=(w[tot]*(w[tot]+1)%mod*inv2%mod-1+mod)%mod;
		g2[tot]=((w[tot]*(w[tot]+1)%mod)*(2*w[tot]+1)%mod*inv6%mod-1 +mod)%mod;
		w[tot]=n/l;
		if(w[tot]<=sq) id1[w[tot]]=tot;
		else id2[n/w[tot]]=tot;
	}
	for(int j=1;j<=cnt;j++)//g(n,j)
	{
		for(int i=1;i<=tot&&primes[j]*primes[j]<=w[i];i++)
		{
			ll tmp=w[i]/primes[j];
			ll p=tmp<=sq?id1[tmp]:id2[n/tmp];
			g1[i]=(g1[i]-primes[j]*(g1[p]-sp1[j-1]+mod)%mod+mod)%mod;
			g2[i]=(g2[i]-primes[j]*primes[j]%mod*(g2[p]-sp2[j-1]+mod)%mod+mod)%mod;
		}
	}
	cout<<(ll)S(n,0)+1<<endl;
	return 0;
} 

C++(g++ 7.5.0) 解法, 执行用时: 768ms, 内存消耗: 4440K, 提交时间: 2022-09-09 16:04:53

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=100009;
const int M=1000000007,i2=(M+1)/2,i6=(M+1)/6;

LL n;
int m;

int id1[N],id2[N],cnt;
LL v[2*N+1];
int g1[2*N+1],g2[2*N+1];
int getid(LL u){
    if(u<N)return id1[u];else return id2[n/u];
}

int pri[N],tot;
bool ntp[N];

LL f(LL pa){return pa%M*((pa-1+M)%M)%M;}

int S(LL t,int j){
    if(pri[j]>=t)return 0;
    int u=getid(t),v=getid(pri[j]);
    int res=(LL(g2[u])-g1[u]-g2[v]+g1[v]+M+M)%M;
    for(int k=j+1;k<=tot&&LL(pri[k])*pri[k]<=t;++k){
        for(LL pa=pri[k];pa*pri[k]<=t;pa*=pri[k]){
            res=(res+f(pa)*S(t/pa,k)+f(pa*pri[k]))%M;
        }
    }
    return res;
}

signed main(){
    scanf("%lld",&n);m=sqrt(n)+1;

    pri[0]=1;
    for(int i=2;i<=m;++i){
        if(!ntp[i])pri[++tot]=i;
        for(int j=1;j<=tot;++j){
            int nex=pri[j]*i;if(nex>m)break;
            ntp[nex]=1;
            if(i%pri[j]==0)break;
        }
    }

    for(LL i=1,j;i<=n;i=j+1){
        LL t=n/i;j=n/t;
        v[++cnt]=t;
        if(t<N)id1[t]=cnt;else id2[j]=cnt;
        g1[cnt]=(t+2)%M*((t-1)%M)%M*i2%M;
        g2[cnt]=(t%M)*((t+1)%M)%M*((2*t+1)%M)%M*i6%M-1;
        if(g2[cnt]<0)g2[cnt]+=M;
    }

    for(int j=1;j<=tot;++j){
        const LL pj=pri[j],lim=pj*pj;
        const int pre=getid(pri[j-1]);
        for(int i=1;i<=cnt&&lim<=v[i];++i){
            const int now=getid(v[i]/pj);
            g1[i]=(g1[i]-pj*(g1[now]-g1[pre]+M)%M+M)%M;
            g2[i]=(g2[i]-pj*pj%M*(g2[now]-g2[pre]+M)%M+M)%M;
        }
    }

    printf("%d\n",(S(n,0)+1)%M);
    return 0;
}