c언어 2436번 공약수 (백준)

#include <stdio.h>

int U(int a, int b) { //유클리드 (최대공약수)
	int r = a%b;
	if(r) U(b, r);
	else return b;
}

int main(void) {
	long long int gcd = 1, lcm = 1, X; //X = gcd * lcm = 구하고자 하는 두 수의 곱
	scanf("%lld %lld", &gcd, &lcm);
	X = gcd*lcm;
	long long int a=1, b=1; //구하고자 하는 두 수를 a, b로 둠
	long long int ans_a=1, ans_b=1; //정답으로 출력할 a, b의 값을 저장하는 변수
	long long int ans = 200000000; //a+b의 값을 더할 변수
	for(long long int i=1; ; i++) {
		a = gcd*i; //a가 커질수록 b는 반비례하며 줄어든다. X = a*b이므로
		if(a > lcm) break; //a가 최소공배수보다 크면 for을 종료한다
		if(X % a) continue; //a*b!=X라면 skip한다
		b = X / a; //b값 대입
		
		if(U(a, b) != gcd) continue; //만약 a, b의 최대공약수가 gcd가 아니라면, skip한다
		
		if(ans > a+b) { //구하고자 하는 두수의 합이 전의 합보다 작으면
			ans = a+b; //ans에 이 값을 대입하고
			ans_a=a; //정답이 될 a, b을 교체한다
			ans_b=b;
		} else if(ans == a+b) { //만약 합이 같다면, 두수의 차이를 비교해야 한다.
			long long int gap = a-b;
			if(gap < 0) gap*=-1;
			long long int ans_gap = ans_a-ans_b;
			if(ans_gap < 0) ans_gap*=-1;
			if(ans_gap > gap) { //기존보다 a,b의 값의 차이가 적다면 교체한다.
				ans_a = a;
				ans_b = b;
 			} 
		}
	}
	printf("%lld %lld", ans_a, ans_b); //구한 두 수의 값을 출력한다
}

 

 

풀이 : 최대 공약수와 최소공배수

구하고자 하는 두 수의 최대공약수와, 최소공배수가 있으면, 그 두 수를 유추할 수가 있다.

최소공배수는 어떤 두수 의 값을 곱한 것에 최대공약수를 나눈 것이기 때문이다.

 

예제에서 의 6 108도

108 = (x*y)/6이 된다. 여기서 최대공약수를 좌변으로 옮기면 108*6 = x*y가 된다.

즉 x*y의 값이 최대공약수 * 최소공배수의 조건을 만족하는 경우에서, x의 값을 점차 늘리고 (y값은 반비례하게 감소)

x와 y의 최대공약수가 처음에 입력받은 것과 같은지를 비교 후

x+y값이 더 작을 때마다 x,y값을 교체해 주며

값이 같은 경우, x,y의 차가 더 작은 것을 구해서 교체해 준다.

 

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

2436번: 공약수