Problem:


Score : 500 points

Problem Statement

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).

Constraints

1 \leq N \leq 10^4

1 \leq A_i \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the minimum possible value of B_1 + ... + B_N for B_1,...,B_N that satisfy the condition, modulo (10^9 +7).

Sample Input 1

3
2 3 4

Sample Output 1

13

Let B_1=6, B_2=4, and B_3=3, and the condition will be satisfied.

Sample Input 2

5
12 12 12 12 12

Sample Output 2

5

We can let all B_i be 1.

Sample Input 3

3
1000000 999999 999998

Sample Output 3

996989508

Print the sum modulo (10^9+7).



Sample input:
3
2 3 4


Sample output:
13

Submission status: Time Limit Exceeded

Solution code:
class Sieve:
    """区間[2,n]の値を素因数分解する"""

    def __init__(self, n=1):
        primes = []
        f = [0] * (n + 1)
        f[0] = f[1] = -1
        for i in range(2, n + 1):  # 素数を探す
            if f[i]: continue
            primes.append(i)
            f[i] = i  # 素数には自身を代入
            for j in range(i * i, n + 1, i):  # 合成数に素因数を書き込む
                if not f[j]:
                    f[j] = i  # 最小の素因数を代入
        self.primes = primes
        self.f = f

    def is_prime(self, x) -> bool:  # 素数判定
        return self.f[x] == x

    def factor_list(self, x) -> list:  # 素因数分解の昇順リスト, [2,2,3,5,...]
        res = []
        while x != 1:
            res.append(self.f[x])
            x //= self.f[x]
        return res

    def factor(self, x) -> list:  # 素因数分解の頻度リスト, [[2,x],[3,y],[5,z],...]
        fl = self.factor_list(x)
        if not fl: return []
        res = [[fl[0], 0]]
        for p in fl:
            if res[-1][0] == p:
                res[-1][1] += 1
            else:
                res.append([p, 1])
        return res


def main():
    from collections import defaultdict

    MOD = 10 ** 9 + 7
    A_MX = 10 ** 6

    N = int(input())
    *a, = map(int, input().split())

    s = Sieve(n=A_MX)

    lcm = defaultdict(int)

    factors = []
    for x in a:
        f = defaultdict(int)
        for prime, cnt in s.factor(x):
            lcm[prime] = max(lcm[prime], cnt)
            f[prime] = cnt
        factors.append(f)

    ans = 0
    for f in factors:
        t = 1
        for prime, cnt in lcm.items():
            power = max(0, cnt - f[prime])
            t *= pow(prime, power, MOD)
            t %= MOD
        ans += t
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce


def lcm(x,y):
    return (x*y)//gcd(x,y)


def lcm_list(nums):
    return reduce(lcm,nums,1)

mod=10**9+7
n=int(input())
A=list(map(int,input().split()))
num=lcm_list(A)
cnt=0
for i in A:
    cnt +=num//i
