51Nod-1237 最大公约数之和V3(欧拉反演 杜教筛)

51Nod-1237 最大公约数之和 V3

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+6;
const int mod=1e9+7;
const int inv2=mod+1>>1;
typedef long long ll;
int prime[N],phi[N],tot=0;
bool vis[N]={0};
void pre(){
    phi[1]=1;phi[0]=0;
    for(int i=2;i<N;i++){
        if(!vis[i])prime[++tot]=i,phi[i]=i-1;
        for(int j=1;j<=tot&&i*prime[j]<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=1;i<N;i++)phi[i]=(1LL*phi[i]+phi[i-1])%mod;
}
map<ll,int>p;
map<ll,bool>q;
int cal(ll n){
    if(n<N)return phi[n];
    if(q[n])return p[n];
    ll x=n;x%=mod;
    int ans=x*(x+1)%mod*inv2%mod;
    for(ll i=2,last;i<=n;i=last+1){
        last=n/(n/i);
        ans-=(last-i+1)%mod*cal(n/i)%mod;
        ans=(ans+mod)%mod;
    }
    q[n]=true;
    return p[n]=ans;
}
int main(){
    pre();
    ll n;
    scanf("%lld",&n);
    int ans=0;
    for(ll i=1,last;i<=n;i=last+1){
        last=n/(n/i);
        ll x=(n/i)%mod;
        x=x*x%mod;
        ans=(1LL*(cal(last)-cal(i-1)+mod)%mod*x%mod+ans)%mod;
    }
    printf("%d\n",ans);
}