2020百度之星初赛一 Function (莫比乌斯反演)

Function

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
const int inv2=mod+1>>1;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
short mu[N];
bool vis[N];
int cnt=0;
int pri[N]={0};
void pre(){
    mu[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i])mu[i]=-1,pri[++cnt]=i;
        for(int j=1;j<=cnt&&i*pri[j]<N;j++){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0){
                mu[i*pri[j]]=0;
                break;
            }
            else mu[i*pri[j]]=-mu[i];
        }
    }
}
ll f(ll n){
    n%=mod;
    return n*(n+1)%mod*inv2%mod;
}
ll g(ll n){
    ll ans=0;
    for(ll i=1,last;i<=n;i=last+1){
        last=n/(n/i);
        ll x=f(n/i);
        ans+=(last-i+1+mod)*x%mod;
        if(ans>=mod)ans%=mod;
        if(ans<=0)ans=(ans+mod)%mod;
    }
    return ans;
}
int main(){
    pre();
    int t;cin>>t;
    while(t--){
        ll ans=0;
        ll n;sc("%lld",&n);
        for(int i=1;1LL*i*i<=n;i++){
            if(mu[i]){
                ans+=mu[i]*i*g(n/i/i);
                if(ans>=mod)ans%=mod;
                if(ans<=0)ans=(ans+mod)%mod;
            }
        }
        pr("%lld\n",ans);
    }
}