题目大意
求约数个数和
solution
我们知道有这么一个公式: (d(nm) = sumlimits_{i | n}sumlimits_{j | m}[gcd(i, j) == 1])
证明: 对于 (nm) 的每个质因数 (p), 设 (n = n_1 * p^a, m = m_1 * p^b), 那么 (nm = n_1 * m_1 * p^{a + b}), p 对 d(nm) 的贡献是 (a+b+1).在等式的右边里,((i_1 * p^a, j_1), (i _ 1 * p^{a - 1}, j_1), ..., (i_1, j_1), ..., (i_1, j_1 * p^b)) 都是可行的数对, 共 (a + b + 1) 个, 证毕.
那么:
(sumlimits_{i = 1}^Nsumlimits_{j = 1}^M d(i, j))
标准的展开:
$= sumlimits_{i = 1}^N sumlimits_{j = 1}^{M} sumlimits_{k | i} sumlimits_{l | j} [gcd(k, l) == 1] $
$=sumlimits_{i = 1}^N sumlimits_{j = 1}^Msumlimits_{d = 1}^{min(N, M)}mu(d)sumlimits_{k|i}sumlimits_{l|j}[gcd(k, l)|d] $
交换枚举顺序:
(=sumlimits_{d = 1}^{min(N, M)}mu(d)sumlimits_{k|i}sumlimits_{l|j}[gcd(k, l)|d] leftlfloorfrac{N}{k} ight floorleftlfloorfrac{M}{l} ight floor)
$=sumlimits_{d = 1}^{min(N, M)}mu(d)sumlimits_{k}^{leftlfloorfrac{N}{k} ight floor}sumlimits_{l}^{leftlfloorfrac{M}{l} ight floor}leftlfloorfrac{N}{dk} ight floorleftlfloorfrac{M}{dl} ight floor $
交换枚举顺序:
$=sumlimits_{d = 1}^{min(N, M)}mu(d)sumlimits_{k}^{leftlfloorfrac{N}{k} ight floor}leftlfloorfrac{N}{dk} ight floorsumlimits_{l}^{leftlfloorfrac{M}{l} ight floor}leftlfloorfrac{M}{dl} ight floor $
记 (f(i) = sumlimits_{j = 1}^i leftlfloorfrac{i}{j} ight floor), 则我们要求 $=sumlimits_{i = 1}^{min(N, M)}mu(i) * f(leftlfloorfrac{N}{i} ight floor) * f(leftlfloorfrac{M}{i} ight floor) $
然后用一下数论分块我们这道题就做完了
Code:
/**
* Author: Alieme
* Data:
* Problem:
* Time: O()
*/
#include <cstdio>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#define int long long
#define rr register
#define inf 1e9
#define MAXN 100010
using namespace std;
inline int read() {
int s = 0, f = 0;
char ch = getchar();
while (!isdigit(ch)) f |= ch == '-', ch = getchar();
while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
void print(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar(x % 10 + 48);
}
int T, n, m, ans, tot;
int mu[MAXN], d[MAXN], c[MAXN], prime[MAXN];
bool vis[MAXN];
inline void init() {
mu[1] = d[1] = c[1] = 1;
for (rr int i = 2; i <= 50000; i++) {
if (!vis[i]) prime[++tot] = i, mu[i] = -1, c[i] = 1, d[i] = 2;
for (int j = 1; j <= tot; j++) {
if (i * prime[j] > 50000) break;
vis[i * prime[j]] = 1;
mu[i * prime[j]] = -mu[i];
d[i * prime[j]] = d[i] * d[prime[j]];
c[i * prime[j]] = 1;
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
d[i * prime[j]] = d[i] / (c[i] + 1) * (c[i] + 2);
c[i * prime[j]] = c[i] + 1;
break;
}
}
}
for (rr int i = 1; i <= 50000; i++) mu[i] += mu[i - 1];
for (rr int i = 1; i <= 50000; i++) d[i] += d[i - 1];
}
signed main() {
init();
T = read();
while (T--) {
n = read();
m = read();
ans = 0;
for (rr int l = 1, r; l <= min(n, m); l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += (mu[r] - mu[l - 1]) * d[n / l] * d[m / l];
}
print(ans);
puts("");
}
}