题目描述

有$T$组询问,每次给定整数$a,b,d$,求有多少对正整数$x,y$,满足$x \le a \wedge y \le b \wedge (x,y)=d$

$1 \le a,b,d,T \le 50000$

题解

$$
\begin{aligned}
a \le b \\
\sum_{i=1}^{a}\sum_{j=1}^{b}[(i,j)=d]
&=\sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}[(i,j)=1] \\
&=\sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}\sum_{d’ \mid (i,j)}\mu(d’) \\
&=\sum_{i=1}^{\lfloor \frac{a}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{b}{d} \rfloor}\sum_{d’ \mid i \wedge d’ \mid j}\mu(d’) \\
&=\sum_{d’=1}^{\lfloor \frac{a}{d} \rfloor}\mu(d’)\sum_{d’ \mid i}^{\lfloor \frac{a}{d} \rfloor}\sum_{d’ \mid j}^{\lfloor \frac{b}{d} \rfloor}1 \\
&=\sum_{d’=1}^{\lfloor \frac{a}{d} \rfloor}\mu(d’) \lfloor \frac{a}{dd’} \rfloor \lfloor \frac{b}{dd’} \rfloor
\end{aligned}
$$

$\lfloor \frac{a}{dd’} \rfloor \lfloor \frac{b}{dd’} \rfloor$的取值只有$O(\sqrt a + \sqrt b)$种,预处理$\mu$的前缀和,单次询问可以$O(\sqrt n)$计算

代码

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
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 50000 + 10;

int n, m, d, mu[N], vis[N], p[N], tot;

void sol() {
ll ans = 0;
scanf("%d%d%d", &n, &m, &d); if(n > m) swap(n, m);
n /= d, m /= d;
for(int i = 1, j ; i <= n ; i = j + 1) {
j = min(n / (n / i), m / (m / i));
ans += (ll) (mu[j] - mu[i - 1]) * (n / i) * (m / i);
}
printf("%lld\n", ans);
}

int main() {
mu[1] = 1;
for(int i = 2 ; i <= 50000 ; ++ i) {
if(!vis[i]) mu[i] = -1, p[++ tot] = i;
for(int j = 1 ; j <= tot && (ll) i * p[j] <= 50000 ; ++ j) {
vis[i * p[j]] = 1;
if(i % p[j] == 0) break;
mu[i * p[j]] = -mu[i];
}
mu[i] += mu[i - 1];
}
int T; scanf("%d", &T);
while(T --) sol();
}