BZOJ 2301 [HAOI2011]Problem b （莫比乌斯反演）

BZOJ 2301 [HAOI2011]Problem b （莫比乌斯反演）

Description

对于给出的 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

22 5 1 5 11 5 1 5 2

Sample Output

143

思路

首先我们可以利用容斥原理将一个询问分解为四个，每次询问有多少个数对 (x,y) 满足 1<=x<=n,1<=y<=m 且 gcd(x,y)=k

然后问题便等价于询问有多少个数对 (x,y) 满足 1<=x<=⌊nk⌋,1<=y<=⌊mk⌋ 且 x 与 y

PS：这道题目的时间限制有 50s ，不过也千万别想枚举过掉它，因为 O(n3) 的复杂度在 n=1e5

我们考虑使用莫比乌斯反演

因为之前的结论，我们可以令 f(i) 为 1<=x<=n,1<=y<=m 且 gcd(x,y)=i 的数对 (x,y) 的个数， F(i) 为 1<=x<=n,1<=y<=m 且 i|gcd(x,y) 的数对 (x,y) 的个数，满足 F(i)=∑i|df(d)

显然，我们有 F(i)=⌊ni⌋⌊mi⌋

反演之后即 f(i)=∑i|dμ(di)F(d)=∑i|dμ(di)⌊nd⌋⌊md⌋

枚举原题中 k 的倍数，我们就可以在 O(n) 的时间处理每一个询问了，不过 O(n)

我们发现，对于其中连续的 s 项，有可能有 ⌊nd⌋=⌊nd+s⌋ ，那么对于这 s 项的贡献，我们可以直接得出，即 (Sumd+s−Sumd−1)×nd×md ，其中 Sumi 代表莫比乌斯函数的前 i

观察式子，我们发现 ⌊nd⌋ 最多有 2n√ 个取值，于是 ⌊nd⌋⌊md⌋ 至多有 2(n√+m−−√) 个取值，所以我们只需要枚举这 2(n√+m−−√)

PS：关于如何求出二元组 (nx,mx) 取值范围相同的一段：对于当前点 x ，其向右延伸最远为 min(nnx,mmx) ，因为 nx 为下界，那么 nnx

AC 代码

#include#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。