BOJ 2436 - 공약수

문제 링크

---

https://www.acmicpc.net/problem/2436

문제 해결

---

1. 구하려는 두 수를 a, b로 놓는다.

2. a == (GCD*x), b == (GCD*y) 이므로, measure = x*y (x*y == LCM/GCD)

3. measure의 (x,y)쌍을 찾되 합이 가장 작은 것을 찾아야하므로 시간을 단축하기 위해, sqrt(measure)부터 찾는다.

주의할 점

---

1. LCM == GCD*x*y가 성립하기 위해선 반드시 x와 y가 서로소임을 보여야한다.

	/*
	explanation in vjerksen.tistory.com
	*/
	#include<cstdio>
	#include<cstring>
	#include<cstdlib>
	#include<iostream>
	#include<string>
	#include<deque>
	#include<vector>
	#include<algorithm>
	#include<queue>
	#include<set>
	#include<cmath>
	using namespace std;
	long long GCD,LCM,measure,a,b;
	bool Euclidean(long long c, long long d){
	long long r=0;
	if(c<d) swap(c,d);
	r = c%d;
	if(r==0){
	if(d==1)
	return true;
	else
	return false;
	}
	else
	go(d,r);
	}
	int main(){
	cin >> GCD >> LCM;
	measure = LCM/GCD;
	for(long long i=sqrt(measure);i>=1;i--){
	if(!measure%i){
	// caution 1
	if(Euclidean(i,measure/i)){
	a=i; b=measure/i;
	break;
	}
	}
	}
	if(a==0&&b==0){
	printf("%lld %lld",GCD,LCM);
	return 0;
	}
	a*=GCD; b*=GCD;
	a>b ? printf("%lld %lld",b,a) : printf("%lld %lld",a,b);
	return 0;
	}

view raw BOJ 2436.cpp hosted with ❤ by GitHub

※ 정확하고 부드러운 태클은 언제나 환영입니다.