問題リンク
問題概要
\(N\)個の正整数\(A_1,…A_N\)が与えられる。
正整数列\(B_1,…B_N\)であって、\(A_iB_i = A_jB_j\) が全ての\( (i,j)(1\leqq i < j\leqq N)\)にして成り立つ物のうち、\(B_1+B_2+ \ldots +B_N\)の最小値を\(10^9+7\)で割った余りを求めよ。
解法
\(A_1B_1 = A_2B_2 = … = A_NB_N\) である。この値を\(L\)と置くと、\(L\)は\(A_1,…,A_N\)の公倍数でなければならない。よって\(L\)は最小公倍数になるように取り、\(B_1,…,B_N\)を求めればよい。
素朴に最小公倍数を求めるとオーバーフローするので、各\(A_i\)を素因数分解して
\(L = 2^{max(A_iが含む2の次数)} \times 3^{max(A_iが含む3の次数)} \times 5^{max(A_iが含む5の次数)} \times …\)
として最小公倍数を求め、素因数分解した形でmapなどで管理する。
最後に各\(B_i\)を求める。もう一度\(A_i\)を素因数分解して指数の差分を取って求めても良いが、mod逆元を使って\(B_i = L \times modinv(A_i)\) とすると楽。
提出
https://atcoder.jp/contests/abc152/submissions/9611761
感想
好きな問題。
