考察
A_iを含むK要素のGCD候補dはA_iの約数であり、さらに列全体でdの倍数がK個以上なければならない。この二条件は十分でもある。
値上限10^6なので、各dの倍数個数を倍数sieveで全て数え、条件を満たすdをその倍数へ配れる。
採用する候補: frequencyの倍数和でvalid divisorを判定し、valid dを倍数nの答えへ昇順上書きする
t[d]=Σ_{multiple}freqをO(V log V)で求め、t[d]≥Kなら全multiple nのbest[n]=dを更新すれば最大valid divisorが残る。
棄却する候補: 各A_iの全約数を列挙し、その都度全配列で倍数個数を数える
要素ごとの重複計算が大きく、同じ値・同じ約数の判定を何度も繰り返す。
GCDをちょうどdにする必要はなく「少なくともdで割れる」K個を選べば、そのGCDはd以上で、最大候補探索の十分性が得られる。
dを昇順に処理してbest[multiple]=dと代入すれば、最後の値が最大のvalid約数になる。
freq[value]を数える。d=1..Vでmultipleを走査してt[d]を求める。t[d]≥Kのdについて全multipleへbest[multiple]=dを設定し、各A_iにbest[A_i]を出力する。
典型の発動条件
倍数sieve
発動条件: 全dについて入力中のdの倍数個数を求めたいとき。
frequencyをmultiple方向に足す。
約数条件の倍数配布
発動条件: 各nに対する最大valid divisorを一括計算したいとき。
valid dからその倍数nへ値を伝播する。
問題固有の要素
選ぶK要素の組合せを考えず、候補GCD dごとに「選択可能な母集団size」だけ判定すればよい。
別の問題へ持ち帰る視点: subsetのGCD最大化では、dで割れる要素数という単調な可否条件へ切り替える。
正当性
K要素のgcdはA_iの約数で、全体にその倍数がK個以上必要。逆にこの条件を満たすdならA_iを含むK個の倍数を選べ、そのgcdはdの倍数である。最大valid約数dより大きいgcdが得られたならそれ自身もvalid約数で矛盾するので、最大dが最適gcdに一致する。昇順上書きでそれを保存する。
実装上の注意
- V=max(A)までに配列を絞り、t[d]とfrequencyはNを保持できる型にする。昇順上書きか降順初回代入のどちらかを一貫する。
復習の核
- N≤12で各iを含むK-combinationを全列挙し、duplicate値、K=1,N、A_i=1をsieve結果と比較する。
計算量と制約
時間
O(V log V+N)。倍数個数とbest約数の倍数配布を行う。
空間
O(V+N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq K \leq N \leq 1.2 \times 10^6; 1 \leq A_i \leq 10^6; All input values are integers.
出典