题面

题解

懒了……写得挺好的……

//minamoto#include
    
     #define R register#define ll long long#define IT map
     
      ::iterator#define fp(i,a,b) for(R int i=a,I=b+1;i
      
       I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;const int N=6e6+5,P=1e9+7,inv2=500000004,inv6=166666668;bitset
       
        vis;int p[N],phi[N],g[N],m,sqr;ll n;map
        
         mp;inline int calc(R int x){return (1ll*x*(x+1)>>1)%P;}inline int calc2(R int x){return 1ll*x*(x+1)%P*((x<<1)+1)%P*inv6%P;}inline int calc3(R int x){x=calc(x);return 1ll*x*x%P;}void init(int n){    phi[1]=g[1]=1;    fp(i,2,n){        if(!vis[i])p[++m]=i,phi[i]=i-1,g[i]=1ll*phi[i]*i%P*i%P;        for(R int j=1,k;j<=m&&1ll*i*p[j]<=n;++j){            vis[k=i*p[j]]=1;            if(i%p[j]==0){phi[k]=phi[i]*p[j],g[k]=1ll*phi[k]*k%P*k%P;break;}            phi[k]=phi[i]*(p[j]-1),g[k]=1ll*g[i]*g[p[j]]%P;        }    }    fp(i,2,n)(g[i]+=g[i-1])%=P;}int G(ll n){    if(n<=sqr)return g[n];    IT it=mp.find(n);    if(it!=mp.end())return it->second;    int res=calc3(n%P),las=1,now;    for(ll i=2,j;i<=n;i=j+1)        j=n/(n/i),now=calc2(j%P),res=(res-1ll*(now-las+P)*G(n/i)%P+P)%P,las=now;    return mp[n]=res;}int main(){//  freopen("testdata.in","r",stdin);    scanf("%lld",&n),init(sqr=N-5);    int res=0,las=0,now=0;    for(R ll i=1,j;i<=n;i=j+1)        j=n/(n/i),now=calc(j%P),(res+=1ll*(now-las+P)*G(n/i)%P)%=P,las=now;    printf("%d\n",res);    return 0;}