正題

評(píng)測(cè)記錄: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都是整數(shù)，所以 xx是a1a1的倍數(shù)也是 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);} }

總結(jié)

以上是生活随笔為你收集整理的P1072-Hankson的趣味题【数论,gcd】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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