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:
#!/usr/bin/env python3
import sys
from collections import Counter
import math
MOD = 1000000007  # type: int


def factorial(n):
    prime_count = Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def solve(N: int, A: "List[int]"):

    C = [factorial(a) for a in A]  # N sqrt(A)

    K = Counter()
    for c in C:                 # 素因数の数*N
        for k in c:
            K[k] = max(K[k], c[k])

    tot = 0
    for i in range(N):          # 素因数の数*N
        a = 1
        for k in K:
            a *= k**(K[k] - C[i][k])
            a %= MOD
        tot += a
        tot %= MOD
    print(tot)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

from functools import lru_cache

@lru_cache(maxsize=10**9)
def gcd(x, y):
    '''
    最大公約数の計算
    '''
    if y == 0:
        return x
    return gcd(y, x % y)

@lru_cache(maxsize=10**9)
def lcm(x, y):
    '''
    最小公倍数の計算
    '''
    return (x * y) // gcd(x, y)

l = 1
for a in A:
    if l % a == 0:
        continue
    l = lcm(l, a)

ret = 0
for a in A:
    ret += l // a

print(ret%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

from functools import lru_cache

@lru_cache(maxsize=1000)
def gcd(x, y):
    '''
    最大公約数の計算
    '''
    if y == 0:
        return x
    return gcd(y, x % y)

@lru_cache(maxsize=1000)
def lcm(x, y):
    '''
    最小公倍数の計算
    '''
    return (x * y) // gcd(x, y)

l = 1
for a in A:
    if l % a == 0:
        continue
    l = lcm(l, a)

ret = 0
for a in A:
    ret += l // a

print(ret%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))


def gcd(x, y):
    '''
    最大公約数の計算
    '''
    if y == 0:
        return x
    return gcd(y, x % y)

def lcm(x, y):
    '''
    最小公倍数の計算
    '''
    return (x * y) // gcd(x, y)

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

ret = 0
for a in A:
    ret += l // a

print(ret%MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))


def gcd(x, y):
    '''
    最大公約数の計算
    '''
    if y == 0:
        return x
    return gcd(y, x % y)

def lcm(x, y):
    '''
    最小公倍数の計算
    '''
    return (x * y) // gcd(x, y)

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

ret = 0
for a in A:
    ret += l // a
    ret %= MOD
print(ret)

Submission status: Time Limit Exceeded

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

mod = 10**9+7
INF = float('inf')

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

lcm = 1
for a in lst_a:
    lcm = a*lcm//fractions.gcd(a,lcm)
ans = 0
for a in lst_a:
	ans += lcm*pow(a,mod-2,mod)
	ans %= mod
	
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


