「BZOJ 2301」「HAOI2011」Problem b

题目地址

描述

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

$1 \leq n\leq50000,1\leq a\leq b\leq 50000,1\leq c \leq d\leq 50000,1\leq k \leq 50000$

分析

这是一个计算满足 gcd(i, j) = ki, j 个数的题目,这样的模型经常出现。

这里我们默认 $n \leq m$,如果不满足就交换。
令 $f(k)$ 为 $gcd(i, j) = k$ 的个数,$g(k)$ 为 $k \mid gcd(i, j)$ 的个数。

那么有以下关系:
我们需要求 $f(k)$,通过反演我们得到:

那么这里的瓶颈就是如何快速求出 $g(d \times k)$,首先考虑如何快速求出 $g(k)$,因为 $i = k \times x_{1}, j = k \times y_{1}$,我们只需要求出来有多少对满足条件的 $x_{1}, y_{1}$,即可求出 $g(k)$,因此有:

那么原式可改写为:
我们可以暴力计算在 $\Theta(n + T\frac{n}{k})$ 的时间内算出来,但是时间复杂度仍然太高,考虑如何降低时间复杂度。

如之前所说,算法的瓶颈在于如何快速计算 $g(d \times k)$,这里可以用 分块 来解决。

如图所示,是 $n = 32, m = 40, k = 2​$ 的 $\left \lfloor \frac{n}{dk} \right \rfloor,\left \lfloor \frac{m}{dk} \right \rfloor, \mu(d)​$ 的取值。

  1. $1 \leq d \leq \sqrt n$,$d$ 最多有 $\sqrt n$ 个取值,$\left \lfloor \frac{n}{d} \right \rfloor$ 最多有 $\left \lfloor \sqrt n \right \rfloor$ 个不同的取值。
  2. $\sqrt n + 1 \leq d \leq n$,$\left \lfloor \frac{n}{d} \right \rfloor \leq \left \lfloor \sqrt n \right \rfloor$,所以 $\left \lfloor \frac{n}{d} \right \rfloor$ 最多有 $\left \lfloor \sqrt n \right \rfloor$ 个取值。

综上所述,$\left \lfloor \frac{n}{d} \right \rfloor$ 最多有 $2 \left \lfloor \sqrt n \right \rfloor$ 个取值。
那么我们可以最多分为 $2 \left \lfloor \frac{n}{dk} \right \rfloor + 2 \left \lfloor \frac{m}{dk} \right \rfloor$ 段来计算。

总时间复杂度 $\Theta(T(\sqrt n + \sqrt m))$

代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//  Created by ZJYelizaveta on Thursday, September 28, 2017 PM02:17:53 CST
// Copyright (c) 2017年 ZJYelizaveta. All rights reserved.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
template<typename T> T readIn() {
T x(0), f(1);
char ch = getchar();
while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
return x * f;
}
const int MAX_N = 50000 + 3;
const int INF = 0x3f3f3f3f;
int testCase;
int prime[MAX_N], mu[MAX_N], sum[MAX_N], cnt = 0;
bool isNotPrime[MAX_N];

inline void sieve() {
memset(prime, 0, sizeof prime);
memset(mu, 0, sizeof mu);
memset(isNotPrime, false, sizeof isNotPrime);
mu[1] = 1, isNotPrime[0] = isNotPrime[1] = true;

for (register int i = 2; i < MAX_N; ++i) {
if (!isNotPrime[i]) {
prime[++cnt] = i;
mu[i] = -1;
}
for (register int j = 1; j <= cnt && i * prime[j] < MAX_N; ++j) {
isNotPrime[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 = 1; i <= 12; ++i) printf("%d ", mu[i]); printf("\n");
sum[0] = 0;
for (register int i = 1; i < MAX_N; ++i) sum[i] = sum[i - 1] + mu[i];
// for (int i = 1; i <= 12; ++i) printf("%d ", sum[i]); printf("\n");
}

inline int solve(int n, int m, int k) {
if (n > m) swap(n, m);
n /= k, m /= k;

int last = 0, ans = 0;
for (register int i = 1; i <= n; i = last + 1) {
last = min((n / (n / i)), (m / (m / i)));
ans += (sum[last] - sum[i - 1]) * (n / i) * (m / i); //
}
return ans;
}

int main()
{
sieve();
testCase = readIn<int>();
while (testCase--) {
int a = readIn<int>(), b = readIn<int>(), c = readIn<int>(), d = readIn<int>(), k = readIn<int>();

int ans = solve(b, d, k) - solve(a - 1, d, k) - solve(b, c - 1, k) + solve(a - 1, c - 1, k);
printf("%d\n", ans);
}
return 0;
}
Partager