C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 4744K, 提交时间: 2020-09-09 09:14:29

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7,N=5e5+5;
ll n;
vector<ll>v;
ll ans[N];
ll tot,p[N],phi[N];
void init()
{
    phi[1]=1;
    for(ll i=2;i<N;i++)
    {
        if(!phi[i]) phi[i]=i-1,p[++tot]=i;
        for(ll j=1;j<=tot&&i*p[j]<N;j++)
        {
            if(i%p[j]==0)
            {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            phi[i*p[j]]=phi[i]*phi[p[j]];
        }
    }
}
map<ll,ll>mp;
ll Phi(ll x)
{
    if(x<N) return phi[x];
    if(mp[x]) return mp[x];
    ll ans=x,y=x;
    for(ll i=2;i*i<=x;i++)
        if(x%i==0)
        {
            ans-=ans/i;
            while(x%i==0) x/=i;
        }
    if(x>1) ans-=ans/x;
    return mp[y]=ans;
}
ll sol(ll n,ll d)
{
    assert(n%d==0);
    return 1ll*Phi(d)*(n/d)%mod;
}
ll solve(ll d)
{
    ll ans=0;
    ans=0;
    for(ll x:v)
        if(d%x==0)
        ans=(ans+sol(n/x,d/x)*(n/(d/x)))%mod;
    return ans;
}
int main()
{
    init();
    ll t;scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        v.clear();
        for(ll i=1;i*i<=n;i++)
            if(n%i==0)
        {
            v.push_back(i);
            if(i!=n/i) v.push_back(n/i);
        }
        sort(v.begin(),v.end());
        ll res=0;
        for(ll i=v.size()-1;i>=0;i--)
        {
            ans[i]=solve(v[i]);
            for(ll j=i+1;j<v.size();j++)
                if(v[j]%v[i]==0)
                 ans[i]=(ans[i]-ans[j])%mod;
            res=(res+ans[i]*v[i])%mod;
        }
        res=(res+mod)%mod;
        printf("%lld\n",res);
    }
}