結果
| 問題 | No.187 中華風 (Hard) |
| コンテスト | |
| ユーザー |
 綾坂こと
|
| 提出日時 | 2026-09-19 07:10:50 |
| 言語 | TypeScript (7.0.2 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 53 ms / 3,000 ms |
| + 275µs | |
| コード長 | 30,235 bytes |
| 記録 | |
| コンパイル時間 | 1,370 ms |
| コンパイル使用メモリ | 194,560 KB |
| 実行使用メモリ | 55,296 KB |
| 最終ジャッジ日時 | 2026-09-19 07:10:56 |
| 合計ジャッジ時間 | 4,067 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge2_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 25 |
ソースコード
// ================================================================
// yukicoder No.187 中華風 (Hard)
// (URL: https://yukicoder.me/problems/no/187)
// TypeScript (Node.js, using InputScanner) [Main] Submission
// ================================================================
function Main(inputText: string): void {
const scanner = new InputScanner(inputText);
// Add your code here
const N = scanner.int()!;
const [X, Y] = scanner.bigint(N, 2);
const MOD = 1000000007n;
// ANS ≡ X_i (mod Y_i)がたくさん与えられるので、CRTをぶん回す
const [ans, lcm] = ExtendedMath.crt(X, Y);
if (ans === 0n && lcm === 0n) {
console.log(-1);
} else if (ans === 0n) {
console.log((lcm % MOD).toString());
} else {
console.log((ans % MOD).toString());
}
}
/**
* 入力をスキャンし、トークンを順に取得するためのクラスです。
* - .str()で文字列、.num()で浮動小数点数、.int()で整数、.bigint()でBigIntとして取得できます。
* - 引数なしだと1つ、引数1つ(n)だと最大長さnの配列、引数2つ(n, g)だと長さgの最大長さnの配列の配列として取得できます。
*/
class InputScanner {
#str: string;
#len: number;
#idx: number;
/** 新しい入力スキャナーインスタンスを生成します。 */
constructor(str: string) {
this.#str = str;
this.#len = str.length;
this.#idx = 0;
}
/** ある文字がトークンの区切りとみなせる文字(' '・'\n'・'\r'・'\t')であるかを判定します。 */
#isSpace(c: number): boolean {
return c === 32 || c === 10 || c === 13 || c === 9;
}
/** #idxをトークンの区切りとみなせる文字の直後まで進めます。 */
#skipSpaces() {
while (this.#idx < this.#len) {
const c = this.#str.charCodeAt(this.#idx);
if (!this.#isSpace(c)) break;
this.#idx++;
}
}
#read<T>(fn: (token: string) => T): T | undefined;
#read<T>(fn: (token: string) => T, n: number): T[];
#read<T>(fn: (token: string) => T, n: number, g: number): T[][];
/**
* @private
* トークンを読んだうえで、そのトークンを渡された関数に通して変換して返します。
* @param fn - トークンを変換する関数
* @param n - 取得するトークンの最大数
* @param g - トークンのグループ数(トークンいくつで1巡するか)
*/
#read<T>(fn: (token: string) => T, n?: number, g?: number): T | T[] | T[][] | undefined {
// nがない場合: 1トークン読む
if (n == null) {
this.#skipSpaces();
if (this.#idx >= this.#len) return undefined;
const startIdx = this.#idx;
while (this.#idx < this.#len) {
const c = this.#str.charCodeAt(this.#idx);
if (this.#isSpace(c)) break;
this.#idx++;
}
const token = this.#str.substring(startIdx, this.#idx);
return fn(token);
}
// nだけある場合: nトークン読む
else if (g == null) {
const result: T[] = [];
for (let i = 0; i < n; i++) {
const token = this.#read(fn);
if (token == null) break;
result.push(token);
}
return result;
}
// nもgもある場合: n×gトークン読む
else {
const result: T[][] = Array.from({ length: g }, () => []);
read: for (let i = 0; i < n; i++) {
for (let j = 0; j < g; j++) {
const token = this.#read(fn);
if (token == null) break read;
result[j].push(token);
}
}
return result;
}
}
/**
* トークンを1つ、stringとして取得します。
* - もうトークンが存在しない場合、undefinedを返します。
*/
str(): string | undefined;
/**
* トークンを(最大)n個、string[]として取得します。
* - 残りトークンがn個に満たない場合、長さn未満のstring[]が返されます。
* @param n 取得するトークンの最大数
*/
str(n: number): string[];
/**
* トークンを(最大)n×g個、string[][]として取得します。
* - 戻り値のi(0≦i<g)番目の配列は、残存トークンのうちi番目, g+i番目, 2g+i番目, ..., (n-1)g+i番目のトークンを順に取得したstring[]です。
* - 戻り値の配列の長さは必ずg個ですが、残存トークンが不足している場合は長さnに満たない配列や空配列が含まれることがあります。
* @param n 取得するトークンの最大数
* @param g トークンのグループ数(トークンいくつで1巡するか)
*/
str(n: number, g: number): string[][];
str(n?: number, g?: number): string | string[] | string[][] | undefined {
const mapFn = (token: string) => token;
if (n == null) return this.#read(mapFn);
else if (g == null) return this.#read(mapFn, n);
else return this.#read(mapFn, n, g);
}
/**
* トークンを1つ、number(64bit浮動小数点数)として取得します。小数を許容します。
* - もうトークンが存在しない場合、undefinedを返します。
*/
num(): number | undefined;
/**
* トークンを(最大)n個、number[]として取得します。各要素は小数を許容します。
* - 残りトークンがn個に満たない場合、長さn未満のnumber[]が返されます。
* @param n 取得するトークンの最大数
*/
num(n: number): number[];
/**
* トークンを(最大)n×g個、number[][]として取得します。各要素は小数を許容します。
* - 戻り値のi(0≦i<g)番目の配列は、残存トークンのうちi番目, g+i番目, 2g+i番目, ..., (n-1)g+i番目のトークンを順に取得したnumber[]です。
* - 戻り値の配列の長さは必ずg個ですが、残存トークンが不足している場合は長さnに満たない配列や空配列が含まれることがあります。
* @param n 取得するトークンの最大数
* @param g トークンのグループ数(トークンいくつで1巡するか)
*/
num(n: number, g: number): number[][];
num(n?: number, g?: number): number | number[] | number[][] | undefined {
const mapFn = (token: string) => Number.parseFloat(token);
if (n == null) return this.#read(mapFn);
else if (g == null) return this.#read(mapFn, n);
else return this.#read(mapFn, n, g);
}
/**
* トークンを1つ、整数値のnumberとして取得します。
* - もうトークンが存在しない場合、undefinedを返します。
*/
int(): number | undefined;
/**
* トークンを(最大)n個、number[]として取得します。
* - 残りトークンがn個に満たない場合、長さn未満の整数値の配列(number[])が返されます。
* @param n 取得するトークンの最大数
*/
int(n: number): number[];
/**
* トークンを(最大)n×g個、整数値のnumber[][]として取得します。
* - 戻り値のi(0≦i<g)番目の配列は、残存トークンのうちi番目, g+i番目, 2g+i番目, ..., (n-1)g+i番目のトークンを順に整数値として取得したnumber[]です。
* - 戻り値の配列の長さは必ずg個ですが、残存トークンが不足している場合は長さnに満たない配列や空配列が含まれることがあります。
* @param n 取得するトークンの最大数
* @param g トークンのグループ数(トークンいくつで1巡するか)
*/
int(n: number, g: number): number[][];
int(n?: number, g?: number): number | number[] | number[][] | undefined {
const mapFn = (token: string) => Number.parseInt(token);
if (n == null) return this.#read(mapFn);
else if (g == null) return this.#read(mapFn, n);
else return this.#read(mapFn, n, g);
}
/**
* トークンを1つ、BigIntとして取得します。
* - もうトークンが存在しない場合、undefinedを返します。
*/
bigint(): bigint | undefined;
/**
* トークンを(最大)n個、bigint[]として取得します。
* - 残りトークンがn個に満たない場合、長さn未満のBigIntの配列(bigint[])が返されます。
* @param n 取得するトークンの最大数
*/
bigint(n: number): bigint[];
/**
* トークンを(最大)n×g個、bigint[][]として取得します。
* - 戻り値のi(0≦i<g)番目の配列は、残存トークンのうちi番目, g+i番目, 2g+i番目, ..., (n-1)g+i番目のトークンを順に取得したbigint[]です。
* - 戻り値の配列の長さは必ずg個ですが、残存トークンが不足している場合は長さnに満たない配列や空配列が含まれることがあります。
* @param n 取得するトークンの最大数
* @param g トークンのグループ数(トークンいくつで1巡するか)
*/
bigint(n: number, g: number): bigint[][];
bigint(n?: number, g?: number): bigint | bigint[] | bigint[][] | undefined {
const mapFn = (token: string) => BigInt(token);
if (n == null) return this.#read(mapFn);
else if (g == null) return this.#read(mapFn, n);
else return this.#read(mapFn, n, g);
}
}
// ======== Copied from AyaExpTech Arcane ========
// Using: AXT-AyaKoto/axt-arcane-bundler (https://github.com/AXT-AyaKoto/axt-arcane-bundler)
// Package: jsr:@ayaexptech/arcane@2.0.0-alpha.4
// Resolved version (sources): 2.0.0-alpha.4
// Selected exports: ExtendedMath
/**
* 数学的な関数のうち、JavaScript標準の`Math`にないものを提供するユーティリティクラスです。
* - number: 最大公約数・最小公倍数・約数列挙・popcount(下位32bit)
* - bigint: 最大公約数・最小公倍数・拡張ユークリッドの互除法・min, max, abs, sign・整数平方根
* - bigint: 冪乗mod・逆元・中国剰余定理(CRT)
* - ミラー-ラビン素数判定法
*/
class ExtendedMath {
/**
* 2つの整数の最大公約数を求めます。
* なお、gcd(0, 0) = 0、gcd(a, 0) = gcd(0, a) = |a| とします。
*
* 時間計算量: 最悪 O(log(min(|a|, |b|)))
*
* @example number型の場合
* ```ts
* ExtendedMath.gcd(48, 18) // => 6
* ```
*
* @example bigint型の場合
* ```ts
* ExtendedMath.gcd(48n, 18n) // => 6n
* ```
*
* @template T - 引数と返り値の型。numberまたはbigint。
* @param a - 1つ目の整数。
* @param b - 2つ目の整数。
* @returns aとbの最大公約数。引数と同じ型で返されます。
*/
static gcd<T extends number | bigint>(a: T, b: T): T {
while (b) {
[a, b] = [b, (a % b) as T];
}
return a < 0 ? (-a as T) : a;
}
/**
* 2つの整数の最小公倍数を求めます。
* なお、lcm(0, 0) = 0、lcm(a, 0) = lcm(0, a) = 0 とします。
*
* 時間計算量: 最悪 O(log(min(|a|, |b|))) （gcdの計算に依存）
*
* @example number型の場合
* ```ts
* ExtendedMath.lcm(12, 18) // => 36
* ```
*
* @example bigint型の場合
* ```ts
* ExtendedMath.lcm(12n, 18n) // => 36n
* ```
*
* @template T - 引数と返り値の型。numberまたはbigint。
* @param a - 1つ目の整数。
* @param b - 2つ目の整数。
* @returns aとbの最小公倍数。引数と同じ型で返されます。
*/
static lcm<T extends number | bigint>(a: T, b: T): T {
if (a === 0 || b === 0 || a === 0n || b === 0n) {
return (typeof a === "bigint" ? 0n : 0) as T;
}
return ((a * b) / ExtendedMath.gcd(a, b)) as T;
}
/**
* 非負整数a, bについて、ax + by = g を満たす整数x, yを求めます。
* なお、ここで g = gcd(a, b) とし、a = b = 0 のときは g = 0 とします。
*
* 時間計算量: O(log(min(a, b)))
*
* @example
* ```ts
* const [g, x, y] = ExtendedMath.extendedGCD(30n, 21n);
* console.log(g); // => 3n
* console.log(x); // => -2n
* console.log(y); // => 3n
* // 確認: 30*(-2) + 21*3 === 3
* console.log(30n * x + 21n * y === g); // => true
* ```
*
* @param a - 非負整数a
* @param b - 非負整数b
* @returns [g, x, y] - gはaとbの最大公約数、xとyはax + by = gを満たす整数
*/
static extendedGCD(a: bigint, b: bigint): [g: bigint, x: bigint, y: bigint] {
let r0 = a;
let r1 = b;
let x0 = 1n;
let x1 = 0n;
let y0 = 0n;
let y1 = 1n;
while (r1 !== 0n) {
const q = r0 / r1;
const temp = r1;
r1 = r0 % r1;
r0 = temp;
const tempX = x0;
x0 = x1;
x1 = tempX - q * x1;
const tempY = y0;
y0 = y1;
y1 = tempY - q * y1;
}
return [r0, x0, y0];
}
/**
* 整数`n`の正の約数を列挙します。
* ただし、`n === 1`なら`[1]`、`n < 1`なら`[]`を返します。
*
* 時間計算量: O(√n)
*
* @example
* ```ts
* ExtendedMath.getDivisors(28) // => [1, 2, 4, 7, 14, 28]
* ExtendedMath.getDivisors(1) // => [1]
* ExtendedMath.getDivisors(0) // => []
* ExtendedMath.getDivisors(-5) // => []
* ```
*
* @param n - 対象の整数
* @returns 正の約数を昇順で列挙した配列
*/
static getDivisors(n: number): number[] {
if (n < 1) return [];
if (n === 1) return [1];
/** @type {number[]} */
const smallDivisors: number[] = [];
/** @type {number[]} */
const largeDivisors: number[] = [];
const limit = Math.sqrt(n);
// 1から√nまでの整数で割り切れるかを調べ、割り切れたらiをsmallDivisors、n/iをlargeDivisorsに追加する
for (let i = 1; i <= limit; i++) {
if (n % i === 0) {
smallDivisors.push(i);
if (i !== n / i) {
largeDivisors.push(n / i);
}
}
}
// smallDivisorsにlargeDivisorsの逆順を追加して返す。
largeDivisors.reverse();
smallDivisors.push(...largeDivisors);
return smallDivisors;
}
/**
* 整数`n`の整数平方根を求めます。すなわち、`x ** 2 <= n < (x + 1) ** 2`を満たす唯一の整数`x`を返します。
*
* 時間計算量: nが2^104未満の場合はO(1)、それ以上の場合はO(M(log_2(n)))
* ここで M(k) はkビット整数の乗算の時間計算量で、これは実行エンジンに依存します。一般に M(k) は O(k^(log_2(3))) もしくは O(k log k log log k) となります。
*
* @example
* ```ts
* ExtendedMath.isqrt(10n) // => 3n
* ExtendedMath.isqrt(15n) // => 3n
* ExtendedMath.isqrt(16n) // => 4n
* ```
*
* @param n - 対象の整数 (n >= 0)
* @returns nの整数平方根
* @throws {RangeError} nが負の数の場合
*/
static isqrt(n: bigint): bigint {
// nが負の数の場合はエラー
if (n < 0n) {
throw new RangeError("n must be non-negative");
}
// f64 で扱える範囲ならば、Math.sqrt + 1段階の補正を利用する
// n <= 2^104 では floor(sqrt) が高々 +1 しかずれないことが示されている
if (n < 20282409603651670423947251286016n /* 2n ** 104n */) {
let s = BigInt(Math.floor(Math.sqrt(Number(n))));
if (s * s > n) s--;
return s;
}
// 漸化式の初期値
// 効率的なビット長の近似計算: 16進数文字列長 * 4
const bitLength = BigInt(n.toString(16).length * 4);
let x0 = 1n << ((bitLength + 1n) / 2n);
let x1 = (x0 + n / x0) / 2n; // 漸化式で次のステップの値を計算
// x1 が x0 より小さい間 = まだ収束していない間
while (x1 < x0) {
x0 = x1; // 値を更新
x1 = (x0 + n / x0) / 2n; // 再度、次のステップの値を計算
}
// ループを抜けた時点の x0 が求める答え
return x0;
}
/**
* 整数`a`, 非負整数`n`, 正整数`m`について、`a`の`n`乗を`m`で割った余り(`(a ** n) % m`)を求めます。
*
* 時間計算量: O(log n)
* (ただし、剰余、余剰演算の時間計算量はO(1)と仮定)
*
* @example
* ```ts
* ExtendedMath.modPow(3n, 200n, 50n) // => 1n
* ```
*
* @param a - 底 (整数)
* @param n - 指数 (非負整数)
* @param m - 法 (正整数)
* @returns aのn乗をmで割った余り
* @throws {RangeError} nが負の数である場合、またはmが正の整数でない場合
*/
static modPow(a: bigint, n: bigint, m: bigint): bigint {
// エラーハンドリング
if (n < 0n) {
throw new RangeError("exponent (n) must be non-negative integer");
}
if (m <= 0n) {
throw new RangeError("modulus (m) must be a positive integer");
}
// m === 1のときは常に0を返す
if (m === 1n) return 0n;
// 繰り返し二乗法をやる
let result = 1n;
let base = ((a % m) + m) % m;
let exponent = n;
while (exponent > 0n) {
if (exponent % 2n === 1n) {
result = (((result * base) % m) + m) % m;
}
base = (((base * base) % m) + m) % m;
exponent = exponent / 2n;
}
return ((result % m) + m) % m;
}
/**
* 法をmとする合同算術におけるaのモジュラ逆数(乗法の逆元)を返します。
* すなわち、av ≡ 1 (mod m)となる0以上m未満の唯一の整数vを返します。
* (ただし、gcd(a, m) ≠ 1のとき逆元は存在せず、このときは例外を発生させます。)
*
* 時間計算量: O(log m)
*
* @example
* ```ts
* console.log(ExtendedMath.modInv(3n, 7n)); // => 5n (3×5 = 15 ≡ 1 (mod 7))
* console.log(ExtendedMath.modInv(0n, 1n)); // => 0n
* console.log(ExtendedMath.modInv(-2n, 7n)); // => 3n
* console.log(ExtendedMath.modInv(2n, 4n)); // => throw Error (gcd(2,4)=2(≠1))
* ```
*
* @param a - 逆元を求めたい整数
* @param m - 法 (1以上)
* @returns 法をmとする合同算術におけるaのモジュラ逆数(乗法の逆元)。0以上m未満の整数
* @throws {Error} - aとmが互いに素でない(つまり、逆元が存在しない)か、mが1未満である場合
*/
static modInv(a: bigint, m: bigint): bigint {
if (m < 1n) {
throw new Error("The modulus `m` must be greater than or equal to 1.");
}
const a_mod_m = a % m;
const a0 = a_mod_m + (a_mod_m < 0n ? m : 0n);
const [g, x] = ExtendedMath.extendedGCD(a0, m);
if (g !== 1n) {
throw new Error(`Inverse does not exist for ${a} (mod ${m}) because gcd(${a0}, ${m}) = ${g} (is not 1).`);
}
const x_mod_m = x % m;
const x0 = x_mod_m + (x_mod_m < 0n ? m : 0n);
return x0;
}
/**
* `n`が素数であるかを、ミラー・ラビン素数判定法により判定します。
*
* > [!IMPORTANT]
* > このメソッドは確率的アルゴリズムです。
* > - `false`が返された場合`n`は確実に合成数です。
* > - `true`が返された場合`n`は素数である可能性がありますが、確実ではありません。
* > - ただし、`n < 2^64`の範囲で、かつ`bases`を省略した場合において、`true`が返されたときは`n`は確実に素数です。
*
* 時間計算量: O(b * log(n) * M(log_2(n)))
* ここで、bは`bases`の長さ、M(k)はkビット整数の乗算の時間計算量です。
* bは`bases`を省略した場合固定で7で、この場合時間計算量はO(log(n) * M(log_2(n)))となります。
* M(k)は実行エンジンに依存しますが、一般にO(k^(log_2(3)))もしくはO(k log k log log k)となります。
*
* @example basesを省略した場合（n < 2^64なら決定的）
* ```ts
* ExtendedMath.isProbablyPrime(17n) // => true
* ExtendedMath.isProbablyPrime(18n) // => false
* ```
*
* @example basesを指定した場合（n < 2^64であっても、basesに不適切な値を入れると誤判定する可能性がある）
* ```ts
* ExtendedMath.isProbablyPrime(17n, [2n]) // => true
* ExtendedMath.isProbablyPrime(25326001n, [2n, 3n, 5n]) // => true (※25326001は、bases={2,3,5}に対して通過する最小の合成数(Strong pseudoprime)として知られています)
* ```
*
* @param n - 判定する整数 (2以上)
* @param [bases] - 判定に使用する基数の配列 (省略時は2^64未満で決定的になるよう選定)
* @returns - 素数でなければfalse、素数かもしれなければtrue (bases省略時、n<2^64なら決定的)
*/
static isProbablyPrime(n: bigint, bases?: bigint[]): boolean {
// エラーハンドリング
if (n <= 1n) return false;
if (n === 2n) return true;
if (n % 2n === 0n) return false;
// 基数のリストを先に作っておく
const BASES = bases ?? [2n, 325n, 9375n, 28178n, 450775n, 9780504n, 1795265022n];
// n - 1 = 2^s * d の形に変形 (dが奇数になるまで2で割る)
let d = n - 1n;
let s = 0n;
while ((d & 1n) === 0n) {
d >>= 1n;
s += 1n;
}
// 各基数についてテストを行う
for (const a of BASES) {
// 底が n と等しい場合は素数
if (a === n) return true;
// 底が n の倍数 (a % n === 0) の場合は skip（mod n が 0 になり x=0 となって誤判定するため）
if (a % n === 0n) continue;
// (効率化) n が底の倍数なら合成数 (例: n=9, a=3)
if (n % a === 0n) return false;
// x = a^d mod n
let x = ExtendedMath.modPow(a, d, n);
// x = 1 または x = n - 1 なら「素数っぽい」ので次の底へ
if (x === 1n || x === n - 1n) continue;
// xを2乗していき、n - 1 になるかチェック (s-1回繰り返す)
let isProbablyPrime = false;
for (let r = 1n; r < s; r++) {
x = (x * x) % n;
if (x === n - 1n) {
isProbablyPrime = true;
break;
}
}
// n - 1 にならなかった場合は合成数
if (!isProbablyPrime) {
return false;
}
}
// すべての基数で「素数っぽい」場合は素数かもしれない
return true;
}
/**
* 符号なし32bit整数`n`における立っているビットの数(popcount)を返します。
* なお、nが整数でない場合、`0`未満の場合、`2**32`以上の場合の動作は未定義です。
* (エラーを吐かず、多くの場合で誤った値を返します。この関数を使用する際は入力値が`0`以上`2**32`未満の整数であることを確認してください。)
*
* 時間計算量: O(1)
*
* @example
* ```ts
* ExtendedMath.popcount32(0b10101010) // => 4
* ExtendedMath.popcount32(0b11111111) // => 8
* ```
*
* @param n - 対象の整数 (`0`以上`2**32`未満)
* @returns nにおける立っているビットの数
*/
static popcount32(n: number): number {
n = n - ((n >>> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
return (((n + (n >>> 4)) & 0x0f0f0f0f) * 0x01010101) >>> 24;
}
/**
* 1つ以上のbigintを受け取り、そのうち最大のものを返します。
*
* 時間計算量: O(n) (nは引数の個数)
*
* @example
* ```ts
* ExtendedMath.maxBigint(1n, 2n, 3n) // => 3n
* ```
*
* @param first - 1つ目のbigint
* @param rest - 2つ目以降のbigint
* @returns 最大のbigint
*/
static maxBigint(first: bigint, ...rest: bigint[]): bigint {
let max = first;
for (const value of rest) {
if (value > max) {
max = value;
}
}
return max;
}
/**
* 1つ以上のbigintを受け取り、そのうち最小のものを返します。
*
* 時間計算量: O(n) (nは引数の個数)
*
* @example
* ```ts
* ExtendedMath.minBigint(1n, 2n, 3n) // => 1n
* ```
* @param first - 1つ目のbigint
* @param rest - 2つ目以降のbigint
* @returns 最小のbigint
*/
static minBigint(first: bigint, ...rest: bigint[]): bigint {
let min = first;
for (const value of rest) {
if (value < min) {
min = value;
}
}
return min;
}
/**
* bigintを受け取り、その絶対値を返します。
*
* 時間計算量: O(1)
*
* @example
* ```ts
* ExtendedMath.absBigint(1n) // => 1n
* ExtendedMath.absBigint(-7n) // => 7n
* ```
* @param n - 対象のbigint
* @returns nの絶対値
*/
static absBigint(n: bigint): bigint {
return n < 0n ? -n : n;
}
/**
* bigintを受け取り、その符号を返します。
*
* 時間計算量: O(1)
*
* @example
* ```ts
* ExtendedMath.signBigint(1n) // => 1n
* ExtendedMath.signBigint(-7n) // => -1n
* ```
* @param n - 対象のbigint
* @returns nの符号
*/
static signBigint(n: bigint): 0n | 1n | -1n {
return n === 0n ? 0n : n < 0n ? -1n : 1n;
}
/**
* ソート済みの数列に対して、中央値を返します。
* 空配列に対してはNaNを返します。
*
* 時間計算量: O(1)
*
* @example
* ```ts
* ExtendedMath.medianOfSorted([1, 2, 3]) // => 2
* ExtendedMath.medianOfSorted([1, 2, 3, 4]) // => 2.5
* ExtendedMath.medianOfSorted([1, 3, 3, 6]) // => 3
* ExtendedMath.medianOfSorted([]) // => NaN
* ```
*
* @param sequence - ソート済みの数列
* @returns 中央値
*/
static medianOfSorted(sequence: Readonly<ArrayLike<number>>): number {
if (sequence.length <= 0 || !Number.isSafeInteger(sequence.length)) {
return NaN;
}
if (sequence.length % 2 === 1) {
return sequence[(sequence.length - 1) / 2];
} else {
const a = sequence[sequence.length / 2 - 1];
const b = sequence[sequence.length / 2];
return (a + b) / 2;
}
}
/**
* 中国剰余定理を用いて、連立合同式を合体します。
* k元連立合同式x≡a_i(mod n_i) (0≦i<k)を満たすxは0以上lcm(n_0, n_1, ...)未満の範囲にただ一つ存在します。
* (ただし、"法が同じでa_iが異なる"のような自明な例外を除きます。)
* それを踏まえて、k元連立合同式のaとmをすべて受け取り、xとlcm(n_0, n_1, ...)を返します。
*
* 時間計算量: O(|n| log lcm(n))
*
* @example
* ```ts
* console.log(ExtendedMath.crt([10n], [7n])); // => [3n, 7n]
* console.log(ExtendedMath.crt([-1n, 3n], [4n, 6n])); // => [3n, 12n]
* console.log(ExtendedMath.crt([1n, 3n], [4n, 6n])); // => [9n, 12n]
* console.log(ExtendedMath.crt([0n, 1n], [2n, 2n])); // => [0n, 0n]
* console.log(ExtendedMath.crt([0n], [1n])); // => [0n, 1n]
* ```
*
* @param a - a[i]は、条件として与えるk元連立合同式x≡a_i(mod n_i)のa_i
* @param n - n[i]は、条件として与えるk元連立合同式x≡a_i(mod n_i)のn_i
* @returns [x, l]で、x+lt(tは整数)がすべての合同式を満たすとを示す。解なしの場合は[0n, 0n]。
* @throws {Error} - aとnの長さが一致しないか、nに1未満の値が含まれている場合
*/
static crt(a: readonly bigint[], n: readonly bigint[]): [x: bigint, l: bigint] {
if (a.length !== n.length) {
throw Error("The lengths of arrays `a` and `n` must match.");
}
if (n.some((ni) => ni < 1n)) {
throw Error("Array `n` must not contain any values less than 1.");
}
let a1 = 0n;
let n1 = 1n;
for (let i = 0; i < a.length; i++) {
const a2 = a[i];
const n2 = n[i];
const g = ExtendedMath.gcd(n1, n2);
if ((a2 - a1) % g !== 0n) return [0n, 0n];
const n2g = n2 / g;
const u = ExtendedMath.modInv(n1 / g, n2g);
const t = (u * (a2 - a1)) / g;
const t_mod_n2g = t % n2g;
const t0 = t_mod_n2g + (t_mod_n2g < 0n ? n2g : 0n);
a1 = a1 + n1 * t0;
n1 = n1 * n2g;
}
return [a1, n1];
}
}
// ======== Copied from AyaExpTech Arcane (End) ========
// Please do not change the following code.
Main(require("fs").readFileSync("/dev/stdin", "utf8"));