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