【Problem b HYSBZ - 2301】【GCD HDU - 1695】莫比乌斯反演 + 容斥 + 分块

Problem b HYSBZ - 2301

对于给出的 $n$ 个询问,每次求有多少个数对 $(x,y)$ ,满足 $a ≤ x ≤ b$ , $c ≤ y ≤ d$ ,且 $gcd(x,y) = k$ , $gcd(x,y)$ 函数为 $x$ 和 $y$ 的最大公约数。

Input

第一行一个整数 $n$,接下来 $n$ 行每行五个整数,分别表示 $a、b、c、d、k$

Output

共 $n$ 行,每行一个整数表示满足要求的数对 $(x,y)$ 的个数

Sample Input

2
2 5 1 5 1
1 5 1 5 2

Sample Output

14
3

Hint

$100\%$ 的数据满足:$1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000$

题解

题目求解

令 $f=[gcd(x,y)=k]$
根据容斥的原理,我们可以知道

所以重点在于 $\sum_{x = 1}^{n}\sum_{y = 1}^{m}f$ 的求法。
和以前一样,令 $n’=\lfloor{n\over k}\rfloor,m’=\lfloor{m\over k}\rfloor$ 。

因此也可以分块计算。

代码

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
#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 && i * prime[j] < 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 n, a, b, c, d, k;
scanf("%d", &n);
while (n--) {
scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
printf("%d\n", solve(b/k, d/k) - solve(b/k, (c - 1)/k) - solve((a - 1)/k, d/k) + solve((a - 1)/k, (c - 1)/k));
}

return 0;
}

GCD HDU - 1695

Problem Description

Given $5$ integers: $a, b, c, d, k,$ you’re to find $x$ in $a…b$, $y$ in $c…d$ that $gcd(x, y) = k$. $gcd(x, y)$ means the greatest common divisor of $x$ and $y$. Since the number of choices may be very large, you’re only required to output the total number of different number pairs.
Please notice that, ($x=5, y=7$) and ($x=7, y=5$) are considered to be the same.


You can assume that $a = c = 1$ in all test cases.

Input

The input consists of several test cases. The first line of the input is the number of the cases. There are no more than $3,000$ cases.
Each case contains five integers: $a, b, c, d, k, 0 < a \le b \le 100,000, 0 < c \le d \le 100,000, 0 \le k \le 100,000$, as described above.

Output

For each test case, print the number of choices. Use the format in the example.

Sample Input

2
1 3 1 5 1
1 11014 1 14409 9

Sample Output

Case 1: 9
Case 2: 736427

Hint

For the first sample input, all the $9$ pairs of numbers are $(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5)$.

题解

起始这题和上题差不多,一样的容斥。但是不同的是在这题看来,$(2,3)$ 和 $(3,2)$ 被看作是同样的一对,只计数一次。
题目已经说明保证 $a = c = 1$。
所以我们只需要容斥进行这样子的处理:
令 $f=[gcd(x,y) =k]$ 。

想想为什么?


因为只有满足 $x,y \in [1, min(b,d)]$ 才会有重复对的情况吧?

接下来对式子的处理也很容易。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 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[prime[j] * i] = 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];
}
}

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

int main()
{
init();
int a, b, c, d, k, n;
scanf("%d", &n);
for (int ca = 0; ca < n; ca++) {
scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);
if (k == 0) {
printf("Case %d: 0\n", ca + 1);
continue;
}
if (b > d) swap(b, d);
printf("Case %d: %lld\n", ca + 1, solve(b/k, d/k) - solve(b/k, b/k)/2);
}

return 0;
}