[백준 11414] LCM [C]

백준 - 11414

---

풀이

gcd(x, y) = gcd(x-y, y)임을 이용해 풀이했다.

A < B일때, gcd(A+N, B+N) = gcd(A+N, B-A)이므로, B-A의 약수를 이용해야 한다.

B-A의 약수가 1, 2, 3, 6

1~ B-A범위를 모두 탐색하면 시간초과가 발생하므로 다른 방법을 생각해야된다.

위의 예시에서 알 수 있듯이, 시작값(X)을 기준으로 X+N이 B-A로 나누어 떨어질 때 X~(X+B-A)구간에서 가장 작은 LCM값을 가진다는 점을 알 수 있다.

 

X+N이 B-A로 나누어 떨어진다는 것은, B-A의 약수로도 나누어 떨어지는 것을 의미한다.

따라서, A가 B-A의 약수로 나누어 떨어지지 않을 때, N번째 수를 생성 후 LCM을 계산해 가장 작은 N값을 구하면 된다.

---

소스코드

#include <stdio.h>
#define ll long long
int facter[100];
int gcd(int a, int b){
    return b ? gcd(b, a%b) : a;
}
ll lcm(ll a, int b){
    return a*b/gcd(a, b);
}
int main(){
    int A, B;
    scanf("%d %d", &A, &B);
	
    if (A == B) return !printf("1");
    if (A > B){
        int swap = A;
        A = B;
        B = swap;
    }
	
    int idx = 0, diff = B-A, result = diff;
    for (int i = 1; i*i <= diff; i++)
        if (diff % i == 0){
            facter[idx++] = i;
            if (diff/i != i) facter[idx++] = diff/i;
        }
	
    ll min = 1e18, N;
    for (int i = 0, f; i < idx; i++){
        if (A % (f = facter[i])){
            N = f- A%f;
            ll temp = lcm(A+N, B+N);
            if (temp < min){
                min = temp;
                result = N;
            }else if (min == temp && N < result) result = N;
        }
    }
    printf("%d", result);
}

---

출처 및 참고자료

11414번: LCM

유클리드 호제법(Euclid's GCD Algorithm)