1005GuGuFishtion

数论题,预处理+容斥

后面的部分可以用容斥做,令

F [ k ] = <munderover> ∑ i = 1 i = M </munderover> <munderover> ∑ j = 1 j = N </munderover> [ g c d ( i , j ) = k ]

F [ k ] = ( M / k ) ∗ ( N / k ) − F [ 2 ∗ k ] − F [ 3 ∗ k ] − . . . . 
倒着求F[K] 即可,复杂度O(nlog(n))
for(int i = N; i; --i){
        F[i] = 1ll*(N/i)*(M/i);
        // if(i == 1) cout<<F[i]<<endl;
        for(int j = i+i;j <= N; j += i)
             F[i] -= F[j];
    }


#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define pb push_back
#define FI first
#define SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
// const LL mod = 1e9 + 7;
// LL qpow(LL a,LL b,LL mod){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
// typedef pair<int,int> p;

const int maxn = 1e6+1000;
LL F[maxn],phi[maxn], inv[maxn];
LL  N,M,P;
void init(int n){
    for(int i = 1;i <= n; ++i) phi[i] = i;
    for(int i = 2;i <= n; ++i){
        if(i == phi[i]){
           for(int j = i; j <= n; j += i) phi[j] = phi[j]/i*(i-1);
        }
    }
}
void init2(void){
    inv[1] = 1;
    for(int i = 2;i <= N; ++i)
        inv[i] = (P - P/i*inv[P%i]%P)%P;
    for(int i = N; i; --i){
        F[i] = 1ll*(N/i)*(M/i);
        // if(i == 1) cout<<F[i]<<endl;
        for(int j = i+i;j <= N; j += i)
             F[i] -= F[j];
    }
    //cout<<F[1]<<endl;
    // DEBUG
   /* for(int i = 1;i <= N; ++i) cout<<F[i]<<" "; cout<<endl; int FF[100]; me(FF); for(int i = 1;i <= N; ++i) for(int j = 1;j <= M; ++j) FF[gcd(i,j)]++; for(int i = 1;i <= N; ++i) cout<<FF[i]<<" "; cout<<endl;*/
}
LL solve(){
    init2();
    LL ans = 0;
    for(LL i = 1;i <= N; ++i){
          ans += (LL)i*inv[phi[i]]%P*(F[i]%P)%P;
          assert(ans >= 0);
          ans %= P;
    }
    // LL ans2 = 0;
/* DEBUG for(int i = 1;i <= N; ++i){ for(int j = 1;j <= M; ++j) ans2 += gcd(i,j)*inv[phi[gcd(i,j)]]%P; } ans2 %= P; if(ans2 != ans) { cout<<"ERROR"<<" "<<N<<" "<<M<<" "<<P<<endl; cout<<ans<<" "<<ans2<<endl; }*/
    return ans%P;
}
// #define Debug
int main(void)
{
    #ifdef Debug
    freopen("input.txt","r",stdin);
    freopen("output1.txt","w+",stdout);
    #endif
    init(maxn-1);
    int T;
    cin>>T;
    while(T--){
        cin>>N>>M>>P;
        if( N < M) swap(N,M);
        cout<<solve()<<endl;
    }


   return 0;
}