print(cnt%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


# 最大公約数
def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b


# 最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)


def main():
    n = int(input())
    A = list(map(int, input().split()))
    l = 1
    for a in A:
        l = lcm(l, a)
    ans = 0
    for a in A:
        ans += l * pow(a, MOD - 2, MOD)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from fractions import gcd
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    lsd = a[0]
    for i in range(1, n):
        lsd = (lsd * a[i]) // gcd(lsd, a[i])
 
    ans = 0
    for i in range(n):
        ans += (lsd//a[i]) % mod
 
    print(int(ans % mod))
 
 
if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from fractions import gcd
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    lsd = a[0]
    for i in range(1, n):
        lsd = (lsd * a[i]) // gcd(lsd, a[i])

    ans = 0
    for i in range(n):
        ans += (lsd//a[i]) % mod

    print(int(ans % mod))


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


# 素因数分解
def prime_factorize(n):
    a = defaultdict(int)
    while n % 2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] += 1
    return a


def main():
    n = int(input())
    A = list(map(int, input().split()))
    l = defaultdict(int)
    for a in A:
        c = prime_factorize(a)
        for k, v in c.items():
            l[k] = max(l[k], v)
    ans = 0
    lcm = 1
    for k, v, in l.items():
        lcm *= k ** v
    for a in A:
        ans += lcm // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from operator import itemgetter
from bisect import bisect_left, bisect_right, insort_left, insort_right
# import sys
# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
# INF = float("inf")



# 素因数分解
def prime_factorize(n):
    a = defaultdict(int)
    while n % 2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] += 1
    return a

def main():
    n = int(input())
    A = list(map(int, input().split()))
    l = defaultdict(int)
    for a in A:
        c = prime_factorize(a)
        for k, v in c.items():
            l[k] = max(l[k], v)
    # print(l)
    ans = 0
    lcm = 1
    for k, v, in l.items():
        lcm *= k ** v
    # print(lcm)
    for a in A:
        ans += lcm // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    def lcm(X, Y):
        x = X
        y = Y
        if y > x:
            x, y = y, x
        while x % y != 0:
            x, y = y, x % y
        return X * Y // y
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    lsd = a[0]
    for i in range(1, n):
        lsd = lcm(lsd, a[i])

    ans = 0
    for i in range(n):
        ans += (lsd//a[i]) % mod

    print(int(ans % mod))
resolve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
MOD = 10 ** 9 + 7


# 素因数分解
def prime_factorize(n):
    a = defaultdict(int)
    while n % 2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] += 1
    return a

def main():
    n = int(input())
    A = list(map(int, input().split()))
    l = defaultdict(int)
    for a in A:
        c = prime_factorize(a)
        for k, v in c.items():
            l[k] = max(l[k], v)
    ans = 0
    lcm = 1
    for k, v, in l.items():
        lcm *= k ** v
    for a in A:
        ans += lcm // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from fractions import gcd
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    lsd = a[0]
    for i in range(1, n):
        lsd = (lsd * a[i]) // gcd(lsd, a[i])
 
    ans = 0
    for i in range(n):
        ans += (lsd//a[i]) % mod
 
    print(int(ans % mod))
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from fractions import gcd
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    lsd = a[0]
    for i in range(1, n):
        lsd = (lsd * a[i]) // gcd(lsd, a[i])

    ans = 0
    for i in range(n):
        ans += (lsd//a[i]) % mod

    print(int(ans % mod))
resolve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd

    MOD = 10 ** 9 + 7

    N = int(input())
    A = list(map(int, input().split()))

    tmp = 1
    for a in A:
        tmp *= a // gcd(tmp, a)

    ans = 0
    for a in A:
        ans += (tmp // a)
    ans %= MOD

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd

    MOD = 10 ** 9 + 7

    N = int(input())
    A = list(map(int, input().split()))

    tmp = 1
    for a in A:
        tmp *= a // gcd(tmp, a)

    ans = 0
    for a in A:
        ans += (tmp // a) % MOD
        ans %= MOD

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

MOD = 10 ** 9 + 7

N = int(input())
A = list(map(int, input().split()))

tmp = 1
for a in A:
    tmp *= a // gcd(tmp, a)

ans = 0
for a in A:
    ans += (tmp // a) % MOD
    ans %= MOD

print (ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

# 最大公約数
def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b


# 最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

def main():
    n = int(input())
    A = list(map(int, input().split()))
    l = 1
    for a in A:
        l = lcm(l, a)
    ans = 0
    for a in A:
        ans += l // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd

    MOD = 10 ** 9 + 7

    N = int(input())

    A = list(map(int, input().split()))

    B = [1] * (N + 1)

    for index, a in enumerate(A):
        tmp = gcd(B[index], a)
        B[index + 1] = B[index] * a // tmp

    C = [1] * (N + 1)
    for i in range(N - 1, -1, -1):
        tmp =gcd(C[i + 1], A[i])
        C[i] = C[i + 1] * A[i] // tmp

    # print (B)
    # print (C)

    ans = 0
    for i in range(N):
        tmp1 = gcd(B[i], C[i + 1])
        tmp2 = B[i] * C[i + 1] // tmp1

        tmp3 = gcd(tmp2, A[i])
        tmp4 = tmp2 * A[i] // tmp3

        ans += (tmp4 * pow(A[i], MOD - 2, MOD) % MOD)
        ans %= MOD

        # print (ans)

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])
        if temp!=1:
            arr.append([temp, 1])
        if arr==[]:
            arr.append([n, 1])
        return arr

    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    import copy

    gcddict = {}
    adiv = []
    for i in range(n):
        primes = factorization(a[i])
        adiv.append(primes)
        for j in range(len(primes)):
            if primes[j][0] in gcddict:
                gcddict[primes[j][0]] = max(gcddict[primes[j][0]], primes[j][1])
            else:
                gcddict[primes[j][0]] = primes[j][1]
    ans = 0
    for i in range(n):
        val = 1
        test = copy.deepcopy(gcddict)
        primes = adiv[i]
        for j in range(len(primes)):
            test[primes[j][0]] -= primes[j][1]
        for k in test.keys():
            val *= pow(k, test[k], mod)
        ans += val
    print(ans % mod)
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])
        if temp!=1:
            arr.append([temp, 1])
        if arr==[]:
            arr.append([n, 1])
        return arr

    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    import copy

    gcddict = {}
    adiv = []
    for i in range(n):
        primes = factorization(a[i])
        adiv.append(primes)
        for j in range(len(primes)):
            if primes[j][0] in gcddict:
                gcddict[primes[j][0]] = max(gcddict[primes[j][0]], primes[j][1])
            else:
                gcddict[primes[j][0]] = primes[j][1]
    ans = 0
    for i in range(n):
        val = 1
        test = copy.deepcopy(gcddict)
        primes = adiv[i]
        for j in range(len(primes)):
            test[primes[j][0]] -= primes[j][1]
        for k in test.keys():
            val *= pow(k, test[k], mod)
            val %= 10**9 + 7
        ans += val
        ans %= 10**9 + 7
    print(ans % (10**9 + 7))
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])
        if temp!=1:
            arr.append([temp, 1])
        if arr==[]:
            arr.append([n, 1])
        return arr

    n = int(input())
    a = list(map(int, input().split()))
    import copy

    gcddict = {}
    adiv = []
    for i in range(n):
        primes = factorization(a[i])
        adiv.append(primes)
        for j in range(len(primes)):
            if primes[j][0] in gcddict:
                gcddict[primes[j][0]] = max(gcddict[primes[j][0]], primes[j][1])
            else:
                gcddict[primes[j][0]] = primes[j][1]
    ans = 0
    for i in range(n):
        val = 1
        test = copy.deepcopy(gcddict)
        primes = adiv[i]
        for j in range(len(primes)):
            test[primes[j][0]] -= primes[j][1]
        for k in test.keys():
            val *= k **test[k]
            val %= 10**9 + 7
        ans += val
        ans %= 10**9 + 7
    print(ans % (10**9 + 7))
resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    def factorization(n):
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])

        if temp!=1:
            arr.append([temp, 1])

        if arr==[]:
            arr.append([n, 1])

        return arr

    n = int(input())
    a = list(map(int, input().split()))
    import copy
    gcddict = {}
    for i in range(n):
        primes = factorization(a[i])
        for j in range(len(primes)):
            if primes[j][0] in gcddict:
                gcddict[primes[j][0]] = max(gcddict[primes[j][0]], primes[j][1])
            else:
                gcddict[primes[j][0]] = primes[j][1]
    ans = 0
    for i in range(n):
        val = 1
        test = copy.deepcopy(gcddict)
        primes = factorization(a[i])
        for j in range(len(primes)):
            test[primes[j][0]] -= primes[j][1]
        for k in test.keys():
            val *= k **test[k]
            val %= 10**9 + 7
        ans += val
        ans %= 10**9 + 7
    print(ans % (10**9 + 7))

