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:
# -*- coding: utf-8 -*-

#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))



#複数の最小公倍数
def calc_lcm_list(l):
    lcm = l[0]
    for i in range(1, N):
        lcm = lcm * l[i] // fractions.gcd(lcm, l[i])
    return lcm


import fractions
N = input_one_number()
lstA = input_multiple_number_as_list()

gcd = calc_lcm_list(lstA)

ans = 0
for a in lstA:
    ans += (gcd // a)
    ans %= 1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

N = ii()
A = lmis()
l = 1
for a in A:
    l = lcm(l, a)
ans = 0
for a in A:
    ans += l//a
    ans %= N1097
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    A = lmis()
    l = 1
    for a in A:
        l = lcm(l, a)
    ans = 0
    for a in A:
        ans += l//a
        ans %= N1097
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
N1097 = 10**9 + 7

def main():
    N = ii()
    A = lmis()
    l = 1
    for a in A:
        l = lcm(l, a)
    ans = 0
    for a in A:
        ans += l//a
        ans %= N1097
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    A = lmis()
    l = 1
    for a in A:
        l = lcm(l, a)
    ans = 0
    for a in A:
        ans += l//a
        ans %= N1097
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
lcm = lambda a, b: a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    A = lmis()
    l = 1
    for a in A:
        l = lcm(l, a)
    ans = 0
    for a in A:
        ans += l//a
        ans %= N1097
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter

MOD = 1000000007  # type: int

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = {i:0 for i in range(1, n+1) if is_prime[i-1]}
    # return is_prime, table
    return table

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

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

    for i in range(N):
        decom = Counter(prime_decomposition(A[i]))

        for d,number in decom.items():
            if table.get(d) == None:
                table[d] = number
                continue

            if table[d] < number:
                table[d] = number
    LCM = 1
    for key,value in table.items():
        LCM *= key**value

    print(sum([LCM//a for a in A])%MOD)

    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:
#!/usr/bin/env python3
import sys
import fractions
from functools import reduce

MOD = 1000000007  # type: int

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

def solve(N: int, A: "List[int]"):
    LCM = reduce(lcm,A)
    answer = 0
    for i in range(N):
        answer += LCM//A[i]
        answer %= MOD
    print(answer)
    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:
from fractions import gcd


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


l = 1

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


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


N = int(input())
A = list(map(int, input().split())) 
MOD = 10**9 + 7
def gcd(a,b):
  x = max([a,b])
  y = min([a,b])
  while y:
    x, y = y, x % y
  return x


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


l = 1

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


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


N = int(input())
A = list(map(int, input().split())) 
MOD = 10**9 + 7
def primes(num):
    if num == 1:
        d = defaultdict(int)
        d[1] = 1
        return d

    i = 2
    d = defaultdict(int)
    while i * i <= num:
        while num % i == 0:
            num //= i
            d[i] += 1
        i += 1
    if num > 1:
        d[num] += 1

    return d

d = primes(A[0])

for a in A[1:]:
    tmp_d = primes(a)
    dk = set(d.keys())
    tmp_dk = set(tmp_d.keys())
    dk = dk | tmp_dk
    for k in dk:
        d[k] = max(d[k], tmp_d[k])

lcm = 1

for k in d.keys():
    lcm *= pow(k, d[k])


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


N = int(input())
A = list(map(int, input().split())) 
MOD = 10**9 + 7
def primes(num):
    if num == 1:
        d = defaultdict(int)
        d[1] = 1
        return d

    i = 2
    d = defaultdict(int)
    while i * i <= num:
        while num % i == 0:
            num //= i
            d[i] += 1
        i += 1
    if num > 1:
        d[num] += 1

    return d

d = primes(A[0])

for a in A[1:]:
    tmp_d = primes(a)
    dk = set(d.keys())
    tmp_dk = set(tmp_d.keys())
    dk = dk | tmp_dk
    for k in dk:
        d[k] = max(d[k], tmp_d[k])

lcm = 1

for k in d.keys():
    lcm *= pow(k, d[k]) % MOD


ans = 0
for i in range(N):
    ans += (lcm // A[i])
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


N = int(input())
A = list(map(int, input().split())) 
MOD = 10**9 + 7
def gcd(a,b):
  x = max([a,b])
  y = min([a,b])
  while y:
    x, y = y, x % y
  return x

# x * y = lcm(x, y) // gcd(x, y)より
def lcm(x, y):
  return x * y // gcd(x, y)

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

ans = 0
for i in range(N):
    ans += l // A[i]
    #ans %= MOD

print(ans%MOD)


"""
def primes(num):
    if num == 1:
        d = defaultdict(int)
        d[1] = 1
        return d

    i = 2
    d = defaultdict(int)
    while i * i <= num:
        while num % i == 0:
            num //= i
            d[i] += 1
        i += 1
    if num > 1:
        d[num] += 1

    return d

d = primes(A[0])

for a in A[1:]:
    tmp_d = primes(a)
    dk = set(d.keys())
    tmp_dk = set(tmp_d.keys())
    dk = dk | tmp_dk
    for k in dk:
        d[k] = max(d[k], tmp_d[k])

lcm = 1

for k in d.keys():
    lcm *= k**d[k] % MOD


ans = 0
for i in range(N):
    ans += (lcm // A[i])
    ans %= MOD

print(ans)
"""

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


N = int(input())
A = list(map(int, input().split())) 
MOD = 10**9 + 7
def gcd(a,b):
  x = max([a,b])
  y = min([a,b])
  while y:
    x, y = y, x % y
  return x

# x * y = lcm(x, y) // gcd(x, y)より
def lcm(x, y):
  return x * y // gcd(x, y)

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

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

print(ans)


"""
def primes(num):
    if num == 1:
        d = defaultdict(int)
        d[1] = 1
        return d

    i = 2
    d = defaultdict(int)
    while i * i <= num:
        while num % i == 0:
            num //= i
            d[i] += 1
        i += 1
    if num > 1:
        d[num] += 1

    return d

d = primes(A[0])

for a in A[1:]:
    tmp_d = primes(a)
    dk = set(d.keys())
    tmp_dk = set(tmp_d.keys())
    dk = dk | tmp_dk
    for k in dk:
        d[k] = max(d[k], tmp_d[k])

lcm = 1

for k in d.keys():
    lcm *= k**d[k] % MOD


ans = 0
for i in range(N):
    ans += (lcm // A[i])
    ans %= MOD

print(ans)
"""

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


N = int(input())
A = list(map(int, input().split())) 
MOD = 10**9 + 7
def primes(num):
    if num == 1:
        d = defaultdict(int)
        d[1] = 1
        return d

    i = 2
    d = defaultdict(int)
    while i * i <= num:
        while num % i == 0:
            num //= i
            d[i] += 1
        i += 1
    if num > 1:
        d[num] += 1

    return d

d = primes(A[0])

for a in A[1:]:
    tmp_d = primes(a)
    dk = set(d.keys())
    tmp_dk = set(tmp_d.keys())
    dk = dk | tmp_dk
    for k in dk:
        d[k] = max(d[k], tmp_d[k])

lcm = 1

for k in d.keys():
    lcm *= k**d[k] % MOD


ans = 0
for i in range(N):
    ans += (lcm // A[i])
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


N = int(input())
A = list(map(int, input().split())) 
MOD = 10**9 + 7
def primes(num):
    if num == 1:
        d = defaultdict(int)
        d[1] = 1
        return d

    i = 2
    d = defaultdict(int)
    while i * i <= num:
        while num % i == 0:
            num //= i
            d[i] += 1
        i += 1
    if num > 1:
        d[num] += 1

    return d

d = primes(A[0])

for a in A[1:]:
    tmp_d = primes(a)
    dk = set(d.keys())
    tmp_dk = set(tmp_d.keys())
    dk = dk | tmp_dk
    for k in dk:
        d[k] = max(d[k], tmp_d[k])

lcm = 1

for k in d.keys():
    lcm *= k**d[k]


ans = 0
for i in range(N):
    ans += (lcm // A[i])
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

l = 1
for a in A:
  l = lcm(l, a)
  
answer = 0
for a in A:
  answer = (answer + l * pow(a, MOD - 2, MOD)) % MOD
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
a = np.array(input().split(),dtype = int)

#素数の書き出し
pn = [2]
for i in range(3,10**3+1000):
    for j in pn:
        if i%j == 0:
            break
        elif j == pn[-1]:
            pn.append(i)

#素因数分解
def pf(k):
    k_int = k
    p = [[],[]]
    i = 0
    times = 0
    while pn[i]*pn[i] <= k_int:
        if k%pn[i] == 0:
            times += 1
            k //= pn[i]
        else:
            if not times == 0:
                p[0].append(pn[i])
                p[1].append(times)
            i += 1
            times = 0
    if not k == 1:
        p[0].append(k)
        p[1].append(1)
    return p

#Aの素因数分解と最小公倍数の決定
a_pf = []
L = [[],[]]
for i in range(n):
    a_pf.append(pf(a[i]))
    for j in a_pf[i][0]:
        if j in L[0]:
            L[1][L[0].index(j)] = max([L[1][L[0].index(j)],a_pf[i][1][a_pf[i][0].index(j)]])
        else:
            L[0].append(j)
            L[1].append(a_pf[i][1][a_pf[i][0].index(j)])

#Bの決定とその和
mod = 10**9+7
bsum = 0
for i in range(n):
    b = 1
    for j in L[0]:
        if j in a_pf[i][0]:
            b *= j**(L[1][L[0].index(j)]-a_pf[i][1][a_pf[i][0].index(j)])
        else:
            b *= j**L[1][L[0].index(j)]
        b %= mod
    bsum += b
    bsum %= mod
print(bsum)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return tuple(map(int,input().split()))

def onem(): #Nとかの取得
    return int(input())


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)

def main():
    n = onem()
    a = l()

    k = lcm_list(a[:n//2])
    kk = lcm_list(a[n//2:])
    k = lcm(k,kk)
    su = 0

    for i in range(n):
        su += k//a[i]
        
        su %= mod

    print(su)

if __name__ == "__main__":
    
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return tuple(map(int,input().split()))

def onem(): #Nとかの取得
    return int(input())


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)

def main():
    n = onem()
    a = l()

    k = lcm_list(a)

    su = 0

    for i in range(n):
        su += k//a[i]
        
        su %= mod

    print(su)

if __name__ == "__main__":
    
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return tuple(map(int,input().split()))

def onem(): #Nとかの取得
    return int(input())


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)

def main():
    n = onem()
    a = l()

    k = lcm_list(a)

    su = 0

    for i in range(n):
        su += int(k//a[i])
        
        su %= mod

    print(su)

if __name__ == "__main__":
    
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))

def onem(): #Nとかの取得
    return int(input())


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)

def main():
    n = onem()
    a = l()

    k = lcm_list(a)

    su = 0

    for i in range(n):
        su += int(k//a[i])
        
        su %= mod

    print(su)

if __name__ == "__main__":
    
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))

def onem(): #Nとかの取得
    return int(input())


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)


if __name__ == "__main__":
    n = onem()
    a = l()

    k = lcm_list(a)

    su = 0

    for i in range(n):
        su += int(k//a[i])
        
        su %= mod

    print(su)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))

def onem(): #Nとかの取得
    return int(input())


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)


if __name__ == "__main__":
    n = onem()
    a = l()

    k = lcm_list(a)

    su = 0

    for i in range(n):
        su += k//a[i]
        su %= mod

    print(su)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))

