ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC152 E - Flatten

問題
提出コード

解法

A_{i}B_{i}の値は、明らかにA_{i}達の最小公倍数になります。
ですが、愚直にやっては途中でオーバーフローをしてしまうため、最小公倍数の素因数を先に列挙してあげることで、後で10^{9}+7でMODを取りながら計算してあげると、オーバーフローせずに最小公倍数を10^{9} +7で割った余りが求められます。
あとは、求めた値をXとして、B_{i} = X / A_{i}の総和を求めてあげればよいです。
素因数を求めるには、全てのA_{i}について、O(\sqrt A_{i})でそれぞれを素因数分解し、素因数と、その個数を求めます。そして、それぞれの素因数について、その個数の最大値を求めてあげればよいです。