记录编号	571122	评测结果	AAAAAAAAAA
题目名称	[BZOJ 2820] YY的GCD	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	9.530 s
提交时间	2022-05-08 13:59:09	内存使用	129.71 MiB

#include <bits/stdc++.h>
#define OPEN(_x) freopen(#_x".in", "r", stdin); freopen(#_x".out", "w", stdout)
#define rep(_x, _y, _z) for (int _x = (_y); _x <= _z; ++ _x)
#define rep1(_x, _y, _z, _a) for (int _x = (_y); _x <= _z; _x += _a)

namespace IO {
    inline int read() {
        char ch = getchar();
        int ret = 0, sig = 1;
        while(ch < '0' || ch > '9') { if(ch == '-') sig = -1; ch = getchar(); }
        while(ch >= '0' && ch <= '9') ret *= 10, ret += ch - 48, ch = getchar();
        return ret * sig;
    }
};

using IO::read;
using i64 = long long;
const int N = 1e7+10;

int primes[N], mu[N], s[N], cnt, t;
bool st[N];

void get_mu() {
    mu[1] = st[1] = 1;
    rep (i, 2, N) {
        if (!st[i]) primes[++ cnt] = i, mu[i] = -1;
        rep (j, 1, cnt && primes[j] <= N / i) {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) {
                mu[i * primes[j]] = 0;
                break;
            }
            mu[i * primes[j]] = - mu[i];
        }
    }
}

i64 calc(int n, int m) {
    i64 res = 0;
    int l = 1, r;
    while (l <= std::min(n, m)) {
        r = std::min(n / (n / l), m / (m / l));
        res += 1LL * (s[r] - s[l - 1]) * (n / l) * (m / l);
        l = r + 1;
    }
    return res;
}

void init() {
    get_mu();
    rep (i, 1, cnt) 
        rep1(j, primes[i], N, primes[i]) 
            s[j] += mu[j / primes[i]]; 
    rep (i, 2, N) s[i] += s[i - 1];
}

int main() {
    OPEN(YYnoGCD);
    init(); 
    t = read();
    while (t --) {
        int n = read(), m = read();
        printf("%lld\n", calc(n, m));
    }
    return 0;
}