結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー yuu_w
提出日時 2024-06-28 15:52:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,146 bytes
コンパイル時間 2,108 ms
コンパイル使用メモリ 196,908 KB
最終ジャッジ日時 2025-02-22 00:48:44
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << (x) << endl
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;

struct IOSetup
{
	IOSetup()
	{
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout << fixed << setprecision(16);
		cerr << fixed << setprecision(16);
	}
} iosetup;

template <typename T1, typename T2>
ostream &operator <<(ostream &os, const pair<T1, T2> &p)
{
	os << p.first << " " << p.second;
	return os;
}

template <typename T1, typename T2>
istream &operator >>(istream &is, pair<T1, T2> &p)
{
	is >> p.first >> p.second;
	return is;
}

template <typename T>
ostream &operator <<(ostream &os, const vector<T> &v)
{
	for(int i = 0; i < (int) v.size(); i++) os << v[i] << (i+1 == (int) v.size() ? "" : " ");
	return os;
}

template <typename T>
istream &operator >>(istream &is, vector<T> &v)
{
	for(int i = 0; i < (int) v.size(); i++) is >> v[i];
	return is;
}

template <typename T> bool chmax(T &a, const T &b) { if(a < b) { a = b; return true; } return false; }
template <typename T> bool chmin(T &a, const T &b) { if(a > b) { a = b; return true; } return false; }

////////////////////////////////////////////////////////

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;
}

template<typename T>
T CRT(const vector<T> &r, const vector<T> &m)
{
	T r0 = 0, m0 = 1;
	for(int i = 0; i < (int) r.size(); i++)
	{
		T r1 = r[i], m1 = m[i];
		if(m0 < m1)
		{
			swap(r0, r1);
			swap(m0, m1);
		}
		if(m0 % m1 == 0)
		{
			if(r0 % m1 != r1) return 0;
			continue;
		}
		T x, y;
		T g = extgcd(m0, m1, x, y);
		T u = m1/g;
		if((r1-r0) % g != 0) return 0;
		T lcm = m0*m1/g;
		T t = (r1-r0)/g*x % u;
		r0 += m0*t;
		m0 = lcm;
		if(r0 < 0) r0 += lcm;
	}
	return r0;
}

int main()
{
	vector<ll> r(3), m(3);
	for(int i = 0; i < 3; i++) cin >> r[i] >> m[i];
	cout << (CRT(r, m) == 0 ? -1 : CRT(r, m)) << endl;
}
0