那么应该是没判断x与y相等的情况!!!
因为gcd(x,a0)一定小于等于x or a0
x,a0一定是gcd(x,a0)的倍数
由此得出: x=a1∗p1 a0=a1∗p2
p1=x/a1 p2=a0/a1
p1,p2一定互质,可以自己举几个例子
lcm(x,b0)同理,只不过变为除法
x=b1/p1 b0=b1/p2
p1=b1/x p2=b1/b0
是人就知道观察两个式子可以发现x既是a1倍数又是b1的因数
所以:枚举b1 的因子(也就是x),判断x是否是a1的倍数加上那两个式子就行了
#include<bits/stdc++.h>
#define IOS; ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
int n,a0,a1,b0,b1;
int gcd(int x,int y){
if(y==0) return x;
else return gcd(y,x%y);
}
int main(){
IOS;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a0>>a1>>b0>>b1;
int sum=0;
for(int j=1;j*j<=b1;j++){
if(b1%j==0){
if(j%a1==0&&gcd(j/a1,a0/a1)==1&&gcd(b1/b0,b1/j)==1){
sum++;
}
int k=b1/j;
if(j&k==j) continue;
if(k%a1==0&&gcd(k/a1,a0/a1)==1&&gcd(b1/b0,b1/k)==1){
sum++;
}
}
}
cout<<sum<<"\n";
}
return 0;
}
本蒟蒻的第一道绿题,必须写篇题解庆祝一下