[BOJ 2436 // C++] 공약수

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2436번 문제인 공약수이다.
문제는 아래 링크를 확인하자.

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

2436번: 공약수

어떤 두 양의 정수의 최대공약수가 g이고 최소공배수가 L이라 하자. 이 때 두 정수는 각각 g의 배수이므로 gX, gY와 같이 나타낼 수 있고(단 X와 Y는 서로소) L = gXY와 같이 나타낼 수 있다.

 

따라서 L/g를 서로소인 두 양의 정수로 나눌 때 두 정수의 합의 최솟값(=X+Y의 최솟값)을 갖는 X와 Y의 값을 구하고 그 값으로 원래의 두 정수 gX와 gY를 출력하는 것으로 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int gcd(int x, int y) {
	if (y) return gcd(y, x % y);
	return x;
}

int A, B, AA, BB;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> A >> B;
	B /= A;
	for (int i = 1; i * i <= B; i++) {
		if (B % i) continue;
		int X = i, Y = B / i;
		if (gcd(X, Y) > 1) continue;

		AA = X, BB = Y;
	}

	cout << A * AA << ' ' << A * BB;
}