結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー ゴリポン先生
提出日時 2026-01-15 19:21:19
言語 D
(dmd 2.111.0)
結果
AC  
実行時間 142 ms / 3,000 ms
コード長 3,078 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,084 ms
コンパイル使用メモリ 190,288 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-15 19:21:29
合計ジャッジ時間 7,657 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/linuxbrew/.linuxbrew/opt/dmd/include/dlang/dmd/std/numeric.d(3011): Warning: cannot inline function `std.numeric.gcdImpl!ulong.gcdImpl`
private typeof(T.init % T.init) gcdImpl(T)(T a, T b)
                                ^

ソースコード

diff #
raw source code 

module main;
// https://qiita.com/drken/items/ae02240cd1f8edfc86fd より
// 中国剰余定理
import std;

immutable MOD = 10L ^^ 9 + 7;
// 負の数にも対応した剰余
long mod(long a, long m)
{
	long ret = a % m;
	if (ret < 0) ret += m;
	return ret;
}
// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす(x, y)が格納される
long extGcd(long a, long b, out long x, out long y)
{
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long d = extGcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
// Garner のアルゴリズムの前処理
long preGarner(long[] b, long[] m, long MOD)
{
	long res = 1;
	int sz = b.length.to!int;
	foreach (i; 0 .. sz) {
		foreach (j; 0 .. i) {
			long g = gcd(m[i], m[j]);
			// これを満たさなければ解はない
			if ((b[i] - b[j]) % g != 0) return -1;
			// s = m[i], t = m[j] を仮想的に素因数分解して s = p^k ... q^l ..., t = q^m ... r^n ... となったときに
			m[i] /= g;	// p については i の方が大きかったものについての j との差分、と q
			m[j] /= g;	// p については j の方が大きかったものについての i との差分、と r
			/*
			  残る g を i と j に振り分ける (i の方が指数大きかった素因子 p の分は最終的に gi に、j の方が指数大きかった素因子 p の分は最終的に gj に)
			 */
			// ひとまず j 側にある p については gj のみに行くようにする
			long gi = gcd(m[i], g), gj = g / gi;
			// 本来 i 側に行くべき p で gj 側にあるものを gi 側に寄せていく
			do {
				g = gcd(gi, gj);
				gi *= g, gj /= g;
			} while (g != 1);
			// i 側と j 側に戻していく
			m[i] *= gi, m[j] *= gj;
			// m[i] と m[j] が元より小さくなったのに合わせて余りも計算し直しておく
			b[i] %= m[i], b[j] %= m[j];
		}
	}
	foreach (i; 0 .. sz) (res *= m[i]) %= MOD;
	return res;
}
// 逆元計算 (ここでは a と m が互いに素であることが必要)
long modInv(long a, long m)
{
	long x, y;
	extGcd(a, m, x, y);
	return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
}
// Garner のアルゴリズム, x%MOD, LCM%MOD を求める (m は互いに素でなければならない)
long garner(long[] b, long[] m, long MOD)
{
	m ~= MOD; // 番兵
	auto coeffs = [1L].replicate(m.length);
	auto constants = new long[](m.length);
	foreach (k; 0 .. b.length.to!int) {
		long t = mod((b[k] - constants[k]) * modInv(coeffs[k], m[k]), m[k]);
		foreach (i; k + 1 .. m.length) {
			(constants[i] += t * coeffs[i]) %= m[i];
			(coeffs[i] *= m[k]) %= m[i];
		}
	}
	return constants.back();
}
void main()
{
	// 入力
	int N = readln.chomp.to!int;
	auto B = new long[](N), M = new long[](N);
	bool existNonZero = false;
	foreach (i; 0 .. N) {
		readln.chomp.formattedRead("%d %d", B[i], M[i]);
		if (B[i]) existNonZero = true;
	}
	// 答えの計算と出力
	long lcm = preGarner(B, M, MOD);
	if (!existNonZero)
		writeln(lcm);
	else if (lcm == -1)
		writeln(-1);
	else
		writeln(garner(B, M, MOD));
}
0