최소 공배수(최대 공약수) 찾기 - 유클리드 호제법 (나머지 정리)
결론 먼저 def gcd(a, b): while b != 0: a, b = b, a % b return a def lcm(a, b): return a * b // gcd(a, b) test_number = int(input()) for _ in range(test_number): number_1, number_2 = map(int, input().split()) print(lcm(number_1, number_2)) 원리 유클리드 호제법 a > b 일 때, a % b = r 이면 a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다 나머지 정리 a % b = r 이면, a = bq + r (q는 임의의 몫) 만약 d가 a와 b의 공약수 라면, d는 r도 나눌 수 있다 좌변 a % d = 0 우변 bq ..
2024. 1. 20.
