HDU-4059 The Boss on Mars(反演)

$Description$
$Calculate \quad \sum_{i=1}^{n}i^4 [gcd(i,n)=1]$

$Solution$
$\sum_{i=1}^{n}i^4 [gcd(i,n)=1] \\ =\sum_{d|n}\mu(d)\cdot d^4 \sum_{i=1}^{\frac{n}{d}}i^4$
$\sum_{i=1}^{n}i^4=\frac{n\cdot(n+1)\cdot(2\cdot n+1)\cdot(3\cdot n^2+3\cdot n-1)}{30}$

$Code$

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int inv=233333335;
typedef long long ll;
ll f(ll n){
    ll ans=n*(n+1)%mod*(2LL*n+1)%mod;
    ll x=(3LL*n*n%mod+3LL*n-1)%mod*inv%mod;
    return ans*x%mod;
}
int mu(ll n){
    if(n==1)return 1;
    int cnt=0;
    for(int i=2;1LL*i*i<=n;i++){
        if(n%i==0){
            cnt++;
            n/=i;
            if(n%i==0)return 0;
        }
    }
    if(n>1)cnt++;
    return cnt%2==1?-1:1;
}
ll cal(ll n,ll d){
    ll res=d*d%mod;
    res=res*res%mod;
    ll ans=f(n/d)*res%mod*mu(d);
    ans=(ans+mod)%mod;
    return ans;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        scanf("%d",&n);
        ll ans=0;
        for(int i=1;1LL*i*i<=n;i++){
            if(n%i==0){
                ans+=cal(n,i);
                if(ans>=mod)ans-=ans/mod*mod;
                if(i!=n/i)ans+=cal(n,n/i);            
                if(ans>=mod)ans-=ans/mod*mod;
            }
        }
        printf("%lld\n",ans);
    }    
}