No.186 中華風 (Easy) - shifth’s blog

中国剰余定理を使う問題。
蟻本に乗ってたライブラリを使ってしまったが、これくらい自力でかけないとダメかなぁ...。
正整数を出力するので 0 や負は変換しないとダメ。

template <typename T>
std::pair<T,T> linear_congruence(
    const std::vector<T> &A,
    const std::vector<T> &B,
    const std::vector<T> &M)
{
        T x = 0, m = 1;
        for (int i = 0; i < A.size(); ++i)
        {
            T a = A[i] * m;
            T b = B[i] - A[i] * x;
            T d = gcd(M[i], a);
            if (b % d) // solution does not exist.
                return std::make_pair(0, -1);
            T md = M[i]/d;
            T t = b / d * mod_inverse(a / d, M[i] / d) % (M[i] / d);
            x = x + m * t;
            m *= M[i] / d;
        }
        return std::make_pair(x % m, m);
}
class ChiniseStyleEasy
{
public:
    void solve(void)
    {
        vector<ll> x(3);
        vector<ll> y(3);

        REP(i, 3)
            cin>>x[i]>>y[i];
        vector<ll> a(3,1);
        ll z,m;
        tie(z,m) = linear_congruence(a,x,y);

        if (m < 0)
        {
            cout<<-1<<endl;
            return;
        }
        ll Y = max({y[0],y[1],y[2]});

        if ( z < 0 )
            z += (-z/m+1)*m;
        ll X = Y/m*m + z;
        if ( X == 0 )
            cout<<m<<endl;
        else
            cout<<X<<endl;
    }
};