Problem: Given are N positive integers A_1,...,A_N.  Consider positive integers B_1, ..., B_N that satisfy the following condition.  Condition: For any i, j such that 1 \leq i < j \leq N, A_i B_i = A_j B_j holds.  Find the minimum possible value of B_1 + ... + B_N for such B_1,...,B_N.  Since the answer can be enormous, print the sum modulo (10^9 +7).

Submission attempts (in order):
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

d = [0] * (max(A) + 1)
d = {i: 0 for i in range(1, max(A)+1)}
d = defaultdict(int)


def prime_factorization(n):  
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            res.append((i, cnt))
    if n > 1:
        res.append((n, 1))
    return res


pf = []
for a in A:
    res = []
    for i in range(2, int(a ** 0.5) + 1):
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                cnt += 1
                a //= i
            d[i] = max(d[i], cnt)
            res.append((i, cnt))
    if a != 1:
        d[a] = max(d[a], 1)
        res.append((i, cnt))
    pf.append(res)

ans = 0
for i, a in enumerate(A):
    tmpD = d.copy()
    for k, v in pf[i]:
        tmpD[k] -= v
    b = 1
    for k, v in tmpD.items():
        if v == 0:
            continue
        b *= pow(k, v, mod)
        v %= mod
    ans += b
    ans %= mod

print(ans % mod)


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

d = defaultdict(int)

pf = []
for a in A:
    res = []
    for i in range(2, int(a ** 0.5) + 1):
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                cnt += 1
                a //= i
            d[i] = max(d[i], cnt)
            res.append((i, cnt))
    if a != 1:
        d[a] = max(d[a], 1)
        res.append((i, cnt))
    pf.append(res)

ans = 0
for i, a in enumerate(A):
    tmpD = d.copy()
    for k, v in pf[i]:
        tmpD[k] -= v
    b = 1
    for k, v in tmpD.items():
        if v <= 0:
            continue
        b *= pow(k, v, mod)
        v %= mod
    ans += b
    ans %= mod

print(ans % mod)


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

d = defaultdict(int)


def prime_factorization(n):  
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            res.append((i, cnt))
    if n > 1:
        res.append((n, 1))
    return res


for a in A:
    for i in range(2, int(a ** 0.5) + 1):
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                cnt += 1
                a //= i
            d[i] = max(d[i], cnt)
    if a != 1:
        d[a] = max(d[a], 1)

ans = 0
lcm = 1
for k, v in d.items():
    lcm *= pow(k, v, mod)
    lcm %= mod

for a in A:
    if a == 1:
        ans += lcm
        continue
    l = lcm*pow(a, mod-2, mod)
    ans += l
    ans %= mod

print(ans % mod)


Verdicts: Runtime Error

Runtime Error

Accepted