ABC 401-500/ABC445E - Many LCMs - 競技プログラミング用 知識集積所

---

問題

ABC445E

必要知識

B以下レベルの内容は省略

• 素因数分解
• 剰余類換※

考え方

最小公倍数は、基本的に以下の手順で求められる。

• 全ての数を素因数分解する
• 各素数について、その冪の最大値を確認する
• 各素数ごとに最大の冪で累乗し、全てを掛け算する

今回の場合、1つを除いた最大公約数を求めることになる。
よって、最大値だけではなく2番目に大きい値も調べておく。
除いたものがある素数の最大の冪を持つ数だった場合、代わりに2番目の冪を使って計算すればよい。

とはいえ、最後の掛け算を毎回愚直にやっているとTLEする。
そこで、最初に全ての最小公倍数を出しておき、「それを取り除いたら最小公倍数が何分の1になるか」を考えていくことになる。
つまり、除いたものがある素数の最大の冪を持つ数だった場合、その素数の「1位の冪-2位の冪」乗で割ればよい。

答えはmod998244353での値なので、剰余類環も参照。

解答例

解答例

注意点

冪の最大値はmap※などで持つ

単純にvectorに入れると、掛け算で最大素数の値と同じくらいの処理回数が必要になる。
しかしこの問題はマルチテストケース問題なので、問題数が多いとTLEしてしまう。
map※などで必要な素数のところだけ値を持つことで、少個数の問題が大量に詰め込まれている場合にもすぐおわるようにしておく必要がある。

別解