abc152e
考えたこと
AiBiはAiの公倍数である、iによらず同じである
AiBiをAiで割ったものがBiである
というわけで数学的には最小公倍数を求めて、各Aiで割って、掛け合わせたものが答え
10^6オーダーAの値が10^4個Nあるので素朴に計算すると大変なことになる
最小公倍数はAiをすべて掛けたものを最大公約数で割ったもの
最大公約数をまず求める
これは10^4回log(10^6)オーダーの計算をするだけなので十分間に合う O(N log A)
一つの数の逆元なのでlog(mod)くらいで求まる
線形オーダーの前処理で、本処理は定数オーダー
足しあわせれば答えになる
公式解説
最小公倍数になるというところまでの考察は同じ
その後、素因数分解された状態で最小公倍数を求めようとしている
素因数分解が平方根オーダーで10^3、それを10^4回やるので10^7、間に合う
前処理によって素因数分解を高速化することでO(A+NlogA)になるとの話
高速素因数分解だね、O(A)のテーブルを事前に作ることで試し割りが不要になって素因数分解が対数オーダーになる ここまでやって僕の解法と同じくらいのオーダーかな？