ps:problems:boj:11414
LCM
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 11414 |
문제명 | LCM |
레벨 | 골드 1 |
분류 |
정수론 |
시간복잡도 | O(sqrt(n)) |
인풋사이즈 | n<=10^9 |
사용한 언어 | Python |
제출기록 | 32952KB / 72ms |
최고기록 | 56ms |
해결날짜 | 2022/06/10 |
풀이
- gcd(x,y) = gcd(x-y, x)라는 점을 이용하자. 그러면 gcd(A+n, B+n) = gcd(A-B, B+n)이 되고, 이값은 (A-B)의 약수중 하나이다.
- 그러면 A-B의 모든 약수 d대해서 d|B+n, d|A+n 이 되는 n을 찾을수 있다.
코드
"""Solution code for "BOJ 11414. LCM".
- Problem link: https://www.acmicpc.net/problem/11414
- Solution link: http://www.teferi.net/ps/problems/boj/11414
Tags: [Number theory]
"""
import math
INF = float('inf')
def all_divisors(n):
ret = [i for i in range(1, math.isqrt(n) + 1) if n % i == 0]
rev = ret[-2::-1] if ret[-1] * ret[-1] == n else ret[::-1]
return ret + [n // x for x in rev]
def main():
A, B = [int(x) for x in input().split()]
if A == B:
print('1')
return
answer = (INF, None)
for d in all_divisors(abs(A - B)):
n = d - A % d
answer = min(answer, ((A + n) * (B + n) // d, n))
print(answer[1])
if __name__ == '__main__':
main()
ps/problems/boj/11414.txt · 마지막으로 수정됨: 2022/06/11 02:59 저자 teferi
토론