BZOJ 2301 [HAOI2011]Problem b


此题与 BZOJ 1101 [POI2007]Zap 同理

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2301

题意:给出 n 个询问,每次询问给出 a,b,c,d,k,询问有多少数对 (x,y),满足 a≤x≤b,c≤y≤d,且 gcd(x,y)=k。

首先这道题若 x 和 y 的范围为 [1,b],[1,d] 即同 1101,实际上,它们并没有什么区别。根据容斥原理,aks([a.b],[c,d]) 即相当于 ask([1,b],[1,d])-ask([1,a-1],[1,d])-ask([1,b],[1,c-1])+ask([1,a-1].[1,c-1]),至此本题转化为 1101.

下面我们考虑如何解决 1101. 为了方便叙述,询问中的 b,d 我们用 n,m 替代,且保证 n≤m.

首先我们定义如下运算

那么很显然地$$ans=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]$$

我们令$$N=\left \lfloor \frac{n}{k} \right \rfloor , M=\left \lfloor \frac{m}{k} \right \rfloor$$

那么$$ans=\sum_{i=1}^{N}\sum_{j=1}^{M} [gcd(i,j)==1]$$

同时,我们知道,莫比乌斯函数(此处链接未完成)具有如下的性质$$\sum_{d|n} \mu (d)[n=1]$$

那么就可以得到$$ans=\sum_{i=1}^{N} \sum_{j=1}^{M}\sum_{d|gcd(i,j)} \mu (d)$$

另外我们还有一个显而易见的性质$$d|gcd(i,j)\Leftrightarrow d|i\ \wedge \ d|j$$

所以$$ans=\sum_{i=1}^{N} \sum_{j=1}^{M}\sum_{d|i\ \&\ d|j} \mu (d)  \ \  (①)$$

然后下面的一步变换是比较关键同时可能相对难懂的,先给出,下面会稍详细解释

$$ans=\sum_{d=1}^{N} \mu (d) \left \lfloor \frac{N}{d} \right \rfloor \left \lfloor \frac{M}{d} \right \rfloor$$

对于上述①式,其意为对于每个 d,若有 t 对数对 (i,j) 被 d 整除,对答案的贡献即为$$\mu (d)*t$$

那么 t 实际上是什么呢,它实际上是 (被 d 整除 i)*(被 d 整除 j),那么式子就可以变换过来了

但是式子推到这里,时间复杂度是 O(n) 的,不能接受。$$\left \lfloor \frac{N}{d} \right \rfloor$$观察这个东西,它的值并非一直变化的,对于一个区间的 d 值,它的值可能是不变的,事实上,如果把它的图像画出来,同时连接图像上离散的点,它有一种“阶梯状”的感觉 (感性理解),可以证明的是 (待补充),它最多有 2 倍根号 N 个取值,所以我们维护一个前缀和,对于取值相同的我们直接计算即可

代码如下 (终于写完了 QwQ)

此题解部分改编自 神犇博客

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2301 [HAOI2011]Problem b


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: ,