resolve()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)

n = int(input())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7

LCM = 1
for i in range(n):
    LCM = lcm(LCM, a[i])

ans = 0
for i in range(n):
    ans = (ans + LCM // a[i]) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
from fractions import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

N = ir()
A = lr()
lcm = 1
for a in A:
    lcm *= a // gcd(lcm, a)

answer = 0
for a in A:
    answer += lcm // a
    answer %= MOD

print(answer % MOD)
# np.int64とint型の違いに注意

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)

n = int(input())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7

LCM = 1
for i in range(n):
    LCM = lcm(LCM, a[i])

ans = 0
for i in range(n):
    ans = ans + LCM // a[i]
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from fractions import gcd
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    A=list(map(int,readline().split()))

    mod=10**9+7
    l=1
    for i in range(N):
        l=l*A[i]//gcd(l,A[i])

    res=0
    for i in range(N):
        res+=l//A[i]
        res%=mod
    
    print(res)

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
from fractions import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

N = ir()
A = lr()
lcm = 1
for a in A:
    lcm *= a // gcd(lcm, a)

answer = 0
for a in A:
    answer += lcm // a

print(answer % MOD)
# np.int64とint型の違いに注意

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
from fractions import gcd
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

N = ir()
A = lr()
lcm = 1
for a in A:
    lcm *= a // gcd(lcm, a)

