• 題意
  給定\(n,m(1 \leqslant n,m \leqslant 10000000)\),求\(1\leqslant x \leqslant n\), \(1 \leqslant y \leqslant m\)且\(\gcd(x, y)\)為質(zhì)數(shù)的\((x, y)\)有多少對(duì).
  \(T(\leqslant 10000)\)組詢問(wèn)

• 題解
  \[ans = \sum_{p \in P}\sum_{i=1}^{n}\sum_{j=1}^{m}{[\gcd(i,j)=p]} \\ = \sum_{p \in P}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}{[\gcd(i,j)=1]} \\ = \sum_{p \in P}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{d|\gcd(i,j)}\mu(d) \\ = \sum_{p \in P}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{d|i,d|j}\mu(d) \\ = \sum_{p \in P} \sum_{d=1}^{\min(n,m)} \mu(d)\biggl\lfloor\frac{n}{pd}\biggr\rfloor \biggl\lfloor\frac{m}{pd}\biggr\rfloor \\ = \sum_{T}^{\min(n,m)}\biggl\lfloor\frac{n}{T}\biggr\rfloor \biggl\lfloor\frac{m}{T}\biggr\rfloor \sum_{p \in P, p|T}\mu(\frac{T}{p})\]
  令\[f(T)=\sum_{p \in P, p|T}\mu(\frac{T}{p})\]
  那么對(duì)\(f(T)\)求前綴和則問(wèn)題可以在\(O(\sqrt{n})\)的時(shí)間內(nèi)解決。
  顯然\(f(T)\)可以通過(guò)類(lèi)似埃式篩法在\(O(n\log\log n)\)的時(shí)間內(nèi)求出
  至此，問(wèn)題在\(O(n\log\log n+T\sqrt{n})\)內(nèi)解決
  ————————————————————————————————————————
  然而\(f(T)\)仍然可以通過(guò)線性篩得到：
  現(xiàn)在已知\(f(x) = \sum_{p'|x}\mu(\frac{x}{p'})\)
  考慮\(f(px)\)
  若\(p|x\)，則\[f(px) = \sum_{p'|x}\mu(\frac{xp}{p'})\]
  顯然，當(dāng)\(p=p'\)時(shí)值為\(\mu(x)\)，當(dāng)\(p \ne p'\)時(shí)，值為0.
  所以此時(shí)\(f(px) = \mu(x)\)
  若\(p\not|x\)，則\[f(px) = \sum_{p'|x}\mu(\frac{xp}{p'}) + \mu(x) = -f(x) + \mu(x)\]
  至此，問(wèn)題在\(O(n+T\sqrt{n})\)內(nèi)解決

轉(zhuǎn)載于:https://www.cnblogs.com/showson/p/5403443.html

總結(jié)

以上是生活随笔為你收集整理的bzoj2820: YY的GCD的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。