def onem(): #Nとかの取得
    return int(input())


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 = onem()
a = l()

k = lcm_list(a)

su = 0

for i in range(n):
    su += k//a[i]
    su %= mod

print(su)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

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 = onem()
a = l()

k = lcm_list(a)



su = 0

for i in range(n):
    su += k//a[i]
    su %= mod

print(su)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

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 = onem()
a = l()

k = lcm_list(a)

po = [k//a[i] for i in range(n)]

su = 0

for i in range(n):
    su += po[i]
    su %= mod

print(su)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
	while y:
		r = x % y
		x = y
		y = r
	return x

MOD = int(1e9 + 7)
n = int(input())
a = list(map(int, input().split()))
a.sort()
if n == 1:
	print(1)
	exit()
g = gcd(a[0], a[1])
tmp = a[0] // g * a[1]
for i in range(2, len(a)):
	g = gcd(tmp, a[i])
	tmp = tmp // g * a[i]
ans = 0
for i in a:
	ans += tmp // i
	ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
	while y:
		r = x % y
		x = y
		y = r
	return x

MOD = int(1e9 + 7)
n = int(input())
a = list(map(int, input().split()))
if n == 1:
	print(1)
	exit()
g = gcd(a[0], a[1])
tmp = a[0] // g * a[1]
for i in range(2, len(a)):
	g = gcd(tmp, a[i])
	tmp = tmp // g * a[i]
ans = 0
for i in a:
	ans += tmp // i
	ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x%y)

