GuGuFishtion HDU - 6390 [Mobius]

GuGuFishtion HDU - 6390

思路:

• 从原式到第一个等式,神奇操作....... 当作结论用.
• 爆int了.难受

当然可以再优化复杂度到

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+6;
ll MOD=1e9+7;

ll inv[N];
ll init(){
    inv[1] = 1;
    for(ll i = 2; i < N; i ++){
        inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
    }
}

ll phi[N];
void Euler(){
    phi[1] = 1;
    for(ll i = 2; i < N; i ++){
        if(!phi[i]){
            for(ll j = i; j < N; j += i){
                if(!phi[j]) phi[j] = j;
                phi[j] = phi[j] / i * (i-1);
            }
        }
    }
}

ll mu[N], vis[N], prime[N];
ll tot;//用来记录prime的个数
ll sum[N];
void init1(){
    mu[1] = 1;
    for(ll i = 2; i < N; i ++){
        if(!vis[i]){
            prime[tot ++] = i;
            mu[i] = -1;
        }
        for(ll j = 0; j < tot && i * prime[j] < N; j ++){
            vis[i * prime[j]] = 1;
            if(i % prime[j]) mu[i * prime[j]] = -mu[i];
            else{
                mu[i * prime[j]] = 0;
                break;
            }
        }
    }
    for(ll i=1;i<=N-1;i++) sum[i]=sum[i-1]+mu[i],sum[i]%=MOD;
}

ll work(int m,int n,int d){
    n/=d,m/=d;
    ll ans=0;
    
    int mn=min(n,m);
    for(int i=1;i<=mn;i++){
        int ed=min(n/(n/i),m/(m/i));
        ans+=1ll*(sum[ed]-sum[i-1])*(n/i)%MOD*(m/i);
        ans%=MOD;ans+=MOD;ans%=MOD;
        i=ed;
    }
    return ans;
}

int main(void){
    int T;
    Euler();
    init1();
    scanf("%d",&T);
    while(T--){
        int m,n;
        scanf("%d%d%lld",&m,&n,&MOD);
        init();
        ll ans=0;
        int mn=min(n,m);
        for(int d=1;d<=mn;d++){
            ans+=1ll*d*inv[phi[d]]%MOD*work(m,n,d);
            ans%=MOD;
        }
        printf("%lld\n",ans);
    }

    return 0;
}