def main():
    # N = int(input())
    # A = list(map(int, input().split()))
    N, *A = map(int, open(0).read().split())
            
    x = 1
    for a in A:
        x *= a //  fractions.gcd(x, a)
        
    b = sum(x//a%MOD for a in A)
    print(b%MOD)
    
if __name__== "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


def main():
    # N = int(input())
    # A = list(map(int, input().split()))
    N, *A = map(int, open(0).read().split())
    
    def lcm(x, y):
        return x * y // fractions.gcd(x, y)
        
    
    x = functools.reduce(lcm, A, 1)
        
    b = sum(x//a%MOD for a in A)
    print(b%MOD)
    
if __name__== "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys
 
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
 
sum_b = 0
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] / fractions.gcd(ans, a[i])
for i in range(n):
    sum_b += ans // a[i]
 
print(int(sum_b % ((10 ** 9) + 7)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#グローバル変数
pn_list = {2:0,3:0}

def next_pn():
    npn = list(pn_list.keys())[-1] + 2
    pn_flg = 0
    while pn_flg == 0:
        for i in pn_list.keys():
            if npn % i == 0:
                break
            if i ** 2 > npn:
                pn_flg = 1
                break
        if pn_flg == 1:
            break # 素数が見つかったらbreak
        else:
            npn += 2
    pn_list[npn] = 0
    return npn

def check_a(n,a):
    res = "ok"
    for i in range(n):
        if a[i] > 1:
            res = "notyet"
    return res

# 整数の入力
n = int(input())
s = input()
#n = 3
#s ="1000000 999999 999998"
a = [int(x) for x in s.split()]
aa = [int(x) for x in s.split()]

#素数作成
sqr_max_a = int((1.0 * 10**6) ** 0.5) + 1
#sqr_max_a = int(1.0 * 10**6)
pn = 0
while pn < sqr_max_a:
    pn = next_pn()

#print(len(pn_list.keys()),pn_list.keys())

# a を素因数分解する
for i in pn_list.keys():
    wareta = 1
    while wareta == 1:
        wareta = 0
        for j in range(len(a)):
            if a[j] % i == 0:
                a[j] = a[j] / i
                wareta = 1
        if wareta == 1:
            pn_list[i] += 1
    if check_a(n,a) == "ok":
        break

lcm = int(1)
for i in pn_list.keys():
    lcm = lcm * (i ** pn_list[i])
for i in a:
    lcm = lcm * i

min_bsum = int(0)
for i in aa:
    min_bsum += lcm / i

print(int(min_bsum % (10**9+7)))

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)

n=int(input())
a=[int(i) for i in input().split()]
tmp=1
for i in a:
	tmp=lcm(i,tmp)
mod=1000000007
ans=0
for i in a:
	ans=(ans+tmp//i)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools

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

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

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

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

lcm_A = lcm_list(A)

B = [None]*N
B = [lcm_A//a for a in A]
print(sum(B)%(10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools
import sys

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

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)
"""
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
"""
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
count = 0
#lcm_A = functools.reduce(lcm_base, A, 1)
B = [None]*N
for i in range(N):
    count += functools.reduce(lcm_base, A, 1)//A[i]

print(count%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
from sys import stdin

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

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

N = int(stdin.readline())
A = list(map(int, stdin.readline().split()))

lcm_A = reduce(lcm_base, A, 1)
B = [None]*N
for i in range(N):
    B[i] = lcm_A//A[i]

print(sum(B)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
import sys

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

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

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

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = reduce(lcm_base, A, 1)
B = [None]*N
for i in range(N):
    B[i] = lcm_A//A[i]

print(sum(B)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
import sys

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
"""
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
"""
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = reduce(lcm_base, A, 1)
B = [None]*N
for i in range(N):
    B[i] = lcm_A//A[i]

print(int(sum(B)%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
import sys
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(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = lcm_list(A)
B = [None]*N
for i in range(N):
    B[i] = lcm_A//A[i]

print(int(sum(B)%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
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
if N == 1:
    print(1)
else:
    data = A[0] * A[1] // gcd(A[0] , A[1])
    for i in range(2, N):
        data = data * A[i] // gcd(data, A[i])
    count= 0
    for i in range(N):
        count += data // A[i]
        count %= mod
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
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()))

lcm_A = lcm_list(A)
B = [None]*N
for i in range(N):
    B[i] = lcm_A//A[i]

print(int(sum(B)%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
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
if N == 1:
    print(1)
else:
    data = A[0] * A[1] // gcd(A[0] , A[1])
    for i in range(2, N):
        data = data * A[i] // gcd(data, A[i])
    count= 0
    for i in range(N):
        count += data // A[i]
    print(count % mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


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

    # def lcm(x, y):
    #     return x * y // fractions.gcd(x, y)
        
    
    # x = functools.reduce(lcm, A, 1)

    x=1
    for a in A:x*=a//fractions.gcd(x, a)

    
    b = sum(x//a%MOD for a in A)
    print(b%MOD)
if __name__== "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


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

    def lcm(x, y):
        return x * y // fractions.gcd(x, y)
        
    
    x = functools.reduce(lcm, A, 1)
        
    b = sum(x//a%MOD for a in A)
    print(b%MOD)
if __name__== "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


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

    def lcm(x, y):
        return x * y // fractions.gcd(x, y)
        
    
    x = functools.reduce(lcm, A, 1)
        
    b = sum(x//a for a in A)
    print(b%MOD)
if __name__== "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    # for a in A:
    #     print(a)

    x = 1
    ans = 0
    # for a in A:
    #     tmp = gcd(x, a)
    #     # ans += (i) * A[i] // tmp + A[i] * x //tmp  
    #     x = (x * a) // tmp

    def lcm(x, y):
        return x * y // fractions.gcd(x, y)
        
    
    x = functools.reduce(lcm, A, 1)
        
    b = sum(x//a for a in A)
    print(b%MOD)
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


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

    x = 1
    ans = 0
    # for a in A:
    #     tmp = gcd(x, a)
    #     # ans += (i) * A[i] // tmp + A[i] * x //tmp  
    #     x = (x * a) // tmp

    def lcm(x, y):
        return x * y // fractions.gcd(x, y)
        
    
    x = functools.reduce(lcm, A, 1)
        
    b = sum(x//a for a in A)
    print(b%MOD)
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


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

    x = 1
    ans = 0
    # for a in A:
    #     tmp = gcd(x, a)
    #     # ans += (i) * A[i] // tmp + A[i] * x //tmp  
    #     x = (x * a) // tmp

    def lcm(x, y):
        return x * y // fractions.gcd(x, y)
        
    
    x = functools.reduce(lcm, A, 1)
        
    b = 0
    for a in A:
        b += x // a
    print(b%MOD)
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


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

    x = 1
    ans = 0
    # for a in A:
    #     tmp = gcd(x, a)
    #     # ans += (i) * A[i] // tmp + A[i] * x //tmp  
    #     x = (x * a) // tmp

    def lcm(x, y):
        return x * y // fractions.gcd(x, y)
        
    
    x = functools.reduce(lcm, A, 1)
        
    b = 0
    A = np.array(A)
    # for a in A:
    #     b += x // a
    b = np.sum(x//A, axis=0)
    print(b%MOD)
main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
 
n = int(input())
A = list(map(int, input().split()))
 
l = 1
for a in set(A):
    l = (a*l) // fractions.gcd(a, l)
 
ans = 0
for a in A:
    ans += (l//a) % (10**9+7)
 
print(ans % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

X = 1

for i in range(N):
    X = lcm(X,A[i])

ANS = int(0)

for i in range(N):
    ANS += X//A[i]
    ANS %= int(1000000007)

print(int(ANS))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
L = 1
def lcm(x,y):
    return x//gcd(x,y)*y
for a in A:
    L = lcm(L,a)
ans=0
for i in range(len(A)):
  ans+=L//A[i]
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

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

lcm_a = 1
 
for i in range(N):
    lcm_a = lcm(lcm_a,A[i])
    
ans = 0
mod = int(1e9+7)
for i in range(N):
    ans += (lcm_a//A[i])%mod
    
print(ans%mod)

Submission status: Time Limit Exceeded

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

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

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


lcm_lst = {}
lst_c = []
for i in lst_A:
	c = collections.Counter(prime_factorize(i))
	lst_c.append(c)
	for key in c:
		if key in lcm_lst:
			if(lcm_lst[key]<c[key]):
				lcm_lst[key]=c[key]
		else:
			lcm_lst[key]=c[key]

ans = 0
for c in lst_c:
	a = 1
	for key in lcm_lst:
		if key in c:
			a = (a * key **(lcm_lst[key] - c[key]))%mod
		else:
			a = (a * key **(lcm_lst[key]))%mod
	ans =  (ans + a )% mod
print(ans)

Submission status: Time Limit Exceeded

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


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

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


lcm_lst = {}
lst_c = []
for i in lst_A:
	c = collections.Counter(prime_factorize(i))
	lst_c.append(c)
	for key in c:
		if key in lcm_lst:
			if(lcm_lst[key]<c[key]):
				lcm_lst[key]=c[key]
		else:
			lcm_lst[key]=c[key]

ans = 0
for c in lst_c:
	g = lcm_lst.copy()
	for key in c:
		g[key]=lcm_lst[key] - c[key]
	a = 1
	for key in g:
		a = (a * key**g[key]) % mod
	ans =  (ans + a )% mod
print(ans)

Submission status: Time Limit Exceeded

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


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

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


lcm_lst = {}
lst_c = []
for i in lst_A:
	c = collections.Counter(prime_factorize(i))
	lst_c.append(c)
	for key in c:
		if key in lcm_lst:
			if(lcm_lst[key]<c[key]):
				lcm_lst[key]=c[key]
		else:
			lcm_lst[key]=c[key]

ans = 0
for c in lst_c:
	g = lcm_lst.copy()
	for key in c:
		g[key]=lcm_lst[key] - c[key]
	a = 1
	for key in g:
		a = (a * key**g[key]) % mod
	ans =  (ans + a)% mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import gcd

MOD = 10**9+7


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

    x = 1
    ans = 0
    for a in A:
        tmp = gcd(x, a)
        # ans += (i) * A[i] // tmp + A[i] * x //tmp  
        x = (x * a) // tmp
    
    b = 0
    A = np.array(A)
    # for a in A:
    #     b += x // a
    b = np.sum(x//A, axis=0)
    print(b%MOD)
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import gcd

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


def main():
    x = 1
    ans = 0
    for a in A:
        tmp = gcd(x, a)
        # ans += (i) * A[i] // tmp + A[i] * x //tmp  
        x = (x * a) // tmp
    
    b = 0
    for a in A:
        b += x // a
        
    print(b%MOD)
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import gcd

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

x = 1
ans = 0
for a in A:
    tmp = gcd(x, a)
    # ans += (i) * A[i] // tmp + A[i] * x //tmp  
    x = (x * a) // tmp
    
b = 0
for a in A:
    b += x // a
    
print(b%MOD)

Submission status: Time Limit Exceeded

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

from collections import defaultdict

MOD = 10**9 + 7

primes = defaultdict(int)

for a in A:
    p = 2
    while p * p <= a:
        if a % p == 0:
            cnt = 0
            while a % p == 0:
                cnt += 1
                a //= p
            primes[p] = max(primes[p], cnt)
        p += 1
    if a != 1:
        if a not in primes:
            primes[a] = 1

lcm = 1
for p in primes:
    lcm = lcm * pow(p, primes[p], MOD) % MOD

ans = 0
for a in A:
    ans += lcm * pow(a, MOD-2, MOD) % MOD
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import fractions
    import sys
    input = sys.stdin.readline
    N = int(input())
    a = list(map(int,input().split()))
    MOD = 10**9+7
    g1 = 1
    for t in a[:N//2]:
        g1 = divmod(g1*t,fractions.gcd(g1,t))[0]

    g2 = 1
    for t in a[N//2:]:
        g2 = divmod(g2*t,fractions.gcd(g2,t))[0]
    res = 0
    g = fractions.gcd(g1,g2)

    r1 = (g2//g)%MOD
    for t in a[:N//2]:
        res += divmod(g1,t)[0]
    res = res*r1%MOD

    res2 = 0
    r2 = (g1//g)%MOD
    for t in a[N//2:]:
        res2 += divmod(g2,t)[0]
    res2 = res2*r2%MOD
    print((res+res2)%MOD)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import decimal
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

class Library():
    @staticmethod
    def Swap(a,b):
        return [b,a]

    @staticmethod
    def myRound(a,dig=0): # 四捨五入
        p = 10 ** dig
        return (a * p * 2 + 1) // 2 / p

    @staticmethod
    def Roundup(a,dig=0): # 切り上げ
        if a < 0:
            return int(a)
        else:
            return int(a + 0.9)

    @staticmethod
    def Gcd(a,b): #最大公約数
        if (a<b):
            a,b = Library.Swap(a,b)
        if (b==0):
            return a
        else:
            return Library.Gcd(b,a%b)

    @staticmethod
    def Lcm(a,b): #最小公倍数
        return a//Library.Gcd(a,b)*b

    @staticmethod
    def Divisors(a): # 約数列挙
        divisors = []
        for i in range(1,int(a**0.5)+1):
            if a%i==0:
                divisors.append(i)
                if i!=a//i:
                    divisors.append(a//i)
        divisors.sort()
        return divisors

class Prime():
    # コンストラクタ
    # エラストテネスの篩
    def __init__(self,num):
        self.num = num
        self.sieve = [0] * (self.num + 1)
        self.sieve[0] = -1
        self.sieve[1] = -1
        for i in range(2,self.num + 1):
            if self.sieve[i] == 0:
                self.sieve[i] = i
                for j in range(i * i,self.num + 1,i):
                    self.sieve[j] = i
    
    # 素数判定
    def isPrime(self,num = None):
        if num is None:
            num = self.num
        if self.sieve[num] == num:
            return True
        else:
            return False
    
    # 素数列挙
    def PrimeNum(self,num = None):
        if num is None:
            num = self.num
        prime = []
        for i in range(2,num):
            if self.sieve[i] == i:
                prime.append(i)
        return prime
    
    # 素因数分解
    def PrimeFact(self,num = None):
        if num is None:
            num = self.num
        fact = []
        while self.sieve[num] != num:
            fact.append(self.sieve[num])
            num //= self.sieve[num]
        fact.append(num)
        return fact

def main():
    n = int(input())
    a = list(map(int,input().split()))
    p = Prime(1000000)
    lcm = {}
    for i in range(n):
        _p = p.PrimeFact(a[i])
        mp = {}
        for x in _p:
            mp[x] = mp.get(x,0) + 1
        for x in mp:
            lcm[x] = max(lcm.get(x,0),mp.get(x))
    x = 1
    for l in lcm:
        x *= l ** lcm[l]
    ans = 0
    for i in range(n):
        ans += x // a[i]
        ans %= mod
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import decimal
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

class Library():
    @staticmethod
    def Swap(a,b):
        return [b,a]

    @staticmethod
    def myRound(a,dig=0): # 四捨五入
        p = 10 ** dig
        return (a * p * 2 + 1) // 2 / p

    @staticmethod
    def Roundup(a,dig=0): # 切り上げ
        if a < 0:
            return int(a)
        else:
            return int(a + 0.9)

    @staticmethod
    def Gcd(a,b): #最大公約数
        if (a<b):
            a,b = Library.Swap(a,b)
        if (b==0):
            return a
        else:
            return Library.Gcd(b,a%b)

    @staticmethod
    def Lcm(a,b): #最小公倍数
        return a//Library.Gcd(a,b)*b

    @staticmethod
    def Divisors(a): # 約数列挙
        divisors = []
        for i in range(1,int(a**0.5)+1):
            if a%i==0:
                divisors.append(i)
                if i!=a//i:
                    divisors.append(a//i)
        divisors.sort()
        return divisors

class Prime():
    # コンストラクタ
    # エラストテネスの篩
    def __init__(self,num):
        self.num = num
        self.sieve = [0] * (self.num + 1)
        self.sieve[0] = -1
        self.sieve[1] = -1
        for i in range(2,self.num + 1):
            if self.sieve[i] == 0:
                self.sieve[i] = i
                for j in range(i * i,self.num + 1,i):
                    self.sieve[j] = i
    
    # 素数判定
    def isPrime(self,num = None):
        if num is None:
            num = self.num
        if self.sieve[num] == num:
            return True
        else:
            return False
    
    # 素数列挙
    def PrimeNum(self,num = None):
        if num is None:
            num = self.num
        prime = []
        for i in range(2,num):
            if self.sieve[i] == i:
                prime.append(i)
        return prime
    
    # 素因数分解
    def PrimeFact(self,num = None):
        if num is None:
            num = self.num
        fact = []
        while self.sieve[num] != num:
            fact.append(self.sieve[num])
            num //= self.sieve[num]
        fact.append(num)
        return fact

def main():
    n = int(input())
    a = list(map(int,input().split()))
    p = Prime(max(a))
    lcm = {}
    for i in range(n):
        _p = p.PrimeFact(a[i])
        mp = {}
        for x in _p:
            mp[x] = mp.get(x,0) + 1
        for x in mp:
            lcm[x] = max(lcm.get(x,0),mp.get(x))
    x = 1
    for l in lcm:
        x *= l ** lcm[l]
    ans = 0
    for i in range(n):
        ans += x // a[i]
        ans %= mod
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

def dp():
    n,=list(map(int,input().split()))
    l=list(map(int,input().split()))
    lcm=1
    for i in l:
        lcm=(lcm*i)//gcd(lcm,i)
    ans=0
    mod=1000000007
    for i in l:
        ans=(ans+(lcm//i))%mod
    print(ans)

if __name__ == "__main__":
    dp()

Submission status: Time Limit Exceeded

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

def dp():
    n=int(input())
    l=list(map(int,input().split()))
    lcm=1
    for i in l:
        lcm=(lcm*i)//gcd(lcm,i)
    ans=0
    mod=1000000007
    for i in l:
        ans=(ans+(lcm//i))%mod
    print(ans)

if __name__ == "__main__":
    dp()

Submission status: Time Limit Exceeded

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

n=int(input())
l=list(map(int,input().split()))
lcm=1
for i in l:
    lcm=(lcm*i)//gcd(lcm,i)
ans=0
mod=1000000007
for i in l:
    ans=(ans+(lcm//i))%mod
print(ans)

Submission status: Time Limit Exceeded

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

    n = int(input())
    num_list = tuple(map(int, input().split()))

    l = 1
    for num in num_list:
        l *= num // gcd(l, num)

    answer = 0

    for num in num_list:
        answer += l // num
        answer %= 10 ** 9 + 7

    print(int(answer))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import decimal
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

class Library():
    @staticmethod
    def Swap(a,b):
        return [b,a]

    @staticmethod
    def myRound(a,dig=0): # 四捨五入
        p = 10 ** dig
        return (a * p * 2 + 1) // 2 / p

    @staticmethod
    def Roundup(a,dig=0): # 切り上げ
        if a < 0:
            return int(a)
        else:
            return int(a + 0.9)

    @staticmethod
    def Gcd(a,b): #最大公約数
        if (a<b):
            a,b = Library.Swap(a,b)
        if (b==0):
            return a
        else:
            return Library.Gcd(b,a%b)

    @staticmethod
    def Lcm(a,b): #最小公倍数
        return a//Library.Gcd(a,b)*b

    @staticmethod
    def Divisors(a): # 約数列挙
        divisors = []
        for i in range(1,int(a**0.5)+1):
            if a%i==0:
                divisors.append(i)
                if i!=a//i:
                    divisors.append(a//i)
        divisors.sort()
        return divisors

class Prime():
    # コンストラクタ
    # エラストテネスの篩
    def __init__(self,num):
        self.num = num
        self.sieve = [0] * (self.num + 1)
        self.sieve[0] = -1
        self.sieve[1] = -1
        for i in range(2,self.num + 1):
            if self.sieve[i] == 0:
                self.sieve[i] = i
                for j in range(i * i,self.num + 1,i):
                    self.sieve[j] = i
    
    # 素数判定
    def isPrime(self,num = None):
        if num is None:
            num = self.num
        if self.sieve[num] == num:
            return True
        else:
            return False
    
    # 素数列挙
    def PrimeNum(self,num = None):
        if num is None:
            num = self.num
        prime = []
        for i in range(2,num):
            if self.sieve[i] == i:
                prime.append(i)
        return prime
    
    # 素因数分解
    def PrimeFact(self,num = None):
        if num is None:
            num = self.num
        fact = []
        while self.sieve[num] != num:
            fact.append(self.sieve[num])
            num //= self.sieve[num]
        fact.append(num)
        return fact

def main():
    n = int(input())
    a = list(map(int,input().split()))
    prime = []
    p = Prime(int(1e6))
    for i in range(n):
        _p = p.PrimeFact(a[i])
        mp = {}
        for x in _p:
            mp[x] = mp.get(x,0) + 1
        prime.append(mp)
    lcm = {}
    for x in prime:
        for y in x.keys():
            lcm[y] = max(lcm.get(y,0),x.get(y))
    x = 1
    for l in lcm:
        x *= l ** lcm[l]
    ans = 0
    for i in range(n):
        ans += x // a[i]
        ans %= mod
    print(ans)
    return

if __name__=='__main__':
    main()