일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
30 | 31 |
- shake!
- expand item
- Codeforces Round 831 (Div. 1 + Div. 2)
- 앳코더
- 기본키 변경
- 1557
- 레지스터
- django
- idpiframe_initialization_failed
- vue-google-login
- Flutter
- 카카오 로그인
- vue3
- 코드포스
- Round 866
- E - Hanging Hearts
- 카카오 API
- 인하대 프로그래밍 경진대회
- Good Bye 2022: 2023 is NEAR
- 리버싱
- 2022
- Graph Cost
- iupc
- 밑바닥부터 시작하는 딥러닝 1
- dart
- Hello 2023
- 알고리즘 대회
- Div. 2
- 넥토리얼
- list_display
- Today
- Total
pseong
중국인의 나머지 정리 본문
중국인의 나머지 정리가 무엇을 의미하는지는 나무위키에 잘 설명이 되어있다.
중국인의 나머지 정리 - 나무위키 (namu.wiki)
보통 중국인의 나머지 정리라 하면 모든 m이 서로소여야 한다.
하지만 서로소가 아닐때도 해를 구하고 싶을때가 있을 것이다.
이런 경우에는 두 개의 합동식을 하나로 합친다.
계속 이렇게 합쳐 주다가 마지막 한 개의 합동식만 남았을 때 답을 구해주면 해결된다.
따라서 두 개의 합동식을 합치는 방법만 알면 문제를 풀 수 있다.
x ≡ a1 ( mod x1 )
x ≡ a2 ( mod x2 )
먼저 이렇게 두 개의 합동식이 있다고 하자.
g = gcd(x1, x2) 라고 하자.
아래 두 개의 식이 성립하므로
x ≡ a1 (mod g)
x ≡ a2 (mod g)
다음 식이 성립한다고 할 수 있다.
a1 ≡ a2 (mod g)
만약 이 식이 성립하지 않는다면 두 개의 합동식을 합칠 수 없는 것이고 그렇게 되면 답은 존재하지 않는 것이다.
s와 t를 확장 유클리드 알고리즘을 이용하여 구한 값이라고 하자.(m1/g) * s + (m2/g) * t = gcd(m1/g, m2/g) = 1 (식 1)
합친 합동식을 다음과 같이 표현하자.x ≡ a1*(m2/g)*t + a2*(m1/g)*s (mod (m1/g)*m2) (식 2)
(식 1) 를 사용하여 (식 2)의 (m1/g) * s 를 1 - (m2/g) * t 로 치환하면 m2으로 나눈 나머지가 a2인 것을 확인 할 수 있다.마찬가지로 (식 2)의 (m2/g) * t를 1 - (m1/g) * s로 치환하면 m1으로 나눈 나머지가 a1인 것을 확인 할 수 있다.
이렇게 합동식을 순차적으로 확인하면서 두 개의 식을 하나로 합쳐가면 결국 마지막엔 합동식 하나만 나올 것이다.마지막에 나온 합동식이 x = a (mod lcm) 이라 한다면 답은 a가 될 것이다.
// input: {{a1, m1}, {a2, m2}, ...} : x = a1 (mod m1), y = a2 (mod m2)
// output: {ans, lcm}
pair<ll, ll> crt(vector<pair<ll, ll>> v) {
int n = v.size();
auto [a1, m1] = v[0];
a1 %= m1;
for (int i=1; i<n; i++) {
auto [a2, m2] = v[i];
ll g = __gcd(m1, m2);
if (a1%g != a2%g) return {-1, -1};
auto [s, t, G] = xgcd(m1/g, m2/g);
i128 mod = (i128)m1 / g * m2;
a1 = ((i128)a1 * (m2/g) % mod) * t % mod + ((i128)a2 * (m1/g) % mod) * s % mod;
a1 = (a1 + mod) % mod;
m1 = mod;
}
return {a1, m1};
}
번외로 xgcd는 확장 유클리드 해 구하는 코드입니다.
// ouput: a*s + b*t = gcd(a, b)
tuple<ll, ll, ll> xgcd(ll a, ll b) {
ll s, t;
ll r1 = a, r2 = b, s1 = 1, s2 = 0, t1 = 0, t2 = 1;
ll r, q;
while (r2) {
q = r1 / r2;
r = r1 % r2;
r1 = r2, r2 = r;
s = s1 - q * s2;
s1 = s2, s2 = s;
t = t1 - q * t2;
t1 = t2, t2 = t;
}
s = s1;
t = t1;
if (s <= 0) {
s += b;
t -= a;
}
return {s, t, r1};
}
'알고리즘 > 알고리즘 이론' 카테고리의 다른 글
제 1종, 2종 스털링 수 (0) | 2022.07.14 |
---|---|
세그먼트 트리 (구간 트리), 느리게 갱신되는 세그먼트 트리 (Lazy Propagation) (0) | 2022.03.16 |