洛谷P3455 [POI2007][BZOJ1101]ZAP-Queries(莫比乌斯反演 + 分块)

洛谷P3455 [POI2007][BZOJ1101]ZAP-Queries

题目

Description

Byteasar the Cryptographer works on breaking the code of BSA (Byteotian Security Agency). He has alreadyfound out that whilst deciphering a message he will have to answer multiple queries of the form”for givenintegers $a$, $b$ and $d$ , find the number of integer pairs $(x,y)$ satisfying the following conditions:
$1\le x\le a,1\le y\le b,gcd(x,y)=d$, where $gcd(x,y)$ is the greatest common divisor of $x$ and $y$ “.
Byteasar would like to automate his work, so he has asked for your help.
TaskWrite a programme which:
reads from the standard input a list of queries, which the Byteasar has to give answer to, calculates answers to the queries, writes the outcome to the standard output.


FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数 $a$, $b$ 和 $d$ ,有多少正整数对 $x$ , $y$ ,满足 $x\le a$ , $y \le b$,并且 $gcd(x,y)=d$ 。作为FGD的同学,FGD希望得到你的帮助。

Input

The first line of the standard input contains one integer $n$ ($1\le n\le 50\ 000$),denoting the number of queries.
The following $n$ lines contain three integers each: $a$ , $b$ and $d$ ($1\le d\le a,b\le 50\ 000$), separated by single spaces.
Each triplet denotes a single query.

Output

Your programme should write $n$ lines to the standard output. The $i$ ‘th line should contain a single integer: theanswer to the $i$ ‘th query from the standard input.

Sample Input

2
4 5 2
6 4 3

Sample Output

3
2

HINT

对于第一组询问,满足条件的整数对有 $(2,2),(2,4),(4,2)$。对于第二组询问,满足条件的整数对有 $(6,3),(3,3)$。

题解

由题可知,需要我们求

那我们可以令 $a’={a \over d},\ b’={b\over d}$ 。
此时,求解 $\sum_{x=1}^{a}\sum_{y=1}^{b}[gcd(x,y)=d]$ 即是求解 $\sum_{x=1}^{a’}\sum_{y=1}^{b’}[gcd(x,y)=1]$。


由莫比乌斯函数的性质可以知道 $\sum_{d|n}\mu(d)=[n=1]$。
我们可以尝试把式子里的 $n$ 换成 $gcd(x,y)$。
即 $\sum_{d|gcd(x,y)}\mu(d)=[gcd(x,y)=1]$
式子可变为:

又知 $d|gcd(x,y)\ \rightarrow\ d|x\ and\ d|y$。
将和式前移,可得

再把形如 $\sum_{i=1}^{n}[d|i]$ 化简为 $\lfloor{n \over d}\rfloor$

此时如果暴力计算,则复杂度为 $O(n)$,但是可以观察到 $\lfloor{\frac{a’}{d}}\rfloor$ 和 $\lfloor{\frac{b’}{d}}\rfloor$ 是有大量重复的,于是可以用到前面整除分块的知识。利用整除分块和 $\mu(d)$ 的前缀和相乘,可将复杂度优化到 $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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 10;
int mu[maxn], prime[maxn], cnt = 0;
bool vis[maxn];

void init() {
mu[1] = 1;
for (int i = 2; i < maxn; i++) {
if (vis[i] == false) {
prime[cnt++] = i;
mu[i] = -1;
}
for (int j = 0; j < cnt && prime[j] * i < maxn; j++) {
vis[i * prime[j]] = true;
if (i%prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
} else {
mu[i * prime[j]] = -mu[i];
}
}
}
for (int i = 2; i < maxn; i++) {
mu[i] += mu[i - 1];
}
}

int solve(int a, int b) {
int ans = 0;
if (a > b) swap(a, b);
for (int l = 1, r; l <= a; l = r + 1) {
r = min(a/(a/l), b/(b/l));
ans += (mu[r] - mu[l - 1]) * (a/l) * (b/l);
}
return ans;
}


int main()
{
init();
int t, a, b, d;
scanf("%d", &t);
while (t--) {
scanf("%d %d %d", &a, &b, &d);
printf("%d\n", solve(a/d, b/d));
}


return 0;
}