結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー codershifth
提出日時 2016-01-13 22:46:35
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,151 bytes
コンパイル時間 1,261 ms
コンパイル使用メモリ 164,332 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-19 18:27:28
合計ジャッジ時間 1,992 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

template<typename T>
T gcd(T a, T b)
{
        if ( std::abs(a) < std::abs(b) )
            std::swap(a,b);
        if ( b == 0 )
            return a;
        return gcd(b, a%b);
}
template<typename T>
T extgcd(T a, T b, T &x, T &y)
{
    T d = a;
    if (b != 0)
    {
        d = extgcd(b, a%b, y, x);
        y -= (a/b)*x;
    }
    else
    {
        x=1; y=0;
    }
    return d;
}
//  mod M の逆元を求める
template<typename T>
T mod_inverse(T a, T M)
{
        T x, y;
        T d = extgcd(a, M, x, y);
        assert(d == 1);
        return (M + x%M) % M;
}
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;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new ChiniseStyleEasy();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0