BZOJ 2820 YY 的 GCD


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

题意:给出 T 组询问,对于每组询问,给出两个正整数 n,m,问对于每组在区间 [1,n] 中 i 和在 [1,m] 中的 j,使得 gcd(i,j) 为质数的数对有多少对。

         T≤104             n,m≤107


最近学了莫比乌斯反演,刷了好多水题 QwQ,此题在前半部分的推导中和 这道题 很类似,下面就只给出式子啦 QwQ(令 n≤m)

同样地,为了便于描述,我们定义如下运算

$$ans=\sum_{p\ ispri}^{n}\sum_{i=1}^{n} \sum_{j=1}^{m}[gcd(i,j)=p]$$

$$ans=\sum_{p\ ispri}^{n} \sum_{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{p} \right \rfloor} [gcd(i,j)=1]$$

$$ans=\sum_{p\ ispri}^{n} \sum_{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{p} \right \rfloor}\sum_{d|gcd(i,j)}^{ } \mu (d)$$

$$ans=\sum_{p\ ispri}^{n} \sum_{i=1}^{\left \lfloor \frac{n}{p} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{p} \right \rfloor}\sum_{d|i\  \wedge\  d|j}^{ } \mu (d)$$

$$ans=\sum_{p\ ispri}^{n} \sum_{d=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\mu (d) \left \lfloor \frac{n}{pd} \right \rfloor\left \lfloor \frac{m}{pd} \right \rfloor$$

在下面的步骤中,我们令 k = pd 同时我们枚举 k,这样做的好处是显而易见的

$$ans=\sum_{k=1}^{n}\sum_{p\ ispri\ \wedge \ p|k}^{ }\mu (\frac{k}{p})\left \lfloor \frac{n}{k} \right \rfloor\left \lfloor \frac{m}{k} \right \rfloor$$

令$$F(k)=\sum_{p\ ispri\ \wedge \ p|k}^{ }\mu (\frac{k}{p})$$

对于 F(k) 我们可以预处理啦!枚举质数,再倍增,这样预处理 F(k) 的时间复杂度可以认为是小于 O(n) 的,可以接受~

代码如下

 

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

转载:转载请注明原文链接 - BZOJ 2820 YY 的 GCD


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

标签: ,