結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー morimario
提出日時 2021-05-06 20:30:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,010 bytes
コンパイル時間 2,284 ms
コンパイル使用メモリ 204,776 KB
最終ジャッジ日時 2025-01-21 07:47:22
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘pll my_crt(vl, vl)’:
main.cpp:150:32: warning: ‘z’ may be used uninitialized [-Wmaybe-uninitialized]
  150 |                 return pll(0, 1);
      |                                ^
main.cpp:148:15: note: ‘z’ was declared here
  148 |         ll y, z;
      |               ^
main.cpp:150:32: warning: ‘y’ may be used uninitialized [-Wmaybe-uninitialized]
  150 |                 return pll(0, 1);
      |                                ^
main.cpp:148:12: note: ‘y’ was declared here
  148 |         ll y, z;
      |            ^

ソースコード

diff # 

// 研究用ファイル

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>; using pii = pair<int, int>;
using vl = vector<ll>; using pll = pair<ll, ll>;

ll my_gcd(ll a, ll b) {
	a = abs(a); b = abs(b);
	if (a < b) swap(a, b);
	if (a == 0) return 0; // (0,0)

	// recursive
	if (b == 0) return a;
	// ll r = a % b;
	return my_gcd(b, a % b);

	// not recursive
	// while (b > 0) {
	// 	ll r = a % b; // ll q = a / b;
	// 	a = b;
	// 	b = r;
	// }
	// return a;
}

ll my_gcd(vl a) {
	ll g = 0;
	for (ll a_i : a) g = my_gcd(g, a_i);
	return g;
}

pll ext_gcd(ll _a, ll _b) {
	vl a = {abs(_a), abs(_b)};
	if (a[0] < a[1]) swap(a[0], a[1]);
	if (a[0] == 0) return pll(0, 0); // (0,0)
	else if (a[1] == 0) { // (a,0)
		ll x = 1, y = 0;
		if (abs(_a) < abs(_b)) swap(x, y);
		if (_a < 0) x = -x;
		if (_b < 0) y = -y;
		return pll(x, y);
	}

	int n = 2; // number of terms

	while (a[n - 1] > 0) {
		a.push_back(a[n - 2] % a[n - 1]);
		++n;
	}
	// for (ll r : a) cout << r << ", "; cout << endl;

	ll x = 0, y = 1;
	// printf("(x, y) = (%lld, %lld)\n", x, y);
	for (int i = n - 2; i >= 2; --i) {
		ll q = a[i - 2] / a[i - 1];
		ll temp_x = y;
		ll temp_y = x - q * y;
		x = temp_x;
		y = temp_y;
		// cout << q << endl; printf("(x, y) = (%lld, %lld)\n", x, y);
	}

	if (abs(_a) < abs(_b)) swap(x, y);
	if (_a < 0) x = -x;
	if (_b < 0) y = -y;

	// assert(_a * x + _b * y == my_gcd(_a, _b)); //

	return pll(x, y);
}

vl ext_gcd(vl a) {
	int n = a.size();
	vl x(n);
	ll g;
	if (n == 0) {
		return x;
	} else if (n == 1) {
		if (a[0] > 0) x[0] = 1;
		else if (a[0] < 0) x[0] = -1;
		return x;
	} else if (n >= 2) {
		tie(x[0], x[1]) = ext_gcd(a[0], a[1]);
		g = my_gcd(a[0], a[1]);
	}

	// cout << "g: " << g << endl;
	// cout << "x: "; for (int i = 0; i < n; ++i) cout << x[i] << ", "; cout << endl;
	
	for (int i = 2; i < n; ++i) {
		ll X, Y;
		tie(X, Y) = ext_gcd(g, a[i]);
		for (int j = 0; j < i; ++j) {
			x[j] *= X;
		}
		x[i] = Y;
		g = my_gcd(g, a[i]);
		// printf("(X, Y) = (%lld, %lld)\n", X, Y);
		// cout << "g: " << g << endl;
		// cout << "x: "; for (int i = 0; i < n; ++i) cout << x[i] << ", "; cout << endl;
	}

	return x;
}

