중국인의 나머지 정리

중국인의 나머지 정리가 무엇을 의미하는지는 나무위키에 잘 설명이 되어있다.

중국인의 나머지 정리 - 나무위키 (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};
}