E - Flatten
LCM
式変形
考察
こういう数学系の問題はとりあえず式変形して嬉しい形にできないか?というのを試していきます
例えばシグマの計算だったら分けて考えれるよね…みたいなのとか
入力例から、LCMが重要なのかな…?という気持ちになります
今回、LCMを求めてBi = LCM / Ai のようになることが分かるので、LCM / Ai の総和を求めていきたいです。
https://gyazo.com/f788bf9b7c7669620caa41df7bb0918f
4つでやりたいことを式変形すると、このような感じになります。
LCMをそのまま求めようとするとオーバーフローしてしまうので、mapでmp[i] // lcmを素因数分解した時、iが何回出てくるかみたいにするといいです LCMの定義をちゃんと復習しよう、知らんけど…
この$ A_2A_3A_4 + A_1A_3A_4 + A_1A_2A_4 + A_1A_2A_3のぶぶん、「ひとつだけ抜けてる…」みたいなやつなので左右から累積積を取ってずらしながら求めていくあのテクが使えそうです
$ A_1A_2A_3A_4で割るやつは、逆元を掛けてあげればいいです