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:
def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007

MOD = 10**9+7
N = int(input())
A = [int(i) for i in input().split()]

k = 1
for i in range(N):
	k = (k * A[i])//kouyaku(k, A[i])
ans = 0
for i in range(N):
	ans += k//A[i]
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

"""
普通に最小公倍数を計算すると桁数が莫大になって
桁溢れor多倍長整数を使っても計算が一気に遅くなるのがこの問題のミソ

桁数の大きい数は素因数分解の形で保持すると高速にmod計算が可能なので、これを用いる。
まずは1000以下の素数テーブルを用意。
"""
prime = [i for i in range(2, 10**6)]
for p in prime:
    prime = [x for x in prime if (x == p or x % p != 0)]

def div(a, n):
    """
    自然数aがnで何回割れるかを返す
    """
    num = 0
    while a % n == 0:
        num += 1
        a = a // n
    return num

"""
素数pごとに、各A[i]がpで何回割れるかを求め、iでループを回した中での最大値をe_pとすると
A[0],...A[N-1]の最小公倍数はL = ¥Prod_p p^{e_p}になる。
これならmodで桁数削減が可能。
"""
L = 1
for p in prime:
    e = 0
    for i in range(N):
        e = max(e, div(A[i], p))
    L *= pow(p, e, mod)

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

lcm_num = A[0]
for i in range(1, N):
    g = gcd(lcm_num, A[i])
    lcm_num = lcm_num * A[i] // g
#print(lcm_num)

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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


lcm_num = A[0]
for i in range(1, N):
    lcm_num = lcm(lcm_num, A[i])
#print(lcm_num)

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
def lcm(a, b): # 最小公倍数
    def gcd(a, b): # 最大公約数
        a = abs(a)
        b = abs(b)
        while b:
            a, b = b, a % b
        return a # int
    return a * b // gcd(a, b) # int

L = reduce(lcm,A)
ans = 0
for i in range(N):
    ans += L//A[i]
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
def lcm(x, y):
  return (x * y) // fractions.gcd(x, y)
  
