正题

评测记录:https://www.luogu.org/recordnew/lists?uid=52918&pid=P1072

---

题目大意

a1=gcd(a0,x)a1=gcd(a0,x)
b1=gcd(b0,x)b1=gcd(b0,x)
求 xx

---

解题思路

如果
a1=gcd(a0,x)a1=gcd(a0,x)
所以 x=ka∗a1x=ka∗a1
b1=gcd(b0,x)b1=gcd(b0,x)
所以 x=b1/kbx=b1/kb
而且 ka,kbka,kb都是整数，所以 xx是a1a1的倍数也是 b1b1的因子。
所以暴力 b1−−√b1，然后用 a1a1剪枝就好了。

---

code

#include<cstdio> #include<algorithm> #define gcd(x,y) __gcd(x,y) #define lcm(x,y) x*y/__gcd(x,y) using namespace std; int t,a0,a1,b0,b1,q,p,ans; int main() {scanf("%d",&t);while(t--){scanf("%d%d%d%d",&a0,&a1,&b0,&b1);ans=0;q=a0/a1;p=b1/b0;for(int i=1;i*i<=b1;i++){if(!(b1%i)){ans+=(!(i%a1)&&gcd(i/a1,p)==1&&gcd(q,b1/i)==1);int k=b1/i;if(i==k) continue;ans+=(!(k%a1)&&gcd(k/a1,p)==1&&gcd(q,b1/k)==1);}}printf("%d\n",ans);} }

总结

以上是生活随笔为你收集整理的P1072-Hankson的趣味题【数论,gcd】的全部内容，希望文章能够帮你解决所遇到的问题。

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