MOD = int(1e9 + 7)
n = int(input())
a = list(map(int, input().split()))
if n == 1:
	print(1)
	exit()
g = gcd(a[0], a[1])
tmp = a[0] * a[1] // g
for i in range(2, len(a)):
	g = gcd(tmp, a[i])
	tmp = tmp * a[i] // g
ans = 0
for i in a:
	ans += tmp // i
	ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

p = [0 for _ in range(10**6)]
for i in range(n):
    m = l[i]
    cnt = 0
    while m%2 == 0:
        m = m//2
        cnt += 1
    p[2] = max(p[2], cnt)
    for j in range(3, l[i]+1, 2):
        cnt = 0
        while m%j == 0:
            m = m//j
            cnt += 1
        p[j] = max(p[j], cnt)

lcm = 1
for i in range(len(p)):
    lcm *= i**p[i]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

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

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

_lcm = l[0]
for i in range(n):
    _lcm = lcm(_lcm, l[i])

ans = 0
for i in range(n):
    ans += (_lcm/l[i])%(10**9+7)
print(int(ans)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from copy import deepcopy
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


def prime_decomposition(n):
    table = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            table += [i]
            n //= i
        if n == 1:
            break
    if n != 1:
        table += [a]
    return table


n = I()
A = LI()
prime_d = defaultdict(int)
for a in A:
    for p, cnt in Counter(prime_decomposition(a)).items():
         if prime_d[p] < cnt:
             prime_d[p] = cnt


lcm = 1
for p, cnt in prime_d.items():
    lcm = lcm * pow(p, cnt, mod) % mod


inv = list(range(10 ** 6 + 1))
for i in range(1, 10 ** 6 + 1):
    inv[i] = pow(inv[i], mod-2, mod)


ans = 0
for a in A:
    ans = ans + lcm * inv[a]


print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:

import fractions
from functools import reduce
from copy import deepcopy
from collections import Counter,defaultdict

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
def gcd(A):
    gcds=A[0]
    for i in A:
        gcds=fractions.gcd(i,gcds)
    return gcds

def resolve():
    N=int(input())
    A=list(map(int,input().split()))
    gcda=gcd(A)
    A=[i//gcda for i in A]
    PA=[Counter(prime_factorize(i)) for i in A]

    lcm=dict()
    for prims in PA:
        for prm in prims:
            cm= lcm[prm] if  prm in lcm else 0
            lcm[prm]=max(prims[prm],cm)

    sm=0
    for i in PA:
        B=1
        for prm in lcm:
            cm = i[prm] if prm in i else 0
            B*=prm**(lcm[prm]-cm)
        sm=(sm+B)%1000000007
    print(sm)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:

import fractions
from functools import reduce
from copy import deepcopy
from collections import Counter,defaultdict

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
def gcd(A):
    gcds=A[0]
    for i in A:
        gcds=fractions.gcd(i,gcds)
    return gcds

def resolve():
    N=int(input())
    A=list(map(int,input().split()))
    gcda=gcd(A)
    A=[i//gcda for i in A]
    PA=[Counter(prime_factorize(i)) for i in A]

    lcm=dict()
    for prims in PA:
        for prm in prims:
            cm= 0 if not prm in lcm else lcm[prm]
            lcm[prm]=max(prims[prm],cm)

    sm=0
    for i in PA:
        B=1
        for prm in lcm:
            cm = 0 if not prm in i else i[prm]
            B*=prm**(lcm[prm]-cm)
        sm=(sm+B)%1000000007
    print(sm)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:

import fractions
from functools import reduce
from copy import deepcopy


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

def gcd(A):
    gcds=A[0]
    for i in A:
        gcds=fractions.gcd(i,gcds)
    return gcds

def lcm_list(numbers):
    lcm=1
    for i in numbers:
        lcm=lcm_base(lcm,i)
    return lcm
def resolve():
    N=int(input())
    A=list(map(int,input().split()))
    gcda=gcd(A)
    A=[i//gcda for i in A]
    lcma=lcm_list(A)

    B=[(lcma//i)%1000000007 for i in A]
    sm=0 

    for i in B:
        sm=(sm+i)%1000000007
    print(sm)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:

import fractions
from functools import reduce
from copy import deepcopy


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



def lcm_list(numbers):
    lcm=1
    for i in numbers:
        lcm=lcm_base(lcm,i)
    return lcm
def resolve():
    N=int(input())
    A=list(map(int,input().split()))
    
    lcma=lcm_list(A)

    B=[(lcma//i)%1000000007 for i in A]
    sm=0 

    for i in B:
        sm=(sm+i)%1000000007
    print(sm)

if __name__ == "__main__":
    resolve()