牛客挑战赛51 A.NIT的签到题(暴力gcd)

LINK

题意

输入四个数 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;
}
上一篇:Codeforces1285C Fadi and LCM (数学 思维)


下一篇:Codeforces 729 Div.2