ABC 445 E — Many LCMs

考察

最小公倍数を求める対象から一要素を除くとき、変わり得るのは、その要素だけが最大の指数を持つ素因数である。素数ごとに最大と次点の指数を持てば、残りの要素を調べ直さずに答えを復元できる。

各要素を除くたびに残りの最小公倍数を計算し直すと、1ケースだけでも O(N2)O(N^2) 回の集約が必要になる。そこで、全要素の最小公倍数を共有し、除いた要素の影響だけを差し引くことを考える。最小公倍数そのものは巨大になり得るので、まず素因数の指数で変化を捉える。

素数 pp に対し、AiA_i に含まれる pp の指数を vi(p)v_i(p) とする。pp を含まない要素の指数は 00 である。これらを重複も含めて大きい順に見た上位二つを e1(p),e2(p)e_1(p),e_2(p) と書くと、要素 AkA_k を除いた後の最大指数は次で決まる。

  • vk(p)<e1(p)v_k(p)<e_1(p) なら、最大を持つ別の要素が残るので e1(p)e_1(p) のまま。
  • vk(p)=e1(p)v_k(p)=e_1(p) なら、最大を一つ取り除いた後の値は e2(p)e_2(p)。最大が複数あれば e2(p)=e1(p)e_2(p)=e_1(p) なので変わらない。

例えば A=(4,8,8)A=(4,8,8) の 22 の指数は (2,3,3)(2,3,3) であり、最大と次点はともに 33 である。どの要素を除いても指数 33 が残り、答えは (8,8,8)(8,8,8) になる。「次点」を最大とは異なる指数 22 としてしまうと、後ろの 88 を除いた答えを誤って 44 にしてしまう。また、A=(4,1)A=(4,1) なら指数は (2,0)(2,0) なので、次点の 00 も必要になる。

全要素の最小公倍数を LL、AkA_k を除いた最小公倍数を LkL_k とすると、整数としては

L=∏ppe1(p),Lk=L∏p∣Akvk(p)=e1(p)pe1(p)−e2(p)\begin{aligned} L&=\prod_p p^{e_1(p)},\\ L_k&=\frac{L}{\displaystyle\prod_{\substack{p\mid A_k\\v_k(p)=e_1(p)}}p^{e_1(p)-e_2(p)}} \end{aligned}

となる。分母では AkA_k の素因数だけを調べればよく、最大が重複した素数の因子は p0=1p^0=1 となる。以下では MOD=998244353\mathrm{MOD}=998244353 とし、LL の剰余から分母の逆元を掛けて LkL_k の剰余を求める。逆元を使える理由は「正当性」で確認する。

ここで、入力は複数ケースからなり、要素数の総和に上限がある。値の上限 V=107V=10^7 に対する最小素因数表は全ケースで共通なので、ケースの処理に入る前に篩で一度だけ作る。一方、最大・次点の指数はケースごとに別の値であり、そのケースに出現した素数だけをキーとする空の連想配列から始める。毎回長さ V+1V+1 の指数表をゼロで埋めると O(TV)O(TV) 時間がかかり、要素数の総和が小さくても間に合わない。

各ケースでは次の順に処理する。

  1. 各 AiA_i を最小素因数表で分解し、異なる素数ごとの組 (p,vi(p))(p,v_i(p)) を要素ごとに保存する。残り値 x>1x>1 から最小素因数 pp を取り出し、pp で割れるだけ割って指数を数える操作を繰り返す。Ai=1A_i=1 の因数リストは空になる。
  2. 各組を使って、その素数の最大・次点を更新する。初登場時は両方 00 とする。新しい指数 ee が最大より大きければ、旧最大を次点へ移して最大を ee にする。それ以外は次点と ee の大きい方を新しい次点にする。最大と等しい ee も後者に入れるので、重複を正しく数えられる。
  3. 連想配列にある素数だけを走査し、∏ppe1(p) mod MOD\prod_p p^{e_1(p)}\bmod\mathrm{MOD} を計算する。積の初期値は 11 とする。
  4. 各 kk の答えをその積で初期化し、保存した AkA_k の因数リストを走査する。vk(p)=e1(p)v_k(p)=e_1(p) のときだけ、pe1(p)−e2(p)p^{e_1(p)-e_2(p)} の逆元を掛ける。このケースの全答えを出力してから、因数リストと連想配列を破棄して次のケースへ進む。最小素因数表はそのまま再利用する。

典型の発動条件

素数指数ごとの top-2

一要素を除いた後の最大値を全要素について求めるときは、重複を含む最大と次点を保持する。最小公倍数なら素数の指数ごとにこの方法を使える。最大公約数へ応用する場合は、指数の最小と次に小さい値を使う。

複数ケースで要素数の総和だけが制限されているときは、前処理とケースごとの初期化も分けて数える。共通の表を一度作り、変化する情報は実際に現れたキーだけ管理すれば、ケース数と値域の積を避けられる。

問題固有の要素

巨大な最小公倍数を整数として構築せず、指数で除去する因子を特定してから法上の積へ移す。今回はすべての素因数が法より小さいため、必要な割り算を逆元の乗算で実行できる。

正当性

最小公倍数における素数 pp の指数は、各要素に含まれる指数の最大値 e1(p)e_1(p) である。更新手順は、処理済みの指数に 00 を補って大きい順に見た上位二つを保つ。したがって、全要素の処理後は、重複と指数 00 を含めた正しい e1(p),e2(p)e_1(p),e_2(p) が得られる。

AkA_k の指数が最大未満なら最大を持つ要素が残り、最大と等しければ一つ除いた後の最大は e2(p)e_2(p) になる。最大が重複した場合も e2(p)=e1(p)e_2(p)=e_1(p) なので同じ規則で扱える。よって手順4で除く因子は、整数の最小公倍数から減る素数冪とちょうど一致する。AkA_k に含まれない素数の指数は変わらないため、その因数リストだけを調べればよい。

