HDU-6706 huntian oy


图片说明 

#include<bits/stdc++.h>
using namespace std;
const int inv2=500000004;
const int inv6=166666668;
const int mod=1e9+7;
const int N=1e6+5;
typedef long long ll;
int prime[N],tot=0;
ll phi[N];
bool vis[N];
map<int ,ll>p;
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]*phi[prime[j]];
        }
    }
    for(int i=1;i<N;i++)phi[i]=(phi[i]*i%mod+phi[i-1])%mod;
}
ll cal(ll x){return x*(x+1)/2%mod;}
ll fun(int n){
    if(n<N)return phi[n];
    if(p.count(n))return p[n];
    ll ans=1LL*n*(n+1)%mod*(2LL*n+1)%mod*inv6%mod;
    for(int i=2,last;i<=n;i=last+1){
        last=n/(n/i);
        ans-=(cal(last)-cal(i-1)+mod)%mod*fun(n/i)%mod;
        if(ans>=mod||ans<0)ans=(ans+mod)%mod;
    }
    return p[n]=ans;
}
int main(){
    pre();
    int t;cin>>t;
    while(t--){
        int n,a,b;scanf("%d%d%d",&n,&a,&b);
        ll ans=fun(n);
        printf("%lld\n",(ans-1)*inv2%mod);
    }
}