[12971] 숫자 놀이

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

12971번: 숫자 놀이

중국인의 나머지 정리

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

ll minv(ll a, ll b) {

    if (a == 0 && b == 1) return 0;

    if (a == 1) return 1;

    return b - minv(b % a, a) * b / a;

}

// x == A.first (mod A.second)

// x == B.first (mod B.second)

// returns solution as X == ans.first (mod ans.second)

// if no solution, returns (-1, -1)

// always a good idea to keep 0 <= ?.first < ?.second (for ? : A, B, ans)

pair<ll, ll> crt(pair<ll, ll> A, pair<ll, ll> B) {

    if (A.second == -1 || B.second == -1) return make_pair(-1, -1);

    if (A.second == 1) return B;

    if (B.second == 1) return A;

    ll g = gcd(A.second, B.second);    // gcd

    ll l = A.second * (B.second / g);  // lcm

    if ((B.first - A.first) % g != 0)

        return make_pair(-1, -1);  // no solution case

    ll a = A.second / g;

    ll b = B.second / g;

    ll mul = (B.first - A.first) / g;

    mul = (mul * minv(a % b, b)) % b;     // this is now t

    ll ret = (mul * A.second + A.first);  // n_1 t + a_1

    ret %= l;

    ret = (ret + l) % l;  // take modulos

    return make_pair(ret, l);

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    ll p1, p2, p3, x1, x2, x3;

    cin >> p1 >> p2 >> p3 >> x1 >> x2 >> x3;

    // N==x1(mod p1)

    // N==x2(mod p2)

    // N==x3(mod p3)

    auto f = crt({x1, p1}, {x2, p2});

    auto g = crt({f.first, f.second}, {x3, p3});

    if (f.first == -1 or g.first == -1) {

        cout << -1;

        return 0;

    }

    if (0 < g.first and g.first < 1'000'000'000)

        cout << g.first;

    else

        cout << -1;

    return 0;

}

---

https://github.com/rkm0959/Number_Theory_in_CP_PS/blob/main/3.%20%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98%20%EB%82%98%EB%A8%B8%EC%A7%80%20%EC%A0%95%EB%A6%AC/CRT.cpp