作者:
呼呼喵
,
2023-04-28 16:50:46
,
所有人可见
,
阅读 19
#include <iostream>
#include <cstring>
using namespace std;
using i64 = long long;
const int N = 50010;
int n, m, primes[N], cnt;
bool st[N];
i64 mu[N], f[N];
void init(int n = 50000) {
mu[1] = 1;
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[cnt++] = i, mu[i] = -1;
for (int j = 0; j < cnt && primes[j] * i <= n; j++) {
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
mu[i * primes[j]] = -mu[i];
}
}
for (int i = 1; i <= n; i++) mu[i] += mu[i - 1];
for (int i = 1; i <= 50000; i++) {
for (int l = 1, r; l <= i; l = r + 1) {
r = i / (i / l);
f[i] += 1ll * (r - l + 1) * (i / l);
}
}
}
i64 calc(int n, int m) {
i64 res = 0;
if (n > m) swap(n, m);
for (int l = 1, r; l <= n; l = r + 1) {
r = min(n / (n / l), m / (m / l));
res += (mu[r] - mu[l - 1]) * f[n / l] * f[m / l];
}
return res;
}
int main() {
init(50000);
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
cout << calc(n, m) << '\n';
}
return 0;
}