728x90
풀이
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번: 공약수
첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0
www.acmicpc.net
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
[백준 15897] 잘못 구현한 에라토스테네스의 체 [C] (0) | 2021.09.02 |
---|---|
[백준 1188] 음식 평론가 [C] (0) | 2021.09.02 |
[백준 1987] 알파벳 [C] (0) | 2021.09.01 |
[백준 11790] Primorial vs LCM [C] (0) | 2021.08.31 |
[백준 11414] LCM [C] (0) | 2021.08.31 |