結果

問題 No.186 中華風 (Easy)
ユーザー leaf_1415leaf_1415
提出日時 2019-09-24 21:26:29
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 1,589 bytes
コンパイル時間 564 ms
コンパイル使用メモリ 57,780 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-19 09:05:53
合計ジャッジ時間 3,994 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
権限があれば一括ダウンロードができます

ソースコード

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 cout << res.first << endl;
	
	return 0;
}
0