51nod 1238 最小公倍数之和 V3

传送门

一个杜教筛的简单题。

这里没开LL那里没模，de了好久。。

127872

5036446814

//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<queue>
#include<ctime>
#include<cmath>
const int N=1e7+7,mod=1000000007;
typedef long long LL;
using namespace std;
LL nn,up=1000000,inv2,inv4,inv6,ha[N]; 

template<typename T> void read(T &x) {
    char ch=getchar(); x=0; T f=1;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}

LL ksm(LL a,LL b) {
    LL base=a,res=1;
    while(b) {
        if(b&1) res=res*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return res;
}

int bo[N],p[N],s[N],phi[N];
void pre(LL n) {
    phi[1]=1;
    inv2=ksm(2,mod-2);    
    inv4=ksm(4,mod-2);
    inv6=ksm(6,mod-2);
    for(int i=2;i<=up;i++) {
        if(!bo[i]) { p[++p[0]]=i; phi[i]=i-1; }
        for(int j=1;j<=p[0]&&p[j]*i<=up;j++) {
            bo[i*p[j]]=1;
            if(i%p[j]==0) {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
    for(int i=1;i<=up;i++) 
        s[i]=(s[i-1]+(LL)i*i%mod*phi[i]%mod)%mod;
} 

LL n_3(LL n) {
    if(n>=mod) n%=mod;
    return n*(n+1)%mod*n%mod*(n+1)%mod*inv4%mod; 
}

LL n_2(LL n) {
    if(n>=mod) n%=mod;
    return n*(n+1)%mod*((2LL*n%mod+1)%mod)%mod*inv6%mod;
}

LL n_1(LL n) {
    if(n>=mod) n%=mod; 
    return n*(n+1)%mod*inv2%mod;
} 

LL S(LL n) {
    if(n<=up) return s[n];
    if(ha[nn/n]) return ha[nn/n];
    LL res=n_3(n),sum=0;
    for(LL i=2;i<=n;) {
        LL r=(n/(n/i));
        sum=(sum+(n_2(r)-n_2(i-1)+mod)%mod*S(n/i)%mod)%mod;
        i=r+1;
    }
    ha[nn/n]=(res-sum+mod)%mod;
    return ha[nn/n];
}

int main() {
    read(nn);
    pre(nn);
    LL ans=0,n=nn;
    for(LL i=1;i<=n;) {
        LL ss=S(n/i);
        LL l=i,r=(n/(n/i));
        ans=(ans+(n_1(r)-n_1(l-1)+mod)%mod*ss%mod)%mod; 
        i=r+1;
    }    
    printf("%lld
",ans);
    return 0;
}