題意:鏈接

方法:莫比烏斯反演

解析:

這題跟上一篇博客有一點(diǎn)差別，當(dāng)然我們能夠考慮枚舉素?cái)?shù)這個(gè)大暴力。只是當(dāng)你A掉這道題后發(fā)現(xiàn)正解？都將近5s時(shí)。就放棄了這個(gè)念頭。

相同的式子我們能夠直接搬過(guò)來(lái)。p是質(zhì)數(shù)

∑p∑1<=x<=a∑1<=y<=b(gcd(x,y)==p)

∑p∑1<=x<=a/p∑1<=y<=b/p(gcd(x,y)==1)

∑p∑1<=x<=a/p∑1<=y<=b/p∑d|(x,y)μ(d)

∑p∑d=1min(a/p,b/p)μ(d)[apd][bpd]

設(shè)pd=k

∑k=1min(a,b)∑p且p|kμ(kp)[apd][bpd]

則設(shè)∑p且p|kμ(kp)=F(k)

發(fā)現(xiàn)F(k)的取值僅僅與選取的p與k的關(guān)系有關(guān)

F(k)=μ(pdp1)

當(dāng)p|d時(shí)

①p=p1 F(k)=μ(d)

②p!=p1 F(k)=0

故F(k)=μ(d)

當(dāng)p不整除d時(shí)

①p=p1 F(k)=μ(d)

②p!=p1 F(k)=?F(d)

故F(k)=μ(d)?F(d)

之后的內(nèi)容和1101一樣分塊

代碼:

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 10000010 using namespace std; typedef long long ll; int tot,t; int a,b,d; int prime[N]; bool f[N]; int miu[N]; ll g[N]; void sieve() {miu[1]=1;for(int i=2;i<=10000000;i++){if(!f[i]){prime[++t]=i;miu[i]=-1;}for(int j=1;j<=t&&i*prime[j]<=10000000;j++){f[i*prime[j]]=1;if(i%prime[j]==0){miu[i*prime[j]]=0;break;}else miu[i*prime[j]]=-miu[i];}}for(int i=1;i<=t;i++){for(int j=1;j*prime[i]<=10000000;j++){g[j*prime[i]]+=miu[j];}}for(int i=1;i<=10000000;i++){g[i]+=g[i-1];} } int main() {sieve();scanf("%d",&tot);for(int i=1;i<=tot;i++){scanf("%d%d",&a,&b);int a1=a,b1=b;int x=min(a1,b1);int pos;ll ans=0;for(int i=1;i<=x;i=pos+1){pos=min((a1/(a1/i)),(b1/(b1/i)));ans+=(g[pos]-g[i-1])*(a1/i)*(b1/i);}printf("%lld\n",ans);} }

總結(jié)

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

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