백준 11414번: LCM

[www.acmicpc.net/problem/11414]

#풀이

- lcm(A+N, B+N)가 최소가 될 때는 |A-B| 의 약수가 gcm(A+N, B+N)일 때이다.

1. |A-B|의 약수를 구한다.

2. (A+N)%약수 == (B+N)%약수 == 0 을 만족하는 N을 구한다.

3. 2.를 만족하는 N과 모든 약수에서 lcm(A+N,B+N)이 최소가 되는 N을 구한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

from math import gcd #모든 약수 구하기 def measure(a):     divs=[]     for i in range(1,int(a**0.5)+1):         if a%i==0:             divs.append(i)             if i!=a//i:                 divs.append(a//i)     return divs #최소공배수 구하기 def lcm(x,y):     return x*y/gcd(x,y) def sol(x,y):     a=abs(x-y)     if a == 0:         return 1     min_lcm=10**19     N=10**10     for i in measure(a):         tmp=i-x%i         if min_lcm > lcm(x+tmp,y+tmp):             min_lcm=lcm(x+tmp,y+tmp)             N=tmp         elif min_lcm == lcm(x+tmp,y+tmp):             N=min(tmp,N)     return N x,y=map(int,input().split()) print(sol(x,y))

cs