사용자 도구

사이트 도구


ps:problems:boj:11414

LCM

ps
링크https://www.acmicpc.net/problem/11414
출처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()

토론

댓글을 입력하세요:
G K Q R Y
 
ps/problems/boj/11414.txt · 마지막으로 수정됨: 2022/06/11 02:59 저자 teferi