提交时间:2024-02-27 19:55:55

运行 ID: 26967

#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned int uint; const int N = 2e5 + 9, maxN = 2e5, Mod = 1073741824; int _, n, m; uint d[N], d2[N], num[N], mu[N]; vector<int> pri; bitset<N> vis; void init() { d[1] = num[1] = mu[1] = 1; for (int i = 2; i <= 2e5; i++) { if (!vis[i]) { d[i] = 2, num[i] = 1, mu[i] = -1; pri.push_back(i); } for (int j : pri) { if (i * j > 2e5) break; vis[i * j] = 1; if (i % j == 0) { num[i * j] = num[i] + 1, mu[i * j] = 0; d[i * j] = d[i] / num[i * j] * (num[i * j] + 1); break; } d[i * j] = d[i] << 1, num[i * j] = 1, mu[i * j] = -mu[i]; } } } uint D2(uint n) { uint res = 0; for (int i = 1; i * i <= n; i++) { if (n % i) continue; res += mu[i] * d[n / i] * d[n / i]; if (i != n / i) res += mu[n / i] * d[i] * d[i]; } return res; } vector<uint> S[N], Bl[49][49]; signed main() { init(); scanf("%d", &_); for (int i = 1; i <= 2e5; i++) d2[i] = D2(i); for (int p = 1; p <= 2e5; p++) { S[p].push_back(0); for (int i = 1; i <= (int)(2e5) / p; i++) { S[p].push_back(S[p][i - 1] + d2[i * p] * d[i]); } } for (int i = 1; i <= 40; i++) { for (int j = i; j <= 40; j++) { Bl[i][j].push_back(0); for (int p = 1; p <= maxN / j; p++) { Bl[i][j].push_back(Bl[i][j][p - 1] + mu[p] * S[p][i] * S[p][j]); } } } while (_--) { scanf("%d%d", &n, &m); if (n > m) swap(n, m); uint ans = 0; for (int i = 1; i <= min((int)(5e3), n); i++) { ans += mu[i] * S[i][n / i] * S[i][m / i]; } int l = 5e3 + 1, r; while (l <= n) { r = min({n / (n / l), m / (m / l), n}); ans += Bl[n / l][m / l][r] - Bl[n / l][m / l][l - 1]; l = r + 1; } printf("%u\n", ans % Mod); } return 0; }