考察
valid Mで同じremainder Xを持つmajority index set Sを考えると、任意のi,j∈SについてM divides |A_i−A_j|となる。
|S|>N/2なのでrandomに二indexを選んだとき両方がSに入る確率は1/4より大きく、正しいdifferenceをconstant probabilityで得られる。
棄却する候補: M=3,…,10^9を列挙してremainder frequenciesを調べる。
modulus候補範囲が大きすぎる。
採用する候補: random pairsのdifferenceをfactorizeし、その3以上のdivisorsを候補Mとして全Aのremainder majorityを検証する。
majority pairを引けば真のMがdifferenceのdivisorに現れ、反復でfailure probabilityが幾何的に減る。
candidateは推測だけで返さず、A_i mod Mのfrequencyが実際にN/2を超えるかO(N)で検証するためfalse positiveはない。
divisor closureより全divisorsの代わりにdifferenceのodd prime factorsと4だけを試しても、valid divisorがある場合のより小さいvalid candidateを拾える。
典型の発動条件
majority集合からの乱択sampling
発動条件: 未知のgood subsetが全体の半数超を占め、その中の少数sampleから答え候補を生成できるとき。
random pairを複数回選び、両方がmajority residue classに入るeventを利用する。
差の約数による合同類候補
発動条件: 複数整数が同じmodulo remainderを持つ未知modulusを探すとき。
sample differenceをfactorizeし、3以上のdivisorsまたは必要十分なprime-factor candidatesを列挙する。
問題固有の要素
入力値はdistinctなのでsampleした異なるindicesのdifferenceは正で、factorization対象0の例外を避けられる。
別の問題へ持ち帰る視点: majority構造はrandom pairが同じhidden classへ入る定数確率を与え、candidate generationのrandomizationに使える。
正当性
過半数の同余類から二要素を引けば、その差は真の法の倍数である。奇素因数または4への候補削減は同余類をさらにまとめるため、過半数条件を保つ。各候補を全要素で確かめるので誤った法を返すことはなく、失敗は有効な対を一度も引けない場合に限られる。
実装上の注意
- 同一pair・同一factorから出るcandidateをdeduplicateし、M≥3かつM≤10^9を満たすものだけ検証する。
- 試行回数を要求failure probabilityから決め、random generatorのindex選択で同じindexを避ける。
復習の核
- 同じmodulo classの二値差はmodulusの倍数になるので、未知modulus候補をdifference factorizationへ移す。
- majorityが保証するconstant hit probabilityと、候補の完全検証を組み合わせてone-sided errorにする。
計算量と制約
時間
T回sample、差の試し割りO(T√D)、候補C個の検査O(CN)、D=maxA−minA。固定Tで失敗確率を制御する。
空間
O(N+√D)、候補とfrequency。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 3 \le N \le 5000; 1 \le A_i \le 10^9; The elements of A are distinct.; All values in the input are integers.
出典