BOJ 11414 - LCM 링크
(2024.03.26 기준 G1)

문제

두 자연수 $A$, $B$가 주어질 때, $A + N$과 $B + N$의 최소공배수가 최소가 되는 자연수 $N$을 출력

알고리즘

정수론

풀이

$\gcd(A, B) = \gcd(A, B-A) (A<B)$이다. 이것을 모른다면 꼭 외워두자.

아무튼 위 식을 이용해서 $\gcd(A+N, B+N) = \gcd(A+N, B-A) (A<B)$로 만들 수 있다.
$A+N$과 $B+N$의 최대공약수는 $B-A$의 약수 중 하나가 된다. 그럼 일단 $B-A$의 약수를 구해보자. 이는 따로 설명하지 않겠다.

$B-A$의 약수들을 $d_1$, $d_2$, $\dots$ 라고 하자.
만약 $\gcd(A+N, B-A)$의 최대공약수가 $d_i$이라면? $A \bmod d_i = r_i$라고 하자. $(A+N) \bmod di = 0$이 되어야 한다. $A$는 $d_i$로 나누어 떨어지기까지 $d_i-r_i$가 부족하기 때문에, $N$은 $d_i-r_i$가 된다.

이렇게 구한 $\gcd(A+N, B+N) = d_i$로 최소공배수를 구해서 정답을 갱신하면 된다. 최소공배수는 두 수의 곱을 최대공약수로 나누면 구할 수 있다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll inf = LLONG_MAX;

// 유클리드 호제법
ll gcd(ll a, ll b){
    ll r = a % b;
    if (r) return gcd(b, r);
    return b;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll A, B; cin >> A >> B;

    // 두 수가 같으면 정답은 1이 된다.
    if (A == B){
        cout << 1;
        return 0;
    }

    // 일반화를 위해 A < B로 맞춰준다.
    if (A > B) swap(A, B);

    /* gcd(A, B) = gcd(A, B-A) (A<B)
    gcd(A+N, B+N) = gcd(A+N, B-A) (A<B)

    (B-A)의 약수를 d1, d2, ... 라고 하자.
    A % di = ri, gcd(A+N, B-A)의 최대공약수가 di라고 하면
    (A+N) % di = 0이 되어야 하고, A는 di로 나누어 떨어지기 까지 di-ri가 부족하기 때문에
    N은 di-ri가 된다. 이렇게 구한 gcd(A+N, B+N) = di로 lcm을 구해서 정답을 갱신하면 된다. */

    // (B-A)의 약수
    set<ll> divisors;
    for (int i = 1, lim = sqrt(B - A); i <= lim; i++) if (!((B - A) % i)){
        divisors.insert(i);
        divisors.insert((B - A) / i);
    }

    pll ans = {inf, -1};
    for (ll d: divisors){
        ll r = A % d;
        ll N = d - r;
        ll lcm = (A + N) * (B + N) / d; // 두 수를 곱해 최대공약수로 나누면 최소공배수가 된다.
        ans = min(ans, {lcm, N});
    }

    cout << ans.second;
}

• Python

import sys; input = sys.stdin.readline
from math import inf

# 유클리드 호제법
def gcd(a, b):
    r = a % b
    if r:
        return gcd(b, r)
    return b

A, B = map(int, input().split())

# 두 수가 같으면 정답은 1이 된다.
if A == B:
    print(1)
    exit()

# 일반화를 위해 A < B로 맞춰준다.
if A > B:
    A, B = B, A

''' gcd(A, B) = gcd(A, B-A) (A<B)
gcd(A+N, B+N) = gcd(A+N, B-A) (A<B)

(B-A)의 약수를 d1, d2, ... 라고 하자.
A % di = ri, gcd(A+N, B-A)의 최대공약수가 di라고 하면
(A+N) % di = 0이 되어야 하고, A는 di로 나누어 떨어지기 까지 di-ri가 부족하기 때문에
N은 di-ri가 된다. 이렇게 구한 gcd(A+N, B+N) = di로 lcm을 구해서 정답을 갱신하면 된다. '''

# (B-A)의 약수
divisors = set()
for i in range(1, int((B - A) ** 0.5) + 1):
    if not (B - A) % i:
        divisors.add(i)
        divisors.add((B - A) // i)

ans = (inf, -1)
for d in divisors:
    r = A % d
    N = d - r
    lcm = (A + N) * (B + N) // d # 두 수를 곱해 최대공약수로 나누면 최소공배수가 된다.
    ans = min(ans, (lcm, N))

print(ans[1])