AK-dream

Problem b[HAOI2011]

AK-dream

发布于：2020年6月23日
次浏览

题目描述

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

题解

莫比乌斯反演

我们可以用二维前缀和的思想，我们设

$f(n,m)=\sum\limits_{i=1}^n \sum\limits_{j=1}^m [\gcd(i,j)=k]$，

那答案应为

$f(b,d)-f(b,c-1)-f(a-1,d)+f(a-1,c-1)$

接下来看看$f(n,m)$怎么求：

$\sum\limits_{i=1}^n \sum\limits_{j=1}^m [\gcd(i,j)=k]$

$=\sum\limits_{i=1}^{n/k} \sum\limits_{j=1}^{m/k} [\gcd(i,j)=1]$

使用莫比乌斯反演

$=\sum\limits_{i=1}^{n/k} \sum\limits_{j=1}^{m/k} \sum\limits_{d|gcd(i,j)}\mu(d)$

把$d$放到前面枚举，设$i=xd,\ j=yd$

$=\sum\limits_{d} \mu(d) * \sum\limits_{x=1}^{n/kd} \sum\limits_{y=1}^{m/kd} 1$

$=\sum\limits_{d} \mu(d) * \lfloor \frac{n}{kd}\rfloor * \lfloor \frac{m}{kd}\rfloor$

预处理$\mu(d)$的前缀和，使用除法分块即可做到时间复杂度$O(\sqrt{n})$

总时间复杂度$O(n\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
#include <bits/stdc++.h>
using namespace std;

int t, a, b, c, d, k;
int pr[50005], mb[50005], sum[50005], tot;
bool np[50005];

void init() {
	mb[1] = 1;
	for (int i = 2; i <= 50000; i++) {
		if (!np[i]) pr[++tot] = i, mb[i] = -1;
		for (int j = 1; j <= tot && i * pr[j] <= 50000; j++) {
			np[i*pr[j]] = 1;
			if (i % pr[j] == 0) {
				mb[i*pr[j]] = 0;
				break;
			} else mb[i*pr[j]] = -mb[i];
		}
	}
	for (int i = 1; i <= 50000; i++) sum[i] = sum[i-1] + mb[i];
}

int solve(int nn, int mm) {
	int ret = 0, n = nn / k, m = mm / k;
	for (int l = 1, r = 0; l <= min(n, m); l = r + 1) {
		r = min(n / (n / l), m / (m / l));
		ret += (sum[r] - sum[l-1]) * (n / l) * (m / l); 
	}
	return ret;
}

int main() {
	scanf("%d", &t);
	init();
	while (t--) {
		scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);
		printf("%d\n", solve(b, d) + solve(a-1, c-1) - solve(b, c-1) - solve(a-1, d));
	}
	return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://akdream.tk/post/93e29827.html/

更新于：2020年9月7日

数论

莫比乌斯函数

评论