TROC #16 E - Multiple Multiplication

問題リンク

解説

各要素において、その素因数毎にLCMの要素になる区間の幅はstackを用いるとならしで線形になります。

素因数分解は前計算をしていけば毎回 O(\log a _ {i})でできます。

最後に繰り返し二乗法もすることを考えると、全体で O(\max(a) \log \log \max(a) + n \log {\max(a)} \log n)で解けました

提出コード

https://tlx.toki.id/problems/troc-16/E/submissions/735983