// mod m での a の逆元の拡張: a * x = g = gcd(a, m) なる0 <= x < m
// a*x ≡ g mod m
// a*x + m*y ≡ g
ll my_inv(ll a, ll m) {
	assert(m >= 1);
	ll x = ext_gcd(a, m).first;
	if (x < 0) x += m;
	return x;
}


// 合同方程式 x ≡ r[i] mod m[i] の解を x ≡ y mod z として、(y,z)を返す
// m[i] >= 1
// n = 2
// g = gcd(m1,m2) = 1 のとき、
// m1 * x1 + m2 * x2 = 1 となるx1,x2を見つけ、
// x = r1*m2*x2 + r2*m1*x1 とすればよい
// g > 1 のとき、
// r1 ≡ r2 (≡ r0) mod g を前提として、
// s1 = (r1 - r0) / g, s2 = (r2 - r0) / g とする

pll my_crt(ll r1, ll r2, ll m1, ll m2) {
	assert(m1 >= 1); assert(m2 >= 1);
	ll g = my_gcd(m1, m2), l = m1 / g * m2;
	ll r = r1 % g;
	if ((r2 - r) % g != 0) return pll(0, 0);
	ll s1 = (r1 - r) / g, s2 = (r2 - r) / g;
	ll n1 = m1 / g, n2 = m2 / g;
	ll y1, y2;
	tie (y1, y2) = ext_gcd(n1, n2);
	ll y = (s1 * n2 * y2 + s2 * n1 * y1) % (l / g);
	// if (y < 0) y += l / g;
	ll x = (y * g + r) % l;
	if (x < 0) x += l;
	return pll(x, l);
}

pll my_crt(vl r, vl m) {
	int n = r.size();
	assert(m.size() == n);
	ll y, z;
	if (n == 0) {
		return pll(0, 1);
	} else if (n == 1) {
		assert(m[0] >= 1);
		ll y = r[0] % m[0], z = m[0];
		if (y < 0) y += z;
		return pll(y, z);
	} else if (n >= 2) {
		tie(y, z) = my_crt(r[0], r[1], m[0], m[1]);
	}
	for (int i = 2; i < n && z > 0; ++i) {
		tie(y, z) = my_crt(y, r[i], z, m[i]);
	}
	return pll(y, z);
}

// test

void test_my_gcd() { // ext_gcd
	ll a, b;
	a = rand(); if (rand() % 2) a = -a;
	b = rand(); if (rand() % 2) b = -b;
	cin >> a >> b;

	printf("(a, b) = (%lld, %lld)\n", a, b);
	printf("%lld %lld %lld\n", a, b, my_gcd(a, b));
	ll x, y; tie(x, y) = ext_gcd(a, b);
	printf("gcd(%lld, %lld) = %lld, (x, y) = (%lld, %lld)\n", a, b, my_gcd(a, b), x, y);
}

void test_my_gcd_multi() {
	vl a;
	int n;
	// n = rand() % 10;
	cin >> n;
	cout << n << endl;
	for (int i = 0; i < n; ++i) {
		// a.push_back(rand());
		int a_i; cin >> a_i;
		a.push_back(a_i);
	}
	for (int a_i : a) cout << a_i << ", "; cout << endl;
	cout << my_gcd(a) << endl;
}

void test_ext_gcd_multi() {
	int n;
	cin >> n;
	vl a(n);
	for (int i = 0; i < n; ++i) {
		ll a_i; cin >> a_i;
		a[i] = a_i;
	}
	vl x = ext_gcd(a);
	for (int x_i : x) cout << x_i << " "; cout << endl;
}

void test_my_inv() {
	ll a, m; cin >> a >> m;
	printf("%lld * %lld = %lld (mod %lld)\n", a, my_inv(a, m), my_gcd(a, m), m);
}

void test_my_crt() {
	int n;
	// cin >> n;
	n = 3;
	vl r(n), m(n);
	for (int i = 0; i < n; ++i) {
		cin >> r[i] >> m[i];
	}
	ll y, z; tie(y, z) = my_crt(r, m);
	if (z == 0) cout << -1 << endl;
	else cout << y << endl;

	// cout << y << " " << z << endl;
	// cout << y << endl;
}

int main() {
	srand((unsigned)time(NULL));

	// test_my_gcd();
	// test_my_gcd_multi();
	// test_ext_gcd_multi();
	// test_my_inv();
	test_my_crt();
}
0