洛谷【P2257】YY的GCD

题意：给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对

做的第一道莫比乌斯反演的题目有点...难啊,还没学会 待更
F(n)表示的是gcd(i,j)=n或为n的倍数的个数，那么我们再求解F(n)时显然是要枚举它的倍数
所以就是n|d，即枚举d为n的倍数

// 要设 F(n)= gcd(x,y)=n或者是n的倍数,个数为多少,
看：https://www.cnblogs.com/peng-ym/p/8652288.html

 

#include<bits/stdc++.h> #define N 10000100 typedef long long ll; const int maxn=10000000; using namespace std; ll g[maxn]; ll sum[maxn]; bool check[maxn]; ll mu[maxn]; ll prim[maxn]; int cnt=0; using namespace std; inline void read(int &x) {x=0;static int p;p=1;static char c;c=getchar();while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();}x*=p; } inline void print(long long x) {static int cnt;static int a[15];cnt=0;do{a[++cnt]=x%10;x/=10;}while(x);for(int i=cnt;i>=1;i--)putchar(a[i]+'0');puts(""); } bool vis[N]; void get_mu(int n) {mu[1]=1;for(int i=2;i<=n;i++){if(!vis[i]){mu[i]=-1;prim[++cnt]=i;}for(int j=1;j<=cnt&&prim[j]*i<=n;j++){vis[i*prim[j]]=1;if(i%prim[j]==0)break;else mu[prim[j]*i]=-mu[i];}}for(int j=1;j<=cnt;j++)for(int i=1;i*prim[j]<=n;i++)g[i*prim[j]]+=mu[i];for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(long long)g[i]; } int n,m; int main() {int t;read(t);get_mu(10000000);while(t--){read(n);read(m);if(n>m)swap(n,m);static long long ans;ans=0;for(int l=1,r;l<=n;l=r+1){r=min(n/(n/l),m/(m/l));ans+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);}cout<<ans<<endl;}return 0; }

 

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的洛谷【P2257】YY的GCD的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。