考察
各prime exponentが偶数である条件はNが完全平方数であることと同値である。N=k²とするとdistinct prime factor集合はkと同じなので、kの素因数種類数がちょうど2かだけ調べればよい。
A≤10^12よりk≤10^6で、全平方候補を事前列挙できる。
採用する候補: 1..10^6のdistinct prime factor countをsieveし、count=2のk²をsortしてqueryをupper_boundする
候補は高々10^6個、前計算O(V log log V相当)、各Q query O(log V)で処理できる。
棄却する候補: 各queryから下へ整数を減らしながらfactorizationする
400 number間のgapと素因数分解回数に十分な上界がなく、Q=2×10^5では重い。
prime pを見つけたらpの全multipleへ種類数+1することで指数に関係なくdistinct countを得る。
候補値k²は64 bitで作り、query A以下の最後の位置をupper_bound-1で取る。
spf/count配列を0初期化し、count[p]=0のpをprimeとしてp,2p,…へ+1する。count[k]=2ならk²を候補へ追加する。各Aにupper_bound(candidates,A)直前を答える。
典型の発動条件
平方根への構造変換
発動条件: 全素因数指数が偶数という条件があるとき。
N=k²としてprime factor種類条件をkへ移す。
distinct prime divisor sieve
発動条件: 全n≤Vの素因数種類数を一括で求めたいとき。
各primeのmultipleへ一回ずつ加算する。
問題固有の要素
10^12という上限でも平方数条件により探索対象のrootは10^6へ落ち、query前計算型問題になる。
別の問題へ持ち帰る視点: 指数parity条件を見たら平方free partや平方根へ変数変換し、値域を縮める。
正当性
素因数指数が全て偶数の数はk²と一意に表される。k²とkの相異なるprime集合は同じなので種類数2のkだけ篩で列挙すれば全候補を得る。k昇順はk²昇順だからupper_bound直前がquery以下の最大候補になる。
実装上の注意
- 1は素因数0種で除外する。k*kは64 bitで計算し、保証によりupper_boundが先頭になるcaseはない。
復習の核
- k≤500をtrial divisionしてsieve countと比較し、p²q²、より高い偶数指数、三prime平方が正しく分類されるか確認する。
計算量と制約
時間
O(V log log V+Q log V)、V=10^6。素因数種類数の篩と候補二分探索。
空間
O(V+Q)、query逐次ならO(V)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq Q \leq 2 \times 10^5; For each query, 36 \leq A \leq 10^{12}.; All input values are integers.
出典