[C/C++] 백준 2436번 - 공약수

✏️문제 링크

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

2436번: 공약수

 

✏️문제 설명

 

 

✏️문제 풀이

일단 문제를 보기에 앞서 두 수를 a, b 라 하면 a와 b의 최대공약수는 m=gcd(a,b)이고, 최소공배수는 a*b/m입니다.

즉 문제에서 최대공약수와 최소공배수가 주어지는데 정답으로 출력하고자 하는 두 개의 자연수의 곱은

최대공약수 * 최소공배수가 되어야 합니다. 이는 최소공배수와 최대공약수를 구하는 식을 보시면 당연한 결과입니다

int형으로 하면 오버플로우가 발생할 수 있기 때문에 두 수의 곱을 저장(mul)하는 자료형을 long long으로 지정했습니다.

 

이제 반복문을 돌리면서 두 수를 구해야 합니다.

먼저 시작하는 i는 최대공약수로 두고, 범위를 최소공배수까지로 한 다음 i+=최대공약수로 설정하였습니다.

차피 나눌건데 굳이 1부터 시작할 필요도 없고, 두 수의 최대공약수가 이미 지정되어있기 때문에 나누는 변수도

최대공약수의 배수로 한 다음 반복문의 길이를 줄일 수 있습니다. 그리고 출력하고자 하는 두 자연수의 최댓값도

주어진 최소공배수보다 클 수 없기 때문에 이런 점들을 생각했습니다.

 

반복문을 돌리면서 mul % i ==0이고 i, mul/i의 gcd가 문제에서 주어진 최소공배수와 같으면 추가를 해주었습니다.

이런 식으로 반복문을 돌리고 정답을 출력했습니다.

 

✏️문제 코드

#include<iostream>
#include<tuple>
#include<vector>
using namespace std;

#define ll long long
typedef tuple<ll ,ll ,ll>cur;
vector<cur>res;

long gcd(int a, int b);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll a, b;
	cin >> a >> b;
	ll mul = a * b;

	for (ll i = a; i <= b; i+=a) {
		if (mul % i == 0) {			
			if (gcd(i, (mul / i)) == a) {
				res.push_back(cur{ i,mul / i,i + (mul / i) });
			}
		}
	}

	int index = 0;
	int min = 300000000;
	for (int i = 0; i < res.size(); i++) {
		cur temp = res[i];
		int value = get<2>(temp);
		if (min > value) {
			index = i;
			min = value;
		}
	}

	cur result = res[index];
	cout << get<0>(result) << " " << get<1>(result);
}
long gcd(int a, int b) {
	if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}