[BZOJ2301/Luogu2522][HAOI2011]Problem b(莫比乌斯反演,容斥原理,数论分块)

发布于 2018-01-17  147 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2301/Luogu2522][HAOI2011]Problem b(莫比乌斯反演,容斥原理,数论分块)

Description

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

Http

BZOJ
Luogu

Tag

莫比乌斯反演,容斥原理,数论分块

题目大意

求\[\sum_{i=a}^{b} \sum_{j=c}^{d} [gcd(i,j)==K]\]

解决思路

先考虑求解\[Ans=\sum_{i=1}^{n} \sum_{j=1}^{m} gcd(i,j)==K\]
这个式子可以化成\[Ans=\sum_{i=1}^{n/K} \sum_{j=1}^{m/K} [gcd(i,j)==1]\]
由莫比乌斯反演可得(具体推导可以参考这里
\[Ans=\sum_{i=1}^{n/K} \mu(i) \lfloor \frac{n/K}{i} \rfloor * \lfloor \frac{m/K}{i} \rfloor\]
那么再考虑\(i\)从\(a\)开始,\(j\)从\(c\)开始。可以像求二维前缀和一样简单容斥一下,设\[Calc(n,m)=\sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i,j)==1]\],那么最后的答案就是
\[Ans=Calc(b,d)-Calc(a-1,d)-Calc(b,c-1)+Calc(a-1,c-1)\]

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2301/Luogu2522][HAOI2011]Problem b(莫比乌斯反演,容斥原理,数论分块)


HNCJ OIer