考察
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}
出典