P3327 [SDOI2015]约数个数和
如果 $x | i \wedge y | j$ ，那么一定有 $xy |ij$ ， 即 $xy$ 是 $ij$ 的约数，对答案有贡献。但是如果直接这样计算可能会出现重复的，如 $4 \times 6 = 24$ ，$3 \times 8 = 24$ ，所以我们要求 $x \bot y$ 时才计算答案，因此 $d(i j) = \displaystyle \sum_{x |i} \sum _{y | j} [gcd(x, y) = 1]$ 。
答案为：
$$
\begin {aligned}
\sum _ {i = 1} ^ n \sum _ {j = 1} ^ m d(i j) = & \sum _ {i = 1} ^ N \sum _ {j = 1} ^ M \sum _ {x | i} \sum _ {y | i} [gcd(x, y) = 1]\\
= & \sum _ {i = 1} ^ N \sum _ {j = 1} ^ M \sum _ {d = 1} ^{min(N, M)} \mu (d) \sum _ {x | i \wedge x | d} \sum_{y | i \wedge y | d} \\
= &\sum _ {d = 1} ^ {min(N, M)} \mu(d) \sum _ {i = 1} ^ {\frac M d} \left \lfloor \frac M {di} \right \rfloor \sum _ {i = 1} ^{\frac N d}\left \lfloor \frac N {j d} \right \rfloor
\end {aligned}
$$
记 $h(x) = \displaystyle \sum_{i = 1} ^ x \left \lfloor \frac x i \right \rfloor$ ，则答案为：
$$
\sum_{i = 1} ^ n \sum_{j = 1} ^ m d(i j) = \sum_{d = 1} ^ {min(N, M)} \mu(d) h(\frac N d) h (\frac M d)
$$
其中 $h _ i$ 可以用数论分块预处理，最终计算答案的时候可以用数论分块计算。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e4 + 10;
int n, m;
LL h[N];
bool vis[N];
int cnt, primes[N], mu[N], s[N];
void init()
{
mu[1] = 1;
for (int i = 2; i < N; i++)
{
if (!vis[i])
{
primes[++cnt] = i;
mu[i] = -1;
}
for (int j = 1; j <= cnt && i * primes[j] < N; j++)
{
vis[i * primes[j]] = true;
if (i % primes[j] == 0)
{
mu[i * primes[j]] = 0;
break;
}
mu[i * primes[j]] = -mu[i];
}
}
for (int i = 1; i < N; i++)
s[i] = s[i - 1] + mu[i];
for (int i = 1; i < N; i++)
for (int l = 1, r; l <= i; l = r + 1)
{
r = i / (i / l);
h[i] += (r - l + 1) * (i / l);
}
}
int main()
{
init();
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &m);
LL res = 0;
for (int l = 1, r; l <= min(n, m); l = r + 1)
{
r = min(n / (n / l), m / (m / l));
res += (s[r] - s[l - 1]) * h[n / l] * h[m / l];
}
printf("%lld\n", res);
}
return 0;
}
|