-
2436. 공약수Algorithm/Baekjoon 2023. 2. 11. 01:38
하나를 놓쳐서 시간이 걸린 문제
먼저 A = a*gcd, B = b*gcd라고 놓고, lcm*gcd = A*B니까 식 전개해서
a*b = lcm//gcd여야 한다는 것까지는 파악을 했고
이 때 합이 최소가 되는 두 수여야 하기에 a와 b가 가장 가까운 숫자여야 한다는 것까지는 알았다.
그래서 a*b의 제곱근 근처에서 탐색을 시작해서 a와 b를 찾아내도록 했는데...
a와 b가 서로소여야 한다는 것을 놓쳐서 바로 정답을 맞추지는 못했다.
a와 b가 서로소가 아니라면 gcd가 해당 값이 아니게 되기 때문에 짚고 넘어가야 하는 조건이다.
놓치지 말기!
import sys input = sys.stdin.readline def calc_gcd(a, b) : if b == 0 : return a return calc_gcd(b, a%b) gcd, lcm = map(int, input().split()) ab = lcm//gcd a = 0 b = 0 for d in range(int(ab**(1/2)), 0, -1) : if ab%d == 0 : a = d b = ab//a if calc_gcd(a, b) == 1 : print(a*gcd, b*gcd) break
'Algorithm > Baekjoon' 카테고리의 다른 글
1018. 체스판 다시 칠하기 (0) 2023.02.20 20302. 민트초코 (0) 2023.02.14 16563. 어려운 소인수분해 (0) 2023.02.10 2960. 에라토스테네스의 체 (0) 2023.02.09 11866. 요세푸스 문제 (0) 2023.02.09