def main():
  mod = 10**9 +7
  n = int(input())
  ls = list(map(int,input().split()))
  
  t = ls[0]
  for a in ls:
    t = lcm(t,a)
  
  ans = 0
  for a in ls:
    ans = (ans + t//a) % mod 
  print(ans)
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
N = int(input())
A = list(map(int,input().split()))
def lcm(a, b): # 最小公倍数
    def gcd(a, b): # 最大公約数
        a = abs(a)
        b = abs(b)
        while b:
            a, b = b, a % b
        return a # int
    return a * b // gcd(a, b) # int

L = reduce(lcm,A)
ans = 0
for i in range(N):
    ans += L//A[i]
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
N = int(input())
A = list(map(int,input().split()))
def lcm(a, b): # 最小公倍数
    def gcd(a, b): # 最大公約数
        a = abs(a)
        b = abs(b)
        while b:
            a, b = b, a % b
        return a # int
    return a * b // gcd(a, b) # int

L = reduce(lcm,A)
ans = 0
for i in range(N):
    ans += L//A[i]
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
def lcm(x, y):
  return (x * y) // fractions.gcd(x, y)

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

MODp = 1000000007
K = 1
for i in range(N):
  K = lcm(K,l[i])

Ans = 0
for i in range(N):
  Ans += ((K // l[i])%MODp)

Ans = Ans % MODp
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7
 
N = int(input())
A = list(map(int,input().split()))
fact = [1]*(10**7+10)
rfact = [1]*(10**7+10)
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
value = lcm_list(A)
ans = 0
for i in range(N):
    ans += value*pow(A[i], mod-2, mod)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
ma = max(a)

p = [0]*10**6
for i in a:
    for j in range(2,ma+1):
        count = 0
        while i%j == 0:
            count += 1
            i /= j
        if count > p[j-1]:
            p[j-1] = count
            
k=1
for i in range(10**6):
    if p[i] != 0:
        k *= (i+1)**p[i]

ans = 0
for i in a:
    ans += k/i
    
print(int(ans)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1, n): l = l // fractions.gcd(l, a[i]) * a[i]
print(sum([l // a[i] for i in range(n)]) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1, n): l = l // fractions.gcd(l, a[i]) * a[i]
print(sum([l // a[i] for i in range(n)]) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1, n): l = l * a[i] // fractions.gcd(l, a[i])
print(sum([l // a[i] % 1000000007 for i in range(n)]) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1, n): l = l * a[i] // fractions.gcd(l, a[i])
print(sum([l // a[i] for i in range(n)]) % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import fractions

def main():
    mod = 10**9+7
    N = int(input())
    A = list(map(int,input().split()))
    lcm = 1
    for Ai in A:
        lcm = lcm*Ai//fractions.gcd(lcm,Ai)
    
    ans = 0
    for Ai in A:
        ans += lcm*pow(Ai,mod-2,mod)%mod
        ans %= mod
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def factorization(n):
    counter = Counter()
    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
            counter[i] = cnt

    if temp!=1:
        counter[temp] = 1

    if len(counter)==0:
        counter[n] = 1

    return counter

def main():
    mod = 10**9+7
    N = int(input())
    A = list(map(int,input().split()))
    
    A_primefact = [0]*N
    union = Counter()
    for i in range(N):
        A_primefact[i] = factorization(A[i])
        union = union | A_primefact[i]
    ans = 0
    for i in range(N):
        tmp = 1
        for prime in (union-A_primefact[i]).most_common():
            tmp *= prime[0]**prime[1]
            tmp %= mod
        ans += tmp
        ans %= mod
    ans %= mod
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def factorization(n):
    counter = Counter()
    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
            counter[i] = cnt

    if temp!=1:
        counter[temp] = 1

    if len(counter)==0:
        counter[n] = 1

    return counter

def main():
    mod = 10**9+7
    N = int(input())
    A = list(map(int,input().split()))
    
    A_primefact = [0]*N
    union = Counter()
    for i in range(N):
        A_primefact[i] = factorization(A[i])
        union = union | A_primefact[i]
    
    ans = 0
    for i in range(N):
        tmp = 1
        for prime in (union-A_primefact[i]).most_common():
            tmp *= prime[0]**prime[1]
            tmp %= mod
        ans += tmp
    ans %= mod
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def factorization(n):
    counter = Counter()
    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
            counter[i] = cnt

    if temp!=1:
        counter[temp] = 1

    if len(counter)==0:
        counter[n] = 1

    return counter

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

A_primefact = [0]*N
union = Counter()
for i in range(N):
    A_primefact[i] = factorization(A[i])
    union = union | A_primefact[i]

ans = 0
for i in range(N):
    tmp = 1
    for prime in (union-A_primefact[i]).most_common():
        tmp *= prime[0]**prime[1]
        tmp %= mod
    ans += tmp
ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 10**9 + 7

n = int(readline())
a = list(map(int, readline().split()))

ab = 1
for i in range(n):
    ab = ab * a[i] // gcd(ab, a[i])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 10**9 + 7

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

ab = 1
for i in range(n):
    ab = ab * a[i] // gcd(ab, a[i])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 10**9 + 7

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

MOD = 10**9+7
lcm_val = lcm_list(A)
diff = [lcm_val // a for a in A]
print(sum(diff)%MOD)

Submission status: Time Limit Exceeded

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

from functools import reduce
import fractions
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
num=lcm_list(a)
ans=0
for tmp in a:
    ans+=num//tmp
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))

from functools import reduce
import fractions
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
num=lcm_list(a)
ans=0
for tmp in a:
    ans+=num//tmp
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
def lcm_base(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm(*numbers):
    return reduce(lcm_base,numbers,1)
num=lcm(*a)
m=1
for i in range(n):
  m*=a[i]
l=0
for i in range(n):
  l+=num//a[i]
  l=l%((10**9)+7)
print(l)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

sys.setrecursionlimit(1000000)
input = lambda: sys.stdin.readline().rstrip()

def factorize(x):
    count = {}
    i = 2
    while i * i <= x:
        while x % i == 0:
            x //= i
            count[i] = count.get(i, 0) + 1
        i += 1
    if x > 1:
        count[x] = count.get(x, 0) + 1
    return count


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

A = list(map(factorize, A))

lcm = {}
for i in A:
    for factor, count in i.items():
        lcm[factor] = max(lcm.get(factor, 0), count)

MOD = 1000000007
ans = 0
for i in A:
    B = 1
    for factor, count in lcm.items():
        B *= pow(factor, count - i.get(factor, 0), MOD)
        B % MOD
    ans = (ans + B) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    while (b):
        r = a % b
        a = b
        b = r
    return a
N = int(input())
a = []
gong = 1
a = list(map(int, input().split()))

for i in range(N):
    x = a[i]
    gong = gong * x // gcd(gong, x)
sum = 0
for i in range(N):
    sum = gong // a[i] + sum
Mod = 1000000007
sum = sum % Mod
print((sum))

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    if a % b ==0 :
        return b
    else:
        return gcd(b,int(a%b))

N = int(input())
a = []
gong = 1
a = list(map(int, input().split()))

for i in range(N):
    x = a[i]
    gong = gong * x // gcd(gong, x)
sum = 0
for i in range(N):
    sum = gong // a[i] + sum
Mod = 1000000007
sum = sum % Mod
print((sum))

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B = a * B // g(B, a)
    
    print(sum(B // a for a in A) % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def l(a, b):
    return a * b // g(a, b)


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B = l(a, B)
    
    print(sum(B // a for a in A) % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def l(a, b):
    return a * b // g(a, b)


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B = l(a, B)
    
    print(sum(B // a for a in A) % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def Prim(N):
    P = []
    M = int(N ** 0.5) + 1
    F = [False, False] + [True] * M
    for n in range(2, M):
        if not F[n]:
            continue
        P.append(n)
        for i in range(n, len(F), n):
            F[i] = False
    
    return P
 

def ps(a, P, K):
    d = {}
    for p in P:
        c = 0
        while a % p == 0:
            c += 1
            a //= p
        d[p] = c

        if a == 1:
            break
    
    if a != 1:
        d[a] = 1
        K.add(a)
    return d


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
    P = Prim(max(A))
    K = set()

    DA = [ps(a, P, K) for a in A]
    P.extend(list(K))

    D = {}
    res = 0
    for d in DA:
        b = 1
        for i in P:
            v = d.setdefault(i, 0)
            r = D.setdefault(i, 0)
            if v > r:
                D[i] = v
                res = res * pow(i, v - r, mod) % mod
            else:
                b = b * pow(i, r - v, mod) % mod
        
        res = (res + b) % mod

    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def Prim(N):
    P = []
    M = int(N ** 0.5) + 1
    F = [False, False] + [True] * M
    for n in range(2, M):
        if not F[n]:
            continue
        P.append(n)
        for i in range(n, len(F), n):
            F[i] = False
    
    return P
 

def ps(a, P, K):
    d = {}
    for p in P:
        c = 0
        while a % p == 0:
            c += 1
            a //= p
        d[p] = c

        if a == 1:
            break
    
    if a != 1:
        d[a] = 1
        K.add(a)
    return d


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
    P = Prim(max(A))
    K = set()

    DA = [ps(a, P, K) for a in A]
    P.extend(list(K))

    D = {}
    res = 0
    for d in DA:
        b = 1
        for i in P:
            v = d.setdefault(i, 0)
            r = D.setdefault(i, 0)
            if v > r:
                D[i] = v
                res = res * (i ** (v - r)) % mod
            else:
                b = b * (i ** (r - v)) % mod
        
        res = (res + b) % mod

    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def Prim(N):
    P = []
    M = int(N ** 0.5) + 10
    F = [False, False] + [True] * M
    for n in range(2, M):
        if not F[n]:
            continue
        P.append(n)
        for i in range(n, len(F), n):
            F[i] = False
    
    return P
 

def ps(a, P):
    d = {}
    for p in P:
        while a % p == 0:
            d[p] = d.setdefault(p, 0) + 1
            a //= p
        
        if a == 1:
            break
    
    if a != 1:
        d[a] = d.setdefault(a, 0) + 1
    return d


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
    P = Prim(max(A))
    DA = [ps(a, P) for a in A]
    keys = set()
    for d in DA:
        keys.update(d.keys())

    D = {}
    res = 0
    for d in DA:
        b = 1
        for i in keys:
            v = d.setdefault(i, 0)
            r = D.setdefault(i, 0)
            if v > r:
                D[i] = v
                res = res * (i ** (v - r)) % mod
            else:
                b = b * (i ** (r - v)) % mod
        
        res = (res + b) % mod

    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def Prim(N):
    P = []
    M = int(N ** 0.5) + 10
    F = [False, False] + [True] * M
    for n in range(2, M):
        if not F[n]:
            continue
        P.append(n)
        for i in range(n, len(F), n):
            F[i] = False
    
    return P
 

def ps(a, P):
    d = {}
    for p in P:
        while a % p == 0:
            d[p] = d.setdefault(p, 0) + 1
            a //= p
        
        if a == 1:
            break
    
    if a != 1:
        d[a] = d.setdefault(a, 0) + 1
    return d


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
    P = Prim(max(A))
    DA = [ps(a, P) for a in A]
    
    D = {}
    for d in DA:
        for i, v in d.items():
            D[i] = max(D.setdefault(i, 0), v)

    res = 0
    for d in DA:
        b = 1
        for i, v in D.items():
            b = b * (i ** max(0, v - d.setdefault(i, 0))) % mod

        res = (res + b) % mod

    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def ps(a):
    d = {}
    for n in range(2, a + 1):
        while a % n == 0:
            d[n] = d.setdefault(n, 0) + 1
            a //= n
        
        if a == 1:
            break
    return d


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    DA = [ps(a) for a in A]
    
    D = {}
    for d in DA:
        for i, v in d.items():
            D[i] = max(D.setdefault(i, 0), v)

    res = 0
    for d in DA:
        b = 1
        for i, v in D.items():
            b = b * (i ** max(0, v - d.setdefault(i, 0))) % mod

        res = (res + b) % mod

    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def Prim(N):
    P = []
    F = [False, False] + [True] * (N + 1)
    for n in range(2, N + 1):
        if not F[n]:
            continue
        P.append(n)
        for i in range(n, len(F), n):
            F[i] = False
    
    return P


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
    P = Prim(max(A))

    l = 1
    res = 0
    for a in A:
        if l % a == 0:
            res = (res + l // a) % mod
            continue
        
        if a in P:
            l2 = l * a
        else:
            l2 = gm(a, l)
        res = (res * l2 // l) % mod
        res = (res + l2 // a) % mod
        l = l2
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a // lm(a, b) * b


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    l = 1
    res = 0
    for a in A:
        if l % a == 0:
            res = (res + l // a) % mod
        else:
            l2 = gm(a, l)
            res = (res * l2 // l) % mod
            res = (res + l2 // a) % mod
            l = l2
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
    A.sort()

    l = 1
    res = 0
    for a in A:
        if l % a == 0:
            res = (res + l // a) % mod
        else:
            l2 = gm(a, l)
            res = (res * l2 // l) % mod
            res = (res + l2 // a) % mod
            l = l2
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
    A.sort()

    l = 1
    res = 0
    for a in A:
        l2 = gm(a, l)
        res = (res * l2 // l) % mod
        res = (res + l2 // a) % mod
        l = l2
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    l = 1
    res = 0
    for i, a in enumerate(A):
        l2 = gm(l, a)
        res = (res * l2 // l) % mod
        res = (res + l2 // a) % mod
        l = l2
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def lm(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def gm(a, b):
    return a * b // lm(a, b)


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    l = 1
    for a in A:
        l = gm(l, a)

    res = 0
    for a in A:
        res = (res + l // a) % mod
    print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd
    import sys
    input=sys.stdin.readline
    N=int(input())
    A=list(map(int,input().split()))
    lcm=A[0]
    for a in A:
        lcm=lcm*a//(gcd(lcm,a))

    ans=0
    for a in A:
        ans=(ans+(lcm//a)%(10**9+7))%(10**9+7)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def main():
    N=int(input())
    A=list(map(int,input().split()))
    lcm=A[0]
    for i in range(1,N):
        lcm=lcm*A[i]//(gcd(lcm,A[i]))

    ans=0
    for i in range(0,N):
        ans=(ans+(lcm//A[i])%(10**9+7))%(10**9+7)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
lcm=A[0]
for i in range(1,N):
    lcm=lcm*A[i]//(gcd(lcm,A[i]))

ans=sum((lcm//A[i])%(10**9+7) for i in range(0,N))%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# from math import gcd
from fractions import gcd
from functools import reduce
 
n = int(input())
a = [int(x) for x in input().split()]
 
def lcm_base(x, y):
    return (x * y) // gcd(x, y)
 
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
lcm = lcm_list(a)
ans = 0
for i in range(len(a)):
    ans += lcm // a[i] % 1000000007
print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
def gcd(n,m):#n,mは正の整数、最大公約数　許容は？
    if n==0:
        return m
    elif m==0:
        return n
    elif n>m:
        n=n%m
        return gcd(n,m)
    else:
        m=m%n
        return gcd(n,m)

N=int(input())
A=list(map(int,input().split()))
lcm=A[0]
for i in range(1,N):
    lcm=lcm*A[i]//(gcd(lcm,A[i]))

ans=sum((lcm//A[i])%(10**9+7) for i in range(0,N))%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# from math import gcd
from fractions import gcd
from functools import reduce
 
n = int(input())
a = [int(x) for x in input().split()]
 
def lcm_list(numbers):
    return reduce(lambda x, y: (x * y) // gcd(x, y), numbers, 1)
 
lcm = lcm_list(a)
aa = []
for i in range(len(a)):
    aa.append(lcm // a[i])
ans = sum(aa) % 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# from math import gcd
from fractions import gcd
from functools import reduce
 
n = int(input())
a = [int(x) for x in input().split()]
 
def lcm_base(x, y):
    return (x * y) // gcd(x, y)
 
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
lcm = lcm_list(a)
aa = []
for i in range(len(a)):
    aa.append(lcm // a[i])
ans = sum(aa) % 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
import math
import fractions
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def get_lcm(num):
    return reduce(lambda x,y:(x * y) // fractions.gcd(x, y), num, 1)

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

    lcm = get_lcm(A)
    _, ans = divmod(sum(list(map(lambda a: lcm // a ,A))), (10**9+7))

    print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def main():
    from fractions import gcd

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

    for ai in a:
        lcm = lcm * ai // gcd(lcm, ai)

    for ai in a:
        ans += lcm // ai

    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def main():
    from fractions import gcd

    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    lcm = a[0]
    ans = 0

    for ai in a[1:]:
        lcm = lcm * ai // gcd(lcm, ai)

    for ai in a:
        ans += lcm // ai

    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def main():
    from fractions import gcd

    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    lcm = a[0]
    ans = 0

    for ai in a[1:]:
        lcm = lcm * ai // gcd(lcm, ai)

    for ai in a:
        ans += lcm // ai
        ans %= mod

    print(ans % mod)


if __name__ == '__main__':
    main()