さらに、すべての素因数は p≤Ai≤107<998244353p\leq A_i\leq 10^7<998244353 を満たす。法 998244353998244353 は素数なので、各 pp は法と互いに素であり、その冪も可逆である。整数として L=LkDkL=L_kD_k(DkD_k は除く因子の積)が成り立つため、法上でも Lk≡LDk−1(modMOD)L_k\equiv L D_k^{-1}\pmod{\mathrm{MOD}} となる。以上より、巨大な整数を保持せず各答えの剰余を正しく求められる。

実装上の注意

  • 次点は「最大とは異なる値」ではなく、重複を含む二番目の指数である。ある素数が一要素にしか現れなければ、他の要素の指数は 00 なので次点も 00 とする。
  • すべての要素が 11 なら連想配列は空のままで、積の初期値 11 がすべての答えになる。N=2N=2 でも同じ手順で、残った一要素の値を得られる。
  • 次のケースへ最大・次点を持ち越さない。例えば (8,4)(8,4) の次に (2,1)(2,1) を処理するとき、後者の最大・次点は (1,0)(1,0) に戻り、答えは (1,2)(1,2) になる。
  • 指数表を配列で持つ場合も、配列の確保・全体のゼロ初期化は一度だけにする。ケース内で初めて使った素数を別リストへ記録し、終了時はそのリストにある位置だけをリセットする。積の計算もこのリストだけを走査する。
  • 累乗と逆元は二分累乗で計算し、逆元は xMOD−2 mod MODx^{\mathrm{MOD}-2}\bmod\mathrm{MOD} で求められる。剰余同士の乗算は、剰余を取る前に64 bit整数へ広げる。

復習の核

  • 一要素除外後の最大を復元するには、最大が何度現れたかを失わない上位二つを持つ。
  • 複数ケースでは、要素数の総和で抑えられる処理と、値域全体への処理を区別する。共有する篩は一度だけ、ケース固有の状態は使った素数だけ初期化する。
  • 巨大な積を法上で割り戻すときは、除く因子が法と互いに素である理由まで確認する。

計算量と制約

時間

全ケースの要素数の総和を M=∑NM=\sum N、要素ごとに保存する組 (p,e)(p,e) の全ケース合計を SS とする。例えば 12=22⋅312=2^2\cdot3 は2組であり、11 は0組である。同じ素数でも別の要素に現れれば別の組として数える。V=107V=10^7 とする。

  • 最小素因数表の作成は、全ケースで一度だけ O(Vlog⁡log⁡V)O(V\log\log V) 時間。線形篩ならこの項は O(V)O(V) になる。
  • 入出力とケースごとのリスト確保は合計 O(M)O(M) 時間。素因数分解では、各組の指数が log⁡2V\log_2 V 以下なので、割り算の総回数は O(Slog⁡V)O(S\log V) で抑えられる。
  • 平衡二分探索木による map では、各組に対する更新・参照が O(log⁡(S+1))O(\log(S+1)) 時間。全ケースの連想配列の走査・破棄は、各ケースのキー数がそのケースの組数以下なので合計 O(S)O(S) 時間。
  • 素数冪の計算と逆元の計算は、組あたり O(log⁡MOD)O(\log\mathrm{MOD}) 時間で抑えられ、合計 O(Slog⁡MOD)O(S\log\mathrm{MOD}) 時間。ここでは V<MODV<\mathrm{MOD} を使っている。

したがって、map を使う場合の全ケース合計は

O(Vlog⁡log⁡V+M+S(log⁡(S+1)+log⁡MOD))\begin{aligned} O\bigl(&V\log\log V+M\\ &+S(\log(S+1)+\log\mathrm{MOD})\bigr) \end{aligned}

となる。素因数分解の項も log⁡V<log⁡MOD\log V<\log\mathrm{MOD} により含めている。ハッシュ表で更新・参照が期待 O(1)O(1) 時間なら、全体は期待 O(Vlog⁡log⁡V+M+Slog⁡MOD)O(V\log\log V+M+S\log\mathrm{MOD}) 時間となる。配列と使用した素数のリストを使う方法でも、この評価が期待値によらず成り立つ。

空間

一度に1ケースずつ処理する。ケース tt の要素数・因数組数を Nt,StN_t,S_t とすると、共有する最小素因数表に O(V)O(V)、そのケースの因数リスト・連想配列・答えに O(Nt+St)O(N_t+S_t) を使う。ピークの使用量は O(V+max⁡t(Nt+St))O(V+\max_t(N_t+S_t)) であり、全ケースのリストを同時には保持しない。

制約との対応

1≤T≤1051\leq T\leq10^5、各ケースで 2≤N≤2×1052\leq N\leq2\times10^5、全ケースで M≤2×105M\leq2\times10^5、1≤Ai≤1071\leq A_i\leq10^7。時間制限は2秒、メモリ制限は1024 MiBである。

10710^7 以下の整数に含まれる異なる素因数は高々8個なので、S≤8MS\leq8M である。これは小さい方から8素数の積が 96996909699690、9素数の積が 223092870>107223092870>10^7 となることから分かる。N=2N=2 のケースが 10510^5 個あっても、篩の作成は一度、ケース内の処理は合計の M,SM,S に応じた量で済む。毎回値域全体を初期化する O(TV)O(TV) の処理は含めない。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Many LCMs の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

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

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

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

    補助タグ: 法上の四則演算・高速累乗・逆元

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

    学習の位置

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

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

    先に読む単元:

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

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

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題