[백준] 2436 공약수

백준 2436 공약수

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

• A와 B의 최소공배수(lcm) = (A x B) / 최대공약수(gcd)

#include <iostream>
#include <math.h>
#include <limits.h>
using namespace std;

typedef long long int ll;

ll getgcd(ll p, ll q) {
	if (q == 0) return p;
	return getgcd(q, p % q);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll gcd, lcm, mul;
	cin >> gcd >> lcm;
	mul = lcm * gcd;

	ll minA = 0, minB = 0;
	ll  minsum = 200000001;

	ll A, B;
	for (A = gcd; A <= sqrt(mul); A++) {
		if (mul % A == 0) {
			B = mul / A;

			if (getgcd(A, B) == gcd) {
				ll sum = A + B;
				if (sum < minsum) {
					minA = A;
					minB = B;
					minsum = sum;
				}
			}
		}
	}

	cout << minA << " " << minB;
	return 0;
}