洛谷P1072：https://www.luogu.org/problemnew/show/P1072
思路
gcd(x,a0)=a1
lcm(x,b0)=b1→b0*x=b1*gcd(x,b0) (由a*b=gcd(a,b)*lcm(a,b))
x=(b1/b0)*gcd(x,b0)
令i=gcd(x,b0)∈[1,√b0] 分成两半求减少时间复杂度 特判相等的时候
判断x=(b1/b0)*i和x=(b1/b0)*(b0/i)是否满足条件
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,a0,a1,b0,b1,ans;
int gcd(
int a,
int b)
{
if(b==
0)
return a;
else
return gcd(b,a%
b);
}
int main()
{
scanf("%d",&
n);
for(
int i=
1;i<=n;i++
)
{
scanf("%d%d%d%d",&a0,&a1,&b0,&
b1);
ans=
0;
if(b1
