結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー leaf_1415
提出日時 2019-09-24 21:28:26
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,641 bytes
コンパイル時間 582 ms
コンパイル使用メモリ 57,080 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-19 18:35:32
合計ジャッジ時間 4,485 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <utility>
#define llint long long

using namespace std;
typedef pair<llint, llint> P;

llint gcd(llint a, llint b)
{
	if(b == 0) return a;
	return gcd(b, a%b);
}

//ax+by = gcd(a, b)を満たす(x, y)を求めgcd(a, b)を返す
llint extgcd(llint a, llint b, llint &x, llint &y)
{
	if(b == 0){
		x = 1, y = 0;
		return a;
	}
	llint xx, yy;
	llint d = extgcd(b, a%b, xx, yy);
	x = yy, y = xx-(a/b)*yy;
	return d;
}

//a^{-1} (mod m)を求める。存在しない場合(gcd(a, m)!=1)は-1を返す
llint mod_inverse(llint a, llint m)
{
	llint x, y;
	if(extgcd(a, m, x, y) != 1) return -1;
	return (x%m + m) % m;
}

//ax = b (mod m)を満たすx(mod m/gcd(a, m))を求める。存在しない場合(b%gcd(a, m)!=0)は(0, -1)を返す
P congruence(llint a, llint b, llint m)
{
	llint d = gcd(a, m);
	if(b % d) return make_pair(0, -1);
	a /= d, b /= d, m /= d;
	return make_pair(b * mod_inverse(a, m) % m, m);
}

//連立合同方程式a_i*x = b_i (mod m_i)(i = 1, 2, ..., n)の解(x, M)を求める。存在しない場合(0, -1)を返す
P SimultaneousCongruence(llint a[], llint b[], llint m[], llint n)
{
	llint x = 0, M = 1;
	for(int i = 1; i <= n; i++){
		P res = congruence(a[i]*M, (b[i]-a[i]*x%m[i]+m[i])%m[i], m[i]);
		if(res.second == -1) return res;
		x += M*res.first, M *= res.second;
	}
	return make_pair(x, M);
}

llint x[3], y[3], z[3];

int main(void)
{
	for(int i = 1; i <= 3; i++) cin >> x[i] >> y[i], z[i] = 1;
	P res = SimultaneousCongruence(z, x, y, 3);
	if(res.second == -1) cout << -1 << endl;
	else{
		if(res.first == 0) res.first += res.second;
		cout << res.first << endl;
	}
	
	return 0;
}
0