题解

#include <iostream>
#include <vector>
using namespace std;

typedef long long LL;
const int MAXN = 1e5 + 9;
const LL P = 998244353;
const int B = 35;

int mu[MAXN], phi[MAXN], prime[MAXN];
bool visit[MAXN];
int inv[MAXN], F[MAXN];
int* G[MAXN];
int* S[B + 1][B + 1];

inline int Read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x * f;
}

inline void Init(int N) {
    mu[1] = phi[1] = inv[1] = 1;
    int tot = 0;
    for (int i = 2; i <= N; ++i) {
        if (!visit[i]) {
            prime[++tot] = i;
            mu[i] = -1;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= tot && i * prime[j] <= N; ++j) {
            visit[i * prime[j]] = true;
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            } else {
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
                mu[i * prime[j]] = -mu[i];
            }
        }
    }
    for (int i = 2; i <= N; ++i)
        inv[i] = P - 1LL * P / i * inv[P % i] % P;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j * i <= N; ++j)
            F[i * j] = (F[i * j] + 1LL * i * inv[phi[i]] % P * mu[j] % P) % P;

    for (int i = 1; i <= N; ++i) {
        G[i] = new int[N / i + 1];
        G[i][0] = 0;
        for (int j = 1; j <= N / i; ++j)
            G[i][j] = (G[i][j - 1] + 1LL * phi[j * i]) % P;
    }

    for (int j = 1; j <= B; ++j)
        for (int k = 1; k <= B; ++k) {
            int len = N / max(j, k);
            S[j][k] = new int[len + 1];
            S[j][k][0] = 0;
            for (int i = 1; i <= len; ++i)
                S[j][k][i] = (S[j][k][i - 1] + 1LL * F[i] * G[i][j] % P * G[i][k] % P) % P;
        }
}

inline LL Solve(int n, int m) {
    if (n > m) swap(n, m);
    LL ans = 0;
    for (int i = 1; i <= m / B; ++i)
        ans = (ans + 1LL * F[i] * G[i][n / i] % P * G[i][m / i] % P) % P;
    for (int l = m / B + 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        ans = (ans + 1LL * (S[n / l][m / l][r] - S[n / l][m / l][l - 1] + P) % P) % P;
    }
    return ans;
}

int main() {
    int T = Read();
    Init(100000);
    while (T--) {
        int n = Read(), m = Read();
        printf("%lld\n", Solve(n, m));
    }
    return 0;
}