题意
输入四个数 a , b , c , d a,b,c,d a,b,c,d,请你输出一个正整数 x x x
满足
x
x
x是
a
a
a的倍数且
x
x
x是
c
c
c的倍数,另外满足
b
b
b是
x
x
x的倍数且
d
d
d是
x
x
x的倍数。
(
a
<
x
<
b
,
c
<
x
<
d
)
(a<x<b,c<x<d)
(a<x<b,c<x<d)
x x x是 a , c a,c a,c的倍数,由于 l c m ( a , c ) lcm(a,c) lcm(a,c)是最小满足条件的数,所以 x x x是 l c m ( a , c ) lcm(a,c) lcm(a,c)的倍数
x x x是 b , d b,d b,d的因子,那么 x x x只能是 g c d ( b , d ) gcd(b,d) gcd(b,d)的因子
我们从 1 1 1暴力枚举到 g c d ( b , d ) gcd(b,d) gcd(b,d)判断即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e7+10;
int a,b,c,d;
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
signed main()
{
cin >> a >> b >> c >> d;
//求出一个x使得a,c是x的因子
//x是b,d的因子
int ac = a/gcd(a,c)*c;
int bd = gcd(b,d);
//x是bd的因子,且是ac的倍数
for(int i=ac;i<=bd;i+=ac)
if( bd%i==0 && i>max(a,c) && i<min(b,d) )
{
cout << i;
return 0;
}
cout << -1;
}