BZOJ 2820 YY 的 GCD

发布于 2017-04-13  243 次阅读


题目链接: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) 的,可以接受~

代码如下

 


一个非常弱的准退役OIER