ABC 400 E — Ringo's Favorite Numbers 3

考察

各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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Ringo's Favorite Numbers 3 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 素因数分解と約数構造

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 素因数・約数分解

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

      学習の位置

      体系上の位置: 素因数分解と約数構造

      • 整数の条件を素因数ごとの指数または約数格子上の条件に分解できる。

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

      • 床関数や整数根の値が一定となる区間への分割。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題