테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== LCM ======

===== 풀이 =====
  * 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을 찾을수 있다. 

===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_1}}