Contents
この記事のゴール
- 結論：答えは「各位置 i を除いた配列の GCD」の最大値。
- 理由：1 つだけ好きな値に書き換えられるため、全体の GCD は「その 1 要素を除いた残りの GCD」まで引き上げられる。
- 方法：左右の累積 GCD（prefix/suffix）で、各 i について
gcd(prefix[i-1], suffix[i+1])を候補に最大を取る。 - 実装：TypeScript（Node.js）で O(N logV)、メモリは O(N) もしくは O(1) 配列。
問題概要（ABC125C）
与えられた N 個の整数列 A に対して、ちょうど 1 つの要素を 1〜10^9 の好きな整数に書き換える。書き換え後の配列全体の最大公約数（GCD）を最大にせよ。
- 制約：2 ≤ N ≤ 10^5、1 ≤ A_i ≤ 10^9
- 入力：
1 行目 N、2 行目 A_1 … A_N - 出力：書き換え後の GCD の最大値
- 例：
N=3, A=[7,6,8]→ 7 を 4 にすると全体 GCD は 2（これが最大） - 問題URL（AtCoder公式）：https://atcoder.jp/contests/abc125/tasks/abc125_c
解法の芯
結論
各位置 i を除いた残り全体の GCD を計算し、その最大が答え。
理由
- i 番目を任意の値 x に書き換えると、全体 GCD は
gcd(x, G)（G = 「i を除いた GCD」）。 - x = G と選べば全体 GCD は少なくとも G になる。
- よって、すべての i で「i を除いた GCD」を出して最大を取るだけでよい。
具体例
[7, 6, 8]
- i=0 を除く
[6,8]の GCD は 2 - i=1 を除く
[7,8]の GCD は 1 - i=2 を除く
[7,6]の GCD は 1
最大が 2 → 実際に 7→4 と書き換えると全体 GCD は 2。
再確認
左右の累積 GCD を作れば、各 i を除いた GCD を O(1) で取り出せる。全体は O(N) 回の GCD で終わる。
アルゴリズムの全体像
prefix[i] = gcd(A[0], …, A[i])suffix[i] = gcd(A[i], …, A[N-1])- i を除いた GCD =
gcd(prefix[i-1], suffix[i+1])（端は片側のみ） - その最大が答え
計算量：GCD は O(logV)。前後 2 パス＋評価で O(N logV)、メモリ O(N)（工夫で実質 1 配列にできる）
実装例（TypeScript / Node.js）
提出コード（1配列＋1パス）
左の累積 L[i] と右側累積を 1 変数 right で持ち、後ろから 1 回なめるだけで更新します。
import * as fs from "fs";
// エントリポイント inputに入力データ全体が入る
function main(input: string): void {
// const splittedInput = input.trim().split(/\r?\n/);
const [nRaw, aRaw] = input.trim().split(/\r?\n/);
const N = Number(nRaw);
const A = aRaw.split(" ").map(Number);
const gcd = (a: number, b: number): number => b ? gcd(b, a % b) : Math.abs(a);
// L を作る
const L = Array(N).fill(0);
L[0] = A[0];
for (let i = 1; i < N; i++) L[i] = gcd(L[i-1], A[i]);
let ans = 0, right = 0; // right は R[i+1] を順に表す
for (let i = N - 1; i >= 0; i--) {
const left = (i > 0 ? L[i-1] : 0); // gcd(x,0)=x
ans = Math.max(ans, gcd(left, right));
right = gcd(right, A[i]); // 次の i-1 に向け更新
}
console.log(ans);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
const inputData: string = fs.readFileSync("/dev/stdin", "utf8")
main(inputData);
参考実装（prefix/suffix の 2 配列で分かりやすく）
読みやすさ重視。境界処理が明瞭です。
import * as fs from 'fs';
const tokens = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
const N = tokens[0];
const A = tokens.slice(1);
const gcd = (a: number, b: number): number => {
a = Math.abs(a); b = Math.abs(b);
while (b !== 0) { const t = a % b; a = b; b = t; }
return a;
};
const prefix = new Array<number>(N);
const suffix = new Array<number>(N);
prefix[0] = A[0];
for (let i = 1; i < N; i++) prefix[i] = gcd(prefix[i-1], A[i]);
suffix[N-1] = A[N-1];
for (let i = N - 2; i >= 0; i--) suffix[i] = gcd(suffix[i+1], A[i]);
let ans = 0;
for (let i = 0; i < N; i++) {
const left = (i === 0) ? 0 : prefix[i-1];
const right = (i === N-1) ? 0 : suffix[i+1];
const withoutI = (left === 0) ? right : (right === 0) ? left : gcd(left, right);
if (withoutI > ans) ans = withoutI;
}
console.log(ans.toString());
動作確認（例）
入力
3
7 6 8
出力
2
よくある間違いと落とし穴
- 端の処理を忘れる：
i=0やi=N-1で配列外参照をしない。 - 毎回 GCD を作り直して O(N^2)：prefix/suffix を前計算する。
- 素因数分解や LCM に寄り道：本問は GCD の性質のみで十分。
- 数値精度が不安：A_i ≤ 10^9 なので JS の Number（53bit）で安全。
- 「ちょうど 1 回」の読み違い：同じ値に書き換え可＝実質「高々 1 回」。解法は同じ。
発展的な実装ヒント
- メモリ最小化：
prefixを変数、suffixのみ配列にすれば 1 配列。 - テスト観点：
- 最小：
N=2（例：5 10→10） - 全要素同一：
[x, x, …]→x - 互いに素っぽい：
[6,10,15]→ 最大は5 - ランダム／大 N で性能確認
- 最小：
まとめ
- 上限は 「除いた残りの GCD」。
- prefix/suffix で候補を O(1) 取得 → 全体 O(N logV)。
- TypeScript で素直に実装でき、境界と I/O だけ注意すれば十分。
付録：入出力テンプレ（Node.js）
import * as fs from 'fs';
const it = fs.readFileSync(0, 'utf8').trim().split(/\s+/)[Symbol.iterator]();
const nextNum = () => Number((it.next().value ?? 0));
const N = nextNum();
const A = Array.from({ length: N }, nextNum);
// ここにロジックを実装
