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
import math
from collections import defaultdict          # subclass of dict. defaultdict(facroty)



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 = list(filter(lambda x: x <= math.sqrt(num), self.prime_numbers))
            candidate_prime_numbers.reverse()
            while num > 1 and candidate_prime_numbers:
                p = candidate_prime_numbers[-1]
                if num % p == 0:
                    num //= p
                    factorized_dict[p] += 1
                else:
                    candidate_prime_numbers.pop()
            if num != 1:
                # num は素数
                factorized_dict[num] = 1
            return factorized_dict

        
    n = ii()
    L = lmi()
    a_max = max(L)
    # O(nlglgn) で前処理
    eratos = Eratos(a_max)
    # O(√n) で 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)
    
    lcm_mod = 1
    for k, v in lcm_dict.items():
        lcm_mod = (lcm_mod * pow(k, v, mod)) % mod

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

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 = list(filter(lambda x: x <= num, self.prime_numbers))
            candidate_prime_numbers.reverse()
            while num > 1 and candidate_prime_numbers:
                p = candidate_prime_numbers[-1]
                if num % p == 0:
                    num //= p
                    factorized_dict[p] += 1
                else:
                    candidate_prime_numbers.pop()
            return factorized_dict

        
    n = ii()
    L = lmi()
    a_max = max(L)
    # O(nlglgn) で前処理
    eratos = Eratos(a_max)
    # O(√n) で 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)
    
    lcm_mod = 1
    for k, v in lcm_dict.items():
        lcm_mod = (lcm_mod * pow(k, v, mod)) % mod

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

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())
    
    def lcm(a, b): return a * b // gcd(a, b)
    
    n = ii()
    L = lmi()
    total_lcm = L[0]
    for i in range(1, n):
        total_lcm = lcm(total_lcm, L[i]) #% mod
    ans = 0
    for elm in L:
        # inverse_element = pow(elm, mod-2, mod)
        # ans = (ans + total_lcm * inverse_element) % mod
        ans = (ans + total_lcm // elm) % mod
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

N = int(input())
A = list(map(int,input().split()))
MOD = 10** 9 + 7
lcm = 1
for a in A:
    lcm = a // fractions.gcd(a,lcm) * lcm

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

Submission status: Time Limit Exceeded

Solution code:
import fractions

N = int(input())
A = list(map(int,input().split()))
MOD = 10** 9 + 7
lcm = 1
for a in A:
    lcm = a // fractions.gcd(a,lcm) * lcm

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

print(sum(lcm//a for a in A)%MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import collections 
from functools import reduce
MOD = 10**9 + 7

N = int(input())
A = [int(i) for i in input().split()]

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

dic = collections.defaultdict(int)
for a in A:
    c2 = collections.Counter(prime_factorize(a))
    for k, v in list(c2.items()):
        dic[k] = max(dic[k],v)
        
ans = 0
for a in A:
    c2 = collections.Counter(prime_factorize(a))
    B =1
    for k,v in list(dic.items()):
        B *= k ** (v-c2[k]) 
        B %= MOD
    ans += B
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
import sys
read=sys.stdin.readline
from fractions import gcd
from collections import deque
def lcm(a,b):
    return(a//gcd(a,b)*b)
def main():
    N=int(input())
    A=list(map(int,read().split()))
    d=deque(A)
    while(len(d)>1):
        a,b=d.popleft(),d.popleft()
        d.append(lcm(a,b))
    g=d[0]
    res=0
    for i in range(N):
        res=(res+g//A[i])%MOD
    print(res)
    
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
from fractions import gcd
def lcm(a,b):
    return(a//gcd(a,b)*b)
N=int(input())
A=list(map(int,input().split()))
g=1
for i in range(N):
    g=lcm(g,A[i])
res=0
for i in range(N):
    res=(res+g//A[i])%MOD
print(res)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
d = {}
mod = 1000000007

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

q = []
for i in range(n):
    p = collections.Counter(prime_factorize(a[i]))
    q.append(p)
    for x,y in p.items():
            d[x] = max(d.get(x,0),y)            

ans = 0
for i in range(n):
    b = 1
    g = q[i]
    for x,y in d.items():        
        h = g.get(x,0)
        for j in range(y-h):
            b *= x
            b %= mod
    ans += b
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
d = {}
mod = 1000000007

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

q = []
for i in range(n):
    p = collections.Counter(prime_factorize(a[i]))
    q.append(p)
    for x,y in p.items():
            d[x] = max(d.get(x,0),y)            

ans = 0
for i in range(n):
    b = 1
    g = q[i]
    for x,y in d.items():        
        h = g.get(x,0)
        for j in range(y-h):
            b *= x
            b %= mod
    ans += b
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
d = {}
mod = 1000000007

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

q = []
for i in range(n):
    p = collections.Counter(prime_factorize(a[i]))
    #print(p)
    q.append(p)
    for x,y in p.items():
            d[x] = max(d.get(x,0),y)  
#print(d)

ma = 1
for x,y in d.items(): 
    ma *= (x**y)
#print(ma)
            
ans = 0
for i in range(n):
    ans += ma//a[i]
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
d = {}
mod = 1000000007

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

q = []
for i in range(n):
    p = collections.Counter(prime_factorize(a[i]))
    q.append(p)
    for x,y in p.items():
            d[x] = max(d.get(x,0),y)            

ans = 0
for i in range(n):
    b = 1
    g = q[i]
    for x,y in d.items():        
        h = g.get(x,0)
        b *= (x**(y-h))
        b %= mod
    ans += b
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
d = {}
mod = 1000000007

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

q = []
for i in range(n):
    p = collections.Counter(prime_factorize(a[i]))
    q.append(p)
    for x,y in p.items():
        if not x in d:
            d[x] = y
        else:
            d[x] = max(d.get(x),y)
            
#print(d)
#print(q)

ans = 0
for i in range(n):
    b = 1
    g = q[i]
    for x in d.keys():
        f = d.get(x)
        
        h = g.get(x,0)
        b *= (x**(f-h))
        b %= mod
    ans += b
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
mod = 10**9+7
#最小公倍数を割った商の和を求める
import fractions
from functools import lru_cache
@lru_cache(maxsize=20000000)
def gcd(x,y):
    if x >= y:
        b = x % y
        return gcd(b,y)
    return fractions.gcd(x,y)
lcm = a[0]
for i in range(1,N):
    lcm = lcm * a[i] // gcd(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:
N = int(input())
a = [int(x) for x in input().split()]
mod = 10**9+7
#最小公倍数を割った商の和を求める
import fractions
lcm = a[0]
for i in range(1,N):
    lcm = lcm * a[i] // fractions.gcd(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:
import sys
import fractions
input = sys.stdin.readline


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

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

ans = 0
for a in A:
    ans += lcm // a
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
now = A[0]
ans = 0
for i in range(1,N):
    now = now//gcd(now, A[i])*A[i]
for i in range(N):
    ans += now//A[i]
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def make_divisors2(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    prime_list = prime(max(a))
    prime_count = dict()
    for value in prime_list:
        prime_count[value] = 0
        key = value
        for i in range(n):
            while a[i]%key == 0:
                key *= value
                prime_count[value] += 1
    
    ans = 0
    inf = pow(10, 9)+7
    
    for value in a:
        sub = 1
        for p in prime_list:
            k = prime_count[p]
            v = value
            while v%p == 0:
                v //= p
                k -= 1
            sub *= pow(p, k, inf)
            sub %= inf
        ans += sub
        ans %= inf
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10**9+7
prime_numbers = set()

def factorization(n):
    counter = Counter()
    tmp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if tmp%i == 0:
            cnt = 0
            while tmp%i == 0:
                cnt += 1
                tmp //= i
            counter[i] += cnt
            prime_numbers.add(i)

    if tmp != 1:
        counter[tmp] += 1
        prime_numbers.add(tmp)

    if counter=={}:
        counter[n] += 1
        prime_numbers.add(n)

    return counter



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

d_list = []
for a in a_list:
    d_list.append(factorization(a))

LCM = 1
# for p in prime_numbers:
#     max_num = 0
#     for d in d_list:
#         if d[p] > max_num:
#             max_num = d[p]
#     LCM *= p**max_num

p_dict = dict()
for p in prime_numbers:
    p_dict[p] = 1

for d in d_list:
    for key, value in d.items():
        if value > p_dict[key]:
            p_dict[key] = value

for key, value in p_dict.items():
    LCM *= key**value

print(sum(list(map(lambda x: (LCM // x) % mod, a_list))) % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10**9+7
prime_numbers = set()

def factorization(n):
    counter = Counter()
    tmp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if tmp%i == 0:
            cnt = 0
            while tmp%i == 0:
                cnt += 1
                tmp //= i
            counter[i] += cnt
            prime_numbers.add(i)

    if tmp != 1:
        counter[tmp] += 1
        prime_numbers.add(tmp)

    if counter=={}:
        counter[n] += 1
        prime_numbers.add(n)

    return counter



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

d_list = []
for a in a_list:
    d_list.append(factorization(a))

LSM = 1
for p in prime_numbers:
    max_num = 0
    for d in d_list:
        if d[p] > max_num:
            max_num = d[p]
    LSM *= p**max_num

print(sum(list(map(lambda x: (LSM // x) % mod, a_list))) % mod)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import math
mod = 10**9+7

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

def multiple(a, b):
    return a*b // euclid(a, b)

def lcm(nums):
        return reduce(multiple, nums)

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

LCM = lcm(a_list)

print(sum(list(map(lambda x: (LCM // x) % mod, a_list))) % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10**9+7
prime_numbers = set()

def factorization(n):
    counter = Counter()
    tmp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if tmp%i == 0:
            cnt = 0
            while tmp%i == 0:
                cnt += 1
                tmp //= i
            counter[i] += cnt
            prime_numbers.add(i)

    if tmp != 1:
        counter[tmp] += 1
        prime_numbers.add(tmp)

    if counter=={}:
        counter[n] += 1
        prime_numbers.add(n)

    return counter



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


d_list = []
for a in a_list:
    d_list.append(factorization(a))

mul_dct = {}
for p in prime_numbers:
    max_num = 0
    for d in d_list:
        if d[p] > max_num:
            max_num = d[p]
    mul_dct[p] = max_num

LSM = 1
for key, value in mul_dct.items():
    LSM *= key**value

print(sum(list(map(lambda x: (LSM // x) % mod, a_list))) % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10**9+7
prime_numbers = set()

def factorization(n):
    counter = Counter()
    tmp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if tmp%i == 0:
            cnt = 0
            while tmp%i == 0:
                cnt += 1
                tmp //= i
            counter[i] += cnt
            prime_numbers.add(i)

    if tmp != 1:
        counter[tmp] += 1
        prime_numbers.add(tmp)

    if counter=={}:
        counter[n] += 1
        prime_numbers.add(n)

    return counter



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


d_list = []
for a in a_list:
    d_list.append(factorization(a))

mul_dct = {}
for p in prime_numbers:
    max_num = 0
    for d in d_list:
        if d[p] > max_num:
            max_num = d[p]
    mul_dct[p] = max_num

LSM = 1
for key, value in mul_dct.items():
    LSM *= key**value

print(sum(list(map(lambda x: LSM // x, a_list))) % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

N = int(input())
A = list(map(int,input().split()))
l = 1
ans, mod = 0, 1000000007

for x in A:
    l = lcm(l, x)

for x in A:
    ans = ans + l//x
    if ans > mod: ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import sys
from collections import defaultdict
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))

d = defaultdict(int)
def factorize2(n,d): # 素因数分解　2次元素数リスト([素数,指数])
    i = 2
    m = 1
    table = defaultdict(int)
    sign = -1
    while i * i <= n:
        j = 0
        while n % i == 0:
            n //= i
            j += 1
        if j != 0:
            d[i] = max(d[i],j)
            table[i] = j
        if i >= 5:
            if sign < 0:
                sign = 1
                i = 6*m + sign
            else:
                m += 1
                sign = -1
                i = 6*m + sign
        elif i == 2:
            i += 1
        elif i == 3:
            i = 5
    if n > 1:
        d[n] = max(d[n],1)
        table[n] = 1
    return table # list

 
ans = 0
mod = 10**9+7
T = []
for i in range(N):
    T.append(factorize2(A[i],d))
for i in range(N):
    b = 1
    for j in d.keys():
        b = (b*j**(d[j]-T[i][j]))%mod
    ans = (ans+b)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
import sys, copy, math, heapq, bisect
from itertools import accumulate
from collections import deque, defaultdict, Counter
input = sys.stdin.readline # 文字列の入力のとき'/n'まで受け取るので注意!!!
sys.setrecursionlimit(500000)
d = defaultdict(int)
def factorize2(n,d): # 素因数分解　2次元素数リスト([素数,指数])
    i = 2
    m = 1
    table = defaultdict(int)
    sign = -1
    while i * i <= n:
        j = 0
        while n % i == 0:
            n //= i
            j += 1
        if j != 0:
            d[i] = max(d[i],j)
            table[i] = j
        if i >= 5:
            if sign < 0:
                sign = 1
                i = 6*m + sign
            else:
                m += 1
                sign = -1
                i = 6*m + sign
        elif i == 2:
            i += 1
        elif i == 3:
            i = 5
    if n > 1:
        d[n] = max(d[n],1)
        table[n] = 1
    return table # list
def lcm(a, b): # 最小公倍数
    return a * b // gcd(a, b) # int


ans = 0
T = []
for i in range(N):
    T.append(factorize2(A[i],d))
for i in range(N):
    b = 1
    for j in d.keys():
        b *= j**(d[j]-T[i][j])
    ans += b
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
def lcm(a, b): # 最小公倍数
    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 numpy as np
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

def eucrid(a,b):
  a,b=max(a,b),min(a,b)
  while True:
    if a%b==0:
      return b
    else:
      a,b=b,a%b
m=a[0]
for i in range(n):
  m=m//eucrid(m,a[i])*a[i]
b=0
for i in a:
  b+=m*pow(i,mod-2,mod)%mod
print(b%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import fractions
n=int(input())
a=list(map(int,input().split()))
a2=np.array(a.copy())
mod=10**9+7
def f(n,i):
  for j in range(i+1,n):
    c=fractions.gcd(a[i],a[j])
    a[j]//=c

for i in range(n):
  f(n,i)
m = 1
for i in a:
  m = m * i
b=(m//a2)%mod
ans=np.sum(b)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
a2=np.array(a.copy())
mod=10**9+7
def f(n,i):
  for j in range(i+1,n):
    c=eucrid(a[i],a[j])
    a[j]//=c
    
def eucrid(a,b):
  if a < b:
    a,b=b,a
  while True:
    if a%b==0:
      return b
    else:
      a,b=b,a%b

for i in range(n):
  f(n,i)
m = 1
for i in a:
  m = m * i
b=(m//a2)%mod
ans=np.sum(b)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
a2=a.copy()
a2=np.array(a2)
mod=10**9+7
def f(n,i):
  if i==n-1:
    return
  for j in range(i+1,n):
    c=eucrid(a[i],a[j])
    a[j]//=c
    
def eucrid(a,b):
  a,b=max(a,b),min(a,b)
  while True:
    if a%b==0:
      return b
    else:
      a,b=b,a%b

for i in range(n):
  f(n,i)
m=1
for i in a:
  m = m * i
b=m//a2
ans=b.sum()%mod
print(ans)

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)
    print(ans%(10**9+7))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
from fractions import gcd

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

temp=A[0]
for item in A:
    temp=temp*item//gcd(temp,item)

ans=0
for item in A:
    ans+=temp//item
    ans%=10**9+7
#print(temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(n,m):
  if n>m:
    return gcd(m,n);
  if n==0:
    return m;
  return gcd(m-n*(m//n),n)

def lcm(x, y):
    return (x * y) // gcd(x, y)
  
n=int(input())
a=list(map(int,input().split()))
s=1
for i in a:
  s=lcm(s,i)
ans=0
for i in a:
  ans+=s//i
print(ans % 1000000007)