結果

問題 No.186 中華風 (Easy)
ユーザー ningenMeningenMe
提出日時 2019-05-02 03:49:07
言語 C++11
(gcc 11.4.0)
結果
WJ  
(最新)
AC  
(最初)
実行時間 -
コード長 3,550 bytes
最終ジャッジ日時 2023-09-27 00:55:03
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

const ll MOD = (ll)1e9 + 7;
const ll MOD2 = 998244353;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e15;
const long double PI = 3.1415926535897932384626433;

template<typename T> vector<T> make_v(size_t N,T init){return vector<T>(N,init);}
template<typename... T> auto make_v(size_t N,T... t){return vector<decltype(make_v(t...))>(N,make_v(t...));}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max<T>(a,b);}
template <class T> void chmin(T& a, const T b){a=min<T>(a,b);}
void YN(bool flg) {cout << ((flg) ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << ((flg) ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << ((flg) ? "yes" : "no") << endl;}

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
		x = 1, y = 0;
		return a;
	}
	else {
		long long d = extGCD(b, a%b, y, x);
		y -= a / b * x;
		return d;
	}
}


//Greatest Common Divisor
long long GCD(long long a, long long b) {
    return ((b == 0) ? a : GCD(b, a % b));
}

//Least Common Multiple
long long LCM(long long a, long long b) {
    return ((a*b == 0) ? 0 : (a / GCD(a, b)*b));
}


// 答えを x ≡ r (mod. M) として、{r, M} をリターン, 存在しない場合は {0, -1} をリターン
pair<long long, long long> Chinese_Remainder_Theorem(const vector<long long> &b, const vector<long long> &m) {
    long long r = 0, M = 1;
    for (int i = 0; i < b.size(); ++i) {
        long long p, q;
        long long d = extGCD(M, m[i], p, q);
        if ((b[i] - r) % d != 0) return {0, -1};
        long long tmp = (b[i] - r) / d * p % (m[i]/d);
        r += M * tmp;
        M *= m[i]/d;
    }
    return {(r%M+M)%M, M};
}

int main() {
	V<ll> b(3),m(3);
	REP(i,3) cin >> b[i] >> m[i];
	auto p = Chinese_Remainder_Theorem(b,m);
	ll ans;
	int flg = 1;
	for(int i = 0; i < 3; ++i) if(b[i]) flg = 0;
	if(p.second == -1) ans = -1;
	else if(flg) ans = p.second;
	else ans = p.first;
	cout << ans << endl;
	
	return 0;
}
0