A = np.array(A)
answer = (lcm // A % MOD).sum() % MOD
print(answer % MOD)
# np.int64とint型の違いに注意

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import gcd
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
g = 0
lcm = 1
for x in a:
  g = gcd(lcm, x)
  lcm *= x // g
res = 0
for x in a:
  res += lcm // x
  res %= mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7


def main():
    import sys
    input = sys.stdin.buffer.readline
    _ = int(input())
    A = [int(i) for i in input().split()]

    def gcd(x, y):
        if y == 0:
            return x
        while y != 0:
            x, y = y, x % y
        return x

    def lcm(x, y):
        return x*y//gcd(x, y)

    L = A[0]
    for a in A[1:]:
        L = lcm(L, a)
    ans = 0
    for a in A:
        ans += L//a
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd

    MOD = 10 ** 9 + 7

    N = int(input())

    A = list(map(int, input().split()))

    B = [1] * (N + 1)

    for index, a in enumerate(A):
        tmp = gcd(B[index], a)
        B[index + 1] = B[index] * a // tmp

    C = [1] * (N + 1)
    for i in range(N - 1, -1, -1):
        tmp =gcd(C[i + 1], A[i])
        C[i] = C[i + 1] * A[i] // tmp

    # print (B)
    # print (C)

    ans = 0
    for i in range(N):
        tmp1 = gcd(B[i], C[i + 1])
        tmp2 = B[i] * C[i + 1] // tmp1

        tmp3 = gcd(tmp2, A[i])
        tmp4 = tmp2 * A[i] // tmp3

        ans += (tmp4 // A[i] % MOD)
        ans %= MOD

        # print (ans)

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

MOD = 10 ** 9 + 7

N = int(input())

A = list(map(int, input().split()))

B = [1] * (N + 1)

for index, a in enumerate(A):
    tmp = gcd(B[index], a)
    B[index + 1] = B[index] * a // tmp

C = [1] * (N + 1)
for i in range(N - 1, -1, -1):
    tmp =gcd(C[i + 1], A[i])
    C[i] = C[i + 1] * A[i] // tmp

# print (B)
# print (C)

ans = 0
for i in range(N):
    tmp1 = gcd(B[i], C[i + 1])
    tmp2 = B[i] * C[i + 1] // tmp1

    tmp3 = gcd(tmp2, A[i])
    tmp4 = tmp2 * A[i] // tmp3

    ans += (tmp4 // A[i] % MOD)
    ans %= MOD

    # print (ans)

print (ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys
n=int(sys.stdin.readline())
a=list(map(int, sys.stdin.readline().split()))

MOD=10**9+7
#a,bの最小公倍数
def lcm(a, b):
    return a*b // gcd (a, b)
l=1
for i in a:
    l=lcm(i,l)
ans=0
for i in a:
    ans+=(l//i)%MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))

MOD=10**9+7
#a,bの最小公倍数
def lcm(a, b):
    return a*b // gcd (a, b)
l=1
for i in a:
    l=lcm(i,l)
ans=0
for i in a:
    ans+=(l//i)%MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))

MOD=10**9+7
#a,bの最小公倍数
def lcm(a, b):
    return a*b // gcd (a, b)
l=[0]*n
l[0]=lcm(1,a[0])

for i in range(n-1):
    l[i+1]=lcm(a[i+1],l[i])

ans=0
for i in a:
    ans+=(l[-1]//i)%MOD

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
def lcm(X,Y):
    x=X
    y=Y
    if y>x:
        x,y=y,x
    while x%y!=0:
        x,y=y,x%y
    return X*Y//y

MOD = 10**9 + 7
ans = 0
n = int(input())
a = list(map(int, input().split()))
l = 1
for i in range(n):
    Q=lcm(l,a[i])
    ans*=Q//l
    l=Q
    ans+=Q//a[i]
print(int(ans%MOD))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
n=int(input())
l=list(map(int,input().split()))
f=l[0]
from fractions import gcd

for i in l:
    f=f*i//gcd(f,i)
mod=10**9+7
ans=0
for i in l:
  ans+=f//i
  ans%=mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
n=int(input())
l=list(map(int,input().split()))
f=1
from fractions import gcd

for i in l:
    f=f*i//gcd(f,i)
mod=10**9+7
ans=0
for i in l:
  ans+=f//i
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
n=int(input())
l=list(map(int,input().split()))
f=l[0]
from fractions import gcd

for i in l:
    f=f*i//gcd(f,i)
mod=10**9+7
ans=0
for i in l:
  ans+=f//i
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
f=l[0]
from fractions import gcd

for i in l:
    f=f*i//gcd(f,i)
mod=10**9+7
ans=0
for i in l:
  ans+=f//i
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
f=l[0]
from fractions import gcd

for i in l:
    f=f*i//gcd(f,i)
mod=10**9+7
ans=0
for i in l:
  ans+=f//i%mod
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
f=l[0]
from fractions import gcd

for i in l:
    f=f*i//gcd(f,i)
mod=10**9+7
ans=0
for i in l:
  ans+=f//i%mod
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
f=l[0]
from fractions import gcd

for i in l:
    f=f*i//gcd(f,i)
mod=10**9+7
print(sum((f//a)%mod for a in l )%mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
f=l[0]
from fractions import gcd

for i in l:
    f=f*i//gcd(f,i)
mod=10**9+7
print(sum((f//a)%mod for a in l )%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
from fractions import gcd

mod = 10**9+7

n = ni()
a = na()
b,c = 1,0

def lcm(m,n):
    return (m*n)//gcd(m,n)

for i in a:
    b=lcm(b,i)

for i in a:
    c+=b//i

print(c%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    

    class Eratos:
        def __init__(self, num):
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
            # self.table_max 以下の素数を列挙したリスト
            self.prime_numbers = [2] if self.table_max >= 2 else []
            for i in range(3, self.table_max + 1, 2):
                if self.table[i]:
                    self.prime_numbers.append(i)
        
        def is_prime(self, num):
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            if num > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed table_max({}). got {}'.format(self.table_max, num))
            factorized_dict = defaultdict(int)    # 素因数分解の結果を記録する辞書
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in candidate_prime_numbers:
                # これ以上調査は無意味
                if num == 1:
                    break
                while num % p == 0:
                    num //= p
                    factorized_dict[p] += 1
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict


    n = ii()
    L = lmi()
    a_max = max(L)
    # O(AlglgA) で前処理
    eratos = Eratos(a_max)

    # O(n) * O(√A) で LCM を素因数分解した形で保存する
    lcm_dict = eratos.prime_factorize(L[0])
    for i in range(1, n):
        d = eratos.prime_factorize(L[i])
        for k, v in d.items():
            lcm_dict[k] = max(lcm_dict[k], v)
    
    # O(√A)
    lcm_mod = 1
    for k, v in lcm_dict.items():
        lcm_mod = (lcm_mod * pow(k, v, mod)) % mod
    
    # O(n)
    ans = 0
    for a in L:
        # a^p-2 ≡ 1/a
        inverse_element = pow(a, mod-2, mod)
        ans = (ans + lcm_mod * inverse_element) % mod
    
    print(ans)

    

if __name__ == "__main__":
    main()