ABC 315 G — Ai + Bj + Ck = X (1 <= i, j, k <= N)

考察

N≤10^6 なので三変数のうち i だけは全探索できる。固定後は正の範囲制約付き一次不定方程式 Bj+Ck=Y に落ちる。

Bj+Ck=Y は gcd(B,C) が Y を割るときだけ解を持ち、一つの解が得られれば全解は j=j0+t(C/g), k=k0−t(B/g) という一次 parameter で表せる。

採用する候補: i を列挙し、extgcd で得た基準解に対する整数 parameter t の許容区間長を floor/ceil 除算で数える。

各 i を O(1) の数論計算で処理でき、全体 O(N+log max(B,C)) になる。

棄却する候補: i,j を二重ループし、残りから k が整数かを判定する。

N² は最大10^12回で、一次方程式の解が等差数列をなすことを使えていない。

extgcd の uB+vC=g を Y/g 倍して基準解を得る前に Y%g=0 を検査する。

1≤j0+tC/g≤N と 1≤k0−tB/g≤N の二つから t の整数区間を取り、その共通部分の個数 max(0,R−L+1) を加える。

g,u,v=extgcd(B,C) を一度求める。i=1..N で Y=X−Ai とし、Y≤0 または Y%g≠0 なら skip。基準 j0=u(Y/g), k0=v(Y/g) を作り、二変数の上下限制約から signed floor_div/ceil_div で t の下限・上限を求め、その交差長を答えへ加える。

典型の発動条件

一次不定方程式の範囲内解数

発動条件: ax+by=c の整数解を箱型範囲内で数えるとき。

extgcd の一解から一般解を作り、自由 parameter の区間を整数除算で交差する。

問題固有の要素

三変数でも一軸の上限10^6は走査可能で、残り二軸を数式で一括処理すればよいという制約配分になっている。

別の問題へ持ち帰る視点: 多変数線形式は、列挙できる軸数と Diophantine equation で消せる軸数を分けて見積もる。

正当性

i固定後のBj+Ck=Yが解を持つのはg=gcd(B,C)がYを割るとき。基準解から全解はj=j0+tC/g,k=k0−tB/gと一意に表される。j,k各々の1..N制限がtの閉整数区間を与えるため、交差長がそのiの全解数になる。異なるiは別三tupleなので合計に重複はない。

実装上の注意

  • 言語の整数除算が負数を0方向へ丸める場合、数学的 floor/ceil helper を用意する。Y/g 倍の途中積は 128 bit で overflow を避ける。

復習の核

  • extgcd で一解を得た後、一般解の符号を暗記せず代入して確かめる。境界数え上げは負の基準解を含むテストを必ず作る。

計算量と制約

時間

O(N+log min(B,C))。extgcdは一度だけ、各iの整数区間交差は定数時間。

空間

O(1)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: All input values are integers.; 1 \le N \le 10^6; 1 \le A,B,C \le 10^9; 1 \le X \le 3 \times 10^{15}

出典

分類・前提・執筆情報

掲載状態: 収録済み

Ai + Bj + Ck = X (1 <= i, j, k <= N) の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: gcdと整数解の成立条件

主題
  • gcdと整数解の成立条件: 整除条件や一次不定方程式の可解性をgcdで特徴付け、必要なら拡張EuclidでBézout整数解を構成できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: Bézout等式・一次不定方程式

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: gcdと整数解の成立条件

      • 整除条件や一次不定方程式の可解性をgcdで特徴付け、必要なら拡張EuclidでBézout整数解を構成できる。

      この解説で扱わないこと:

      • 差や周期をgcdへ集約する不変量の抽出は「gcd不変量・差分構造」で扱う。複数の合同条件の統合は合同式・CRT、有理近似は連分数・Stern–Brocotの単元へ進む。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題