[BOJ] 2436 | 공약수

문제

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

출처

• KOI 2011 초등부 2번
• KOI 2011 중등부 1번
• KOI 2011 고등부 1번

풀이

유클리드 호제법 (최대공약수 구하기) :https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

여기서는 두 입력으로 최대공약수와 최소공배수를 준다.

두 수를 각 a와 b라고 할때, LCM을 다음과 같이 나타낼 수 있다.

LCM = a*b/GCD

이를 정리하면,

GCD * LCM = a*b

이를 이용하여 시간복잡도 O(sqrt(GCD*LCM)) = O(sqrt(a*b))만에 풀 수 있다.

입력이 1억이니, int 범위 초과에 주의하자.

소스

#include<iostream>
using namespace std;

long long GCD, LCM, mul, a, b, flag;
long long gcd(long long a, long long b) {
	return b ? gcd(b, a%b) : a;
}

int main() {
	cin >> GCD >> LCM;
	mul = GCD * LCM;
	a = 1; b = LCM;
	for (int i = 1; i <= mul / i; i++) {
		if (mul%i || gcd(i, mul / i) != GCD)
			continue;
		flag = 1;
		a = i, b = mul / i;
	}
	if(flag)
		cout << a << " " << b;
}