취미로 코딩하기

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

이번에 볼 문제는 백준 23604번 문제인 Chinese Remainder Theorem이다.
문제는 아래 링크를 확인하자.

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

$a_i$와 $b_i$가 법 $m$에 대해 합동이라는 것은 $m$이 $a_i$와 $b_i$의 차의 약수라는 것과 동치임을 관찰하자.

따라서 모든 $i$에 대하여 $a_i$와 $b_i$가 법 $m$에 대해 합동이라는 것은 $m$이 모든 $a_i$와 $b_i$의 차의 약수라는 것과 같고, 이는 $a_i$와 $b_i$의 차들의 공약수와 같게 된다. 따라서 이 문제는 이러한 공약수들 중 가장 큰 수, 즉 최대공약수를 구하는 것으로 해결할 수 있다.

두 수의 최대공약수는 유클리드 호제법(Euclidean Algorithm)을 이용해 계산할 수 있다. 여러 수의 최대공약수는 둘씩 최대공약수를 구하는 것을 반복하는 것으로 구할 수 있다.

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

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

ll gcd(ll x, ll y) {
	if (y) return gcd(y, x % y);
	return x;
}

int N; ll ans;
ll A[100000], B;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> A[i];
	cin >> B; ans = abs(A[0] - B);
	for (int i = 1; i < N; i++) {
		cin >> B;
		ans = gcd(ans, abs(A[i] - B));
	}

	cout << ans;
}