[BZOJ2820/Luogu2257]YY的GCD(莫比乌斯反演,数论分块,线性筛)

发布于 2018-01-20  191 次阅读


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

本文链接地址:[BZOJ2820/Luogu2257]YY的GCD(莫比乌斯反演,数论分块,线性筛)

Description

神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种
傻×必然不会了,于是向你来请教……多组输入

Http

BZOJ
权限题,提供本站离线版本BZOJch
Luogu

Tag

莫比乌斯反演,数论分块,线性筛

题目大意

求\(\sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i,j)\ is\ a\ prime]\)

解决思路

这一题类似,但是有多组数据。
直接从那一题的结尾开始推
\[Ans=\sum_{d=1}^{n} f(d)*\sum_{i=1}^{n/d} \mu(i) \lfloor \frac{n}{id} \rfloor^2\]
另\(T=id\),变枚举\(d\)为枚举\(T\)
\[Ans=\sum_{T=1}^{n} \lfloor \frac{n}{T} \rfloor ^2 \sum_{d|T} [d\ is\ a\ prime]*\mu(\frac{T}{d})\]
后面这个东西\(\sum_{d|T} [d\ is\ a\ prime]*\mu(\frac{T}{d})\)虽然不是积性函数,但是可以线性筛的,具体来说,设\(h(x)=\sum_{d|T} [d\ is\ a\ prime]*\mu(\frac{T}{d})\),那么有
设\(p\)为质数
\(h(p)=1\),这个很容易得到
\(h(p*i)=\mu(i) \quad [gcd(p,i)==p]\)。这个的原理是如果乘进去一个质数\(p\),并且这个\(p\)在\(i\)中已经出现过了,那么在\(\mu(x)\)中就必定有大于等于\(2\)个质因子\(p\),根据莫比乌斯函数的定义\(\mu(x)==0\),所以就只剩\(\mu(i))\)自己的贡献
\(h(p*i)=\mu(i)-h(i) \quad [gcd(p,i)==1]\)。原因是由于乘进去一个互质质数\(p\),原来的莫比乌斯函数要变号,再加上\(mu(i)\)的贡献。
那么结合数论分块,可以做到\(O(n)\)预处理,\(O(\sqrt{n})\)单次询问

代码

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

本文链接地址:[BZOJ2820/Luogu2257]YY的GCD(莫比乌斯反演,数论分块,线性筛)


HNCJ OIer