취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11414번 문제인 LCM이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/11414

A+N과 B+N의 최소공배수는 두 수의 곱을 A+N과 B+N의 최대공약수로 나눈 것과 같다.

N에 상관없이 계산하기 위해 관찰을 해보면, gcd(A+N,B+N) = gcd(A+N, abs(A-B)) 라는 점을 발견할 수 있다.

위 식에 따라, gcd(A+N,B+N)은 abs(A-B)의 약수 K들일 수밖에 없다는 것을 알 수 있다.

A+N과 B+N의 최대공약수가 K가 되게끔 하는 N의 최솟값이 항상 존재하므로, 그러한 N을 찾아 abs(A-B)의 약수 K 각각에 대하여 답을 비교해나가는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

vector<int> divisors;

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

	int A, B; cin >> A >> B;
	if (A == B) {
		cout << 1;
		return 0;
	}

	int diff = abs(A - B);
	int i = 1;
	for (; i * i < diff; i++) {
		if (diff % i == 0) {
			divisors.emplace_back(i);
			divisors.emplace_back(diff / i);
		}
	}
	ll val = 4000000000000000001LL;
	int ans = 1000000001;
	if (i * i == diff) divisors.emplace_back(i);
	sort(divisors.begin(), divisors.end());
	for (auto d : divisors) {
		int r = A % d;
		r = d - r;
		ll AA = A + r, BB = B + r;
		ll tmp = AA * (BB / d);
		if (tmp < val) {
			val = tmp;
			ans = r;
		}
	}

	cout << ans;
}