YY的GCD [hard] [莫比乌斯反演]

本文主要是介绍YY的GCD [hard] [莫比乌斯反演]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

题解传送门 

 

 

 

---

#include<bits/stdc++.h>
#define N 10000005
#define LL long long
using namespace std;
int p[N],isp[N],mu[N],f[N],T,tot; LL s[N];
void Init(){mu[1]=1;for(int i=2;i<=N-5;i++){if(!isp[i]) p[++tot]=i,mu[i]=-1;for(int j=1;j<=tot;j++){if(p[j]*i>N-5) break;isp[p[j]*i]=1; if(i%p[j]==0) break;mu[p[j]*i] = -mu[i];}}for(int i=1;i<=N-5;i++)for(int j=1;j<=tot;j++)if(p[j]*i<=N-5) f[p[j]*i] += mu[i]; else break;for(int i=1;i<=N-5;i++) s[i]=(LL)s[i-1]+f[i];
}
void Solve(){int n,m; scanf("%d%d",&n,&m);if(n>m) swap(n,m); LL ans=0;for(int l=1,r;l<=n;l=r+1){int x1=n/l,x2=m/l;r=min(n/x1,m/x2);ans += (LL)(s[r]-s[l-1]) * x1 *x2;}printf("%lld\n",ans);
}
int main(){scanf("%d",&T); Init();while(T--) Solve(); return 0;
}

 

这篇关于YY的GCD [hard] [莫比乌斯反演]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---