ABC152 E - Flatten - あっとのTECH LOG

問題原文

問題要旨

長さ $N$ の正整数列 $A$ が与えられる。
以下の条件を満たすような正整数列 $B$ を構築した時の、 $\sum_{}^{N} B_i$ の最小値を [tex: 10⁹ + 7] で割ったあまりを求めよ。

任意の $i, j$ について、 $A_iB_i = A_jB_j$ が成り立つ。
$1 \leq N \leq 10^{4}$
$1 \leq A_i \leq 10^{6}$

解法

少し実験すると答えは、 $\sum_{}^{N} LCM / A_i$ になる。
あとは LCMを計算すればいい。。。いいだけなのだが。。。いつものようにGCDからLCMを求めようとすると、数がデカすぎて爆発する。
なので、LCMの基本的な定義から求めていく。具体的には、各 $A_i$ を素因数分解して、LCMになるために必要な素因数の種類と個数を更新することで、LCMの素因数を求めればいい。
答えを求めるフェーズでは逆元を用いること。

実装

from collections import defaultdict
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7


# 素因数分解
def prime_factorization(n):
    table = []
    for x in range(2, int(n ** 0.5) + 1):
        while n % x == 0:
            table.append(x)
            n //= x
    if n > 1:
        table.append(n)
    return table


# LCMの素因数
prime_max_factors = defaultdict(int)
for a in A:
    prime_factors = Counter(prime_factorization(a))
    for k, v in prime_factors.items():
        # 素因数の数と種類を包むように更新
        prime_max_factors[k] = max(prime_max_factors[k], v)


# LCM計算
LCM = 1
for k, v in prime_max_factors.items():
    LCM *= pow(k, v, MOD)
LCM %= MOD

# 答えを出す
ans = 0
for a in A:
    ans += LCM * pow(a, MOD - 2, MOD)
    ans %= MOD

print(ans % MOD)

感想

あぁあ〜〜〜〜。。。忘れがちだ。。。勉強になりました。。。
ところでPythonなら強引にLCMを計算して殴れるらしい（）