[BZOJ2818/Luogu2568] gcd (莫比乌斯反演)

发布于 2018-01-19  9 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2818/Luogu2568] gcd (莫比乌斯反演)

Description

给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.

Tag

莫比乌斯反演

题目大意

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

解决思路

设\( f(d)=\begin{cases} 1 \quad d\ is\ a\ prime \\ 0 \quad\ d\ is\ not\ a\ prime\end{cases}\)
提取gcd(i,j)==d,得到
\[Ans=\sum_{d=1}^{n} f(d)*\sum_{i=1}^{n} \sum_{j=1}^{m} [gcd(i,j)==1]\]
根据以前(这里)推出的式子,由莫比乌斯反演得
\[Ans=\sum_{d=1}^{n} f(d)*\sum_{i=1}^{n/d} \mu(i) \lfloor \frac{n}{id} \rfloor^2\]
那么记一下质数个数的前缀和以及\(\mu()\)的前缀和前后两层数论分块即可

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2818/Luogu2568] gcd (莫比乌斯反演)


HNCJ OIer 一枚