看了看题解，就是第一篇题解的做法。

但是WA（答案全部小了）

#include <bits/stdc++.h>
#define PLI pair<long long , int>
#define fi first
#define se second
#define ll long long
using namespace std;
const int maxq = 5e4 + 100;
const int maxn = 1e5;
const int N = 1e5 + 100;
const ll mod = (1LL << 31);
struct Qs{
    int n, m, a, num;
    friend bool operator < (Qs x, Qs y){return x.a < y.a;}
}qs[maxq];
ll t[N];
ll mu[N], sig[N];
int ex[N], pw[N];
bool vis[N];
PLI si[N];
int pri[N], idx;
void pl(ll &x, ll y){x = (x + y) % mod; }
ll mi(ll x, ll y){return ((x - y) % mod + mod) % mod;}
inline int lowbit(int x){return x & (-x);}
void add(int x, ll k){while(x <= maxn){pl(t[x], k);x += lowbit(x);}}
ll ask(int x){ll ret = 0;while(x){pl(ret, t[x]);x -= lowbit(x);}return ret;}
int Q, l;
void init(){
    mu[1] = sig[1] = 1;
    for(int i = 2;i <= maxn;i++){
        if(!vis[i]){
            pri[++idx] = i;
            mu[i] = -1;
            sig[i] = i + 1;
            ex[i] = 1, pw[i] = i;
        }
        for(int j = 1;j <= idx && pri[j] * i <= maxn;j++){
            int x = pri[j] * i;
            vis[x] = 1;
            if(pri[j] % i){
                ex[x] = 1, pw[x] = i;
                sig[x] = sig[pri[j]] * sig[i];
                mu[x] = -mu[i];
            }
            else{
                ex[x] = ex[i] + 1, pw[x] = pw[i] * pri[j];
                sig[x] = sig[pw[x]] * sig[x / pw[x]];
                mu[x] = 0;
                break;
            }
        }
    }
    for(int i = 1;i <= maxn;i++) si[i] = make_pair(sig[i], i);
    sort(si + 1, si + 1 + maxn);
}
ll ans[maxq];
int main(){
    scanf("%d",&Q);
    for(int i = 1;i <= Q;i++){scanf("%d%d%d",&qs[i].n,&qs[i].m,&qs[i].a);qs[i].num = i;}
    init();
    int id = 0;     
    sort(qs + 1,qs + 1 + Q);
    for(int i = 1;i <= Q;i++){
        while(si[id + 1].fi <= qs[i].a && id < maxn){
            int d = si[++id].se;
            for(int k = 1;k * d <= maxn;k++) add(k * d, sig[d] * mu[k]);
        }
        int n = qs[i].n, m = qs[i].m;
        if(n > m) swap(n, m);
        ll res = 0;
        for(int l = 1, r;l <= n;l = r + 1){
            r = min(n / (n / l), m / (m / l));
            pl(res, 1LL * (n / l) * (m / l) % mod * mi(ask(r) , ask(l - 1)) % mod);
        }
        ans[qs[i].num] = res;
    }
    for(int i = 1;i <= Q;i++) printf("%lld\n",ans[i]);
    return 0;
}