[백준 2436] 공약수 [C]

백준 - 2436

---

풀이

a*b = gcd(a,b)*lcm(a,b)이므로 양변의 약수가 같다는 점을 이용해 풀이했다.

---

소스코드

#include <stdio.h>
int gcd(int a, int b){
    return b ? gcd(b, a%b) : a;
}
int main(){
    int A, B, a, b;
    scanf("%d %d", &A, &B);
    B /= A;
    for (int i = 1; i*i <= B; i++)
        if (B % i == 0 && gcd(i, B/i) == 1){
            a = i;
            b = B/i;
        }
    printf("%d %d", a*A, b*A);	
}

---

출처

2436번: 공약수