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:
from collections import Counter
"""素因数分解"""
def prime_decomposition(n):
    i = 2
    tank = []
    while i * i <= n:
        while n%i == 0:
            n /= i
            tank.append(i)
        i += 1
    if n > 1:
        tank.append(int(n))
    return dict(Counter(tank))

def main():
    n = int(input())
    A = list(map(int,input().split()))
    mod = 10**9 + 7
    dct = {}
    for a in A:
        tmp = prime_decomposition(a)
        for k, v in tmp.items():
            if k not in dct.keys():
                dct[k] = v
            else:
                if v > dct[k]:
                    dct[k] = v
    l = 1
    for k,v in dct.items():
        l *= k**v
    res = 0
    for a in A:
        res += l//a
    print(res % mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import functools
"""最大公約数"""
def gcd(a,b):
    import fractions
    return fractions.gcd(a,b)

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

def m(nums):
    return functools.reduce(lcm, nums)

def main():
    n = int(input())
    A = list(map(int,input().split()))
    mod = 10**9+7
    l = m(A)
    res = 0
    for a in A:
        res += l//a
        res %= mod
    print(res%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

"""最大公約数"""
def gcd(a,b):
    return fractions.gcd(a,b)

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


def main():
    n = int(input())
    A = list(map(int,input().split()))
    mod = 10**9+7
    l = A[0]
    for i in range(1, n):
        l = lcm(l, A[i])
    res = 0
    
    for a in A:
        res += l//a
        res %= mod
    print(res%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

import fractions

"""最大公約数"""
def gcd(a,b):
    return fractions.gcd(a,b)

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


def main():
    n = int(input())
    A = list(map(int,input().split()))
    mod = 10**9+7
    l = A[0]
    for i in range(1, n):
        l = lcm(l, A[i])
    res = 0
    
    for a in A:
        res += l//a
        res %= mod
    print(res%mod)

main()

Submission status: Time Limit Exceeded

Solution code:
import functools
import fractions
"""最大公約数"""
def gcd(a,b):
    return fractions.gcd(a,b)
"""最小公倍数"""
def lcm(a,b):
    f = gcd(a,b)
    return a*b//f
def m(nums):
    return functools.reduce(lcm, nums)

n = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
l = m(A)
res = 0
for a in A:
    res += l//a
    res %= mod
print(res%mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions
"""最大公約数"""
def gcd(a,b):
    return fractions.gcd(a,b)

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

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
mod = 10**9+7
n = int(input())
a = list(map(int,input().split()))
ans = 0
l = 1
for i in range(n):
    l = l*a[i]//gcd(l,a[i])
for i in a:
    ans = (ans + l*pow(i,mod-2,mod)) % 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()))
l = 1
ans = 0
for i in range(n):
    l = l*a[i]//gcd(l,a[i])
for i in range(n):
    ans = (ans + l//a[i]) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
from fractions import gcd
def lcm(list):
    num = 1
    for x in list:
        num = num//gcd(num, x)*x
    return num

def Pow(a,n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod

N = int(input())
A = list(map(int, input().split()))
M = lcm(A)
R = [0]*N
for i in range(N):
    R[i] = Pow(A[i],mod-2)
ans = 0
for i in range(N):
    ans = (ans+M*R[i])%mod
print(ans)

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())
Alist = list(map(int, input().split()))
l = 1
ans = 0
for a in Alist:
    l = lcm(l, a)
for a in Alist:
    ans += l//a
print(ans%(10**9+7))

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())
Alist = list(map(int, input().split()))
l = lcm_list(Alist)
ans = 0
for a in Alist:
    ans += l//a
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

def lcm(x,y):
    return x*y//gcd(x,y)
mod = 10**9+7
n = int(input())
a = list(map(int,input().split()))
L = a[0]
for i in a:
    L = lcm(L,i)
    
ans = 0
for i in a:
    ans += (L // i )
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from collections import defaultdict


def sieve(x):
    """
    Sieve of Eratosthenes
    :param x: max value
    :return: list of primes
    """

    primes = []
    li = list(range(2, x + 1))

    while li[0] <= sqrt(x):
        p = li[0]
        primes.append(p)
        li = [e for e in li if e % p != 0]

    primes += li
    return primes


def prime_fact(x):
    for e in p:
        cnt = 0
        while x % e == 0:
            x //= e
            cnt += 1
        if cnt > 0:
            pf[e] = max(pf[e], cnt)


def prime_fact2(x):
    ret = defaultdict(int)
    for e in p:
        cnt = 0
        while x % e == 0:
            x //= e
            cnt += 1

        if cnt > 0:
            ret[e] = cnt

    return ret


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

p = sieve(MAX)
pf = defaultdict(int)

for e in a:
    prime_fact(e)

ans = 0
for e in a:
    e_pf = prime_fact2(e)
    b = 1
    for k, v in pf.items():
        b *= pow(k, v - e_pf[k], mod)

    ans += b
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from collections import defaultdict


def sieve(x):
    """
    Sieve of Eratosthenes
    :param x: max value
    :return: list of primes
    """

    primes = []
    li = list(range(2, x + 1))

    while li[0] <= sqrt(x):
        p = li[0]
        primes.append(p)
        li = [e for e in li if e % p != 0]

    primes += li
    return primes


def prime_fact(x):
    for e in p:
        cnt = 0
        while x % e == 0:
            x //= e
            cnt += 1
        pf[e] = max(pf[e], cnt)


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

p = sieve(MAX)
pf = [0] * MAX

for e in a:
    prime_fact(e)

lcm = 1
for i, e in enumerate(pf[1:], 1):
    lcm *= pow(i, e)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
MOD = 10**9+7
def prime_table(n):
  if n < 2:
    return []
  prime = [2]
  limit = int(n**0.5)
  data = [i+1 for i in range(2,n,2)]
  while True:
    p = data[0]
    if limit <= p:
      return prime + data
    prime.append(p)
    data = [e for e in data if e%p != 0]
def modinv(a,m=MOD):
  b,u,v = m,1,0
  while b:
    t = a//b
    a,u = a-t*b,u-t*v
    a,b,u,v = b,a,v,u
  u %= m
  if u < 0:
    u += m
  return u
data = prime_table(max(a))
prime = [0] * len(data)
l_prime = []
for i in a:
  for j in range(len(data)):
    c = 0
    while True:
      if i % data[j] == 0:
        i = i // data[j]
        c += 1
      else:
        break
    prime[j] = max(prime[j],c)
    if i == 1:
      break
  if i != 1:
    l_prime.append(i)
lcm = 1
for i,j in zip(data,prime):
  lcm = (lcm*pow(i,j,MOD))%MOD
for i in l_prime:
  lcm = (lcm*i) % MOD
c = 0
for i in a:
  c += lcm*modinv(i,MOD)
  c %= MOD
print(c)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
MOD = 10**9+7
def prime_table(n):
  if n < 2:
    return []
  prime = [2]
  limit = int(n**0.5)
  data = [i+1 for i in range(2,n,2)]
  while True:
    p = data[0]
    if limit <= p:
      return prime + data
    prime.append(p)
    data = [e for e in data if e%p != 0]
def modinv(a,m=MOD):
  b,u,v = m,1,0
  while b:
    t = a//b
    a,u = a-t*b,u-t*v
    a,b,u,v = b,a,v,u
  u %= m
  if u < 0:
    u += m
  return u
data = prime_table(max(a))
prime = [0] * len(data)
for i in a:
  for j in range(len(data)):
    c = 0
    while True:
      if i % data[j] == 0:
        i = i // data[j]
        c += 1
      else:
        break
    prime[j] = max(prime[j],c)
lcm = 1
for i,j in zip(data,prime):
  lcm = (lcm*pow(i,j,MOD))%MOD
c = 0
for i in a:
  c += lcm*modinv(i,MOD)
  c %= MOD
print(c)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

MOD = 1000000007

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = reduce(lcm, a)

arr = [0] * n
for i in range(n):
    arr[i] = LCM // a[i]
print(sum(arr) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

MOD = 10**9+7

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = reduce(lcm, a)

arr = [0] * n
for i in range(n):
    arr[i] = LCM // a[i]
print(sum(arr) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools

MOD = 10**9+7

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
def arr(lis):
    return functools.reduce(lcm, lis)

n = int(input())
a = [int(_) for _ in input().split()]
LCM = arr(a)

arr = [0] * n
for i in range(n):
    arr[i] = LCM // a[i]
print(sum(arr) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools

MOD = 10**9+7

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

    n = int(input())
    a = [int(_) for _ in input().split()]
    LCM = functools.reduce(lambda x, y : lcm(x, y), a)

    arr = [0] * n
    for i in range(len(a)):
        arr[i] = LCM // a[i]
    print(sum(arr) % MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools

MOD = 10**9+7

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = functools.reduce(lambda x, y : lcm(x, y), a)

ans_arr = [0] * n
for i in range(len(a)):
    ans_arr[i] = LCM // a[i]
print(sum(ans_arr) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools

MOD = 10**9+7

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = functools.reduce(lambda x, y : lcm(x, y), a, 1)

ans_arr = [0] * n
for i in range(len(a)):
    ans_arr[i] = LCM // a[i]
print(sum(ans_arr) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys

MOD = 10**9+7
input = sys.stdin.readline

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = 1
for i in a:
    LCM = lcm(LCM, i)

ans_arr = [0] * n
for i in range(len(a)):
    ans_arr[i] = LCM // a[i]
print(sum(ans_arr) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions

MOD = 10**9+7

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = 1
for i in a:
    LCM = lcm(LCM, i)

ans_arr = [0] * n
for i in range(len(a)):
    ans_arr[i] = LCM // a[i]
print(sum(ans_arr) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

MOD = 10**9+7

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = reduce(lambda x, y: lcm(x, y), a)

ans = 0
for i in a:
    ans += LCM // i
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

MOD = 10**9+7

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = 1
for i in a:
    LCM = lcm(LCM, i)

ans = 0
for i in a:
    ans += LCM // i
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MAX_PRIME = 10**5
is_prime = [1] * MAX_PRIME
primes = []
is_prime[0] = 0
is_prime[1] = 0
for i in range(MAX_PRIME):
    if is_prime[i]:
        primes.append(i)
        for j in range(2, ((MAX_PRIME-1)//i) + 1):
            is_prime[i*j] = 0

def factorization(n):
    factor = {}
    for p in primes:
        if p ** 2 > n:
            break
        while n % p == 0:
            n //= p
            if p not in factor:
                factor[p] = 1
            else:
                factor[p] += 1
    if n > 1:
        factor[n] = 1
    return factor

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

ans = 0
l = {}
law = 10 ** 9 + 7
for x in a:
    fx = factorization(x)
    for p, c in fx.items():
        if p not in l:
            l[p] = c
            ans *= p ** c
            ans %= law
        elif c > l[p]:
            ans *= p ** (c - l[p])
            ans %= law
            l[p] = c
    b = 1
    for p, c in l.items():
        if p in fx:
            b *= p ** (l[p] - fx[p])
        else:
            b *= p ** l[p]
        b %= law
    ans += b
    ans %= law
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import floor, sqrt
from collections import defaultdict
def pow(x, n, mod):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * x % mod
        x = x * x % mod
        n >>= 1
    return ret

def factors(n):
    d = defaultdict(int)
    for i in range(2,floor(sqrt(n))+1):
        while n % i == 0:
            n //= i
            d[i] += 1
        if n == 1:
            break
    if n != 1:
        d[n] += 1
    return d

mod = 10**9+7
def gcd(x,y):
    a,b = max(x,y),min(x,y)
    r = a % b
    while r != 0:
        a,b = b,r
        r = a % b
    return b
N = int(input())
a = list(map(int,input().split()))
g = a[0]
fs = [None]*N
fs[0] = factors(a[0])
fac = factors(a[0])
for i in range(1,N):
    fs[i] = factors(a[i])
    for k in fs[i]:
        fac[k] = max(fac[k], fs[i][k])
ans = 0
for i in range(N):
    tmp = 1
    for k in fac:
        tmp *= pow(k, fac[k]-fs[i][k], mod)
    ans = (ans+tmp)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9+7
def gcd(x,y):
    a,b = max(x,y),min(x,y)
    r = a % b
    while r != 0:
        a,b = b,r
        r = a % b
    return b
N = int(input())
a = list(map(int,input().split()))
g = a[0]
l = a[0]
for i in range(1,N):
    g = gcd(l,a[i])
    l = (a[i]*l)//g
ans = 0
for i in range(N):
    ans = (ans+l//a[i])%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
from fractions import gcd
n = int(input())
# n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7


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

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

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

ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc152/tasks/abc152_e
# 見た瞬間にわかってしまった天才だ

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
        # 内包表記はpypyでは若干遅いことに注意
        # #numpy使うだろうからこれを残しておくけど
    return ret


MOD = 10**9 + 7
# default import
from collections import defaultdict, Counter, deque
from fractions import gcd


def ret_inv(a, p):
    return pow(a, p - 2, p)


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


N = read_a_int()
A = read_ints()
flat = 1
for a in A:
    flat = lcm(flat, a)

ans = 0
for a in A:
    ans += flat // a
    if ans >= MOD:
        ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

# mod. m での a の逆元 a^{-1} を計算する
# b * a^{-1} (mod m)を計算したい場合はb * modinv(a, m) % m
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = int(a / b)
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u

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

lcm = A[0]
for i in range(1, N):
    lcm = lcm * A[i] // gcd(lcm, A[i])

print(sum([(lcm * modinv(x, int(1e9+7)) % int(1e9+7)) for x in A]) % int(1e9+7))

Submission status: Time Limit Exceeded

Solution code:
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)

law = 10 ** 9 + 7
ans = 0
l = a[0]
for x in a:
    r = lcm(l, x)
    ans *= r // l
    ans += r // x
    ans %= law
    l = r
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)

law = 10 ** 9 + 7
ans = 0
l = a[0]
for x in a:
    r = lcm(l, x)
    ans = (ans * (r // l) + (r // x)) % law
    l = r
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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 = a[0]
for x in a:
    l = lcm(l, x)

law = 10 ** 9 + 7
ans = 0
for x in a:
    ans += l // x
    ans %= law
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import functools
from collections import Counter

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

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

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

lcm = lcm_list(a)
ans = 0
a = Counter(a)

for i,v in a.items():
	ans += (lcm // i)*v % MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import functools

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

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

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

lcm = lcm_list(a)
ans = 0
for i in range(n):
	ans += lcm // a[i]

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import functools
import fractions

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

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

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

lcm = lcm_list(a)
ans = 0
for i in range(n):
	ans += (lcm // a[i]) % MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n = ii()
a = li()
aco = a
aco = list(set(aco))
lis = [0]*(10**3)
rootn = 10**3
for i in range(len(aco)):
    for nm in range(2,rootn):
        if aco[i] % nm != 0:
            continue
        ima = 0
        while(aco[i]%nm == 0):
            ima += 1
            aco[i] = aco[i] //nm
        lis[nm] = max(lis[nm],ima)
aco = list(set(aco))
mod = 10**9 + 7
gcd = 1
for i in range(2,rootn):
    gcd *= (i ** lis[i]) % mod
for i in range(len(aco)):
    gcd *= aco[i] % mod

ans = 0
for i in range(n):
    ans += pow(a[i],mod-2,mod) * gcd % mod
print(ans% mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import lru_cache
import numpy as np


def trial_division(n):
    factor = defaultdict(int)
    tmp = int(np.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor[num] += 1
    factor[n] += 1
    return factor


@lru_cache(maxsize=None)
def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
numbers = defaultdict(int)
for a_i in a:
    for i, v in trial_division(a_i).items():
        numbers[i] = max(v, numbers[i])

l = 1
for i, v in numbers.items():
    l *= powmod(i, v, mod)
    l %= mod


ans = 0
for i in a:
    r = powmod(i, mod-2, mod)
    ans += l * r
    ans %= mod
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import lru_cache
import numpy as np


def trial_division(n):
    factor = defaultdict(int)
    tmp = int(np.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor[num] += 1
    factor[n] += 1
    return factor


@lru_cache(maxsize=None)
def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
numbers = defaultdict(int)
for a_i in a:
    for i, v in trial_division(a_i).items():
        numbers[i] = max(v, numbers[i])

l = 1
for i, v in numbers.items():
    l *= i ** v
    l %= mod


ans = 0
for i in a:
    r = powmod(i, mod-2, mod)
    ans += l * r
    ans %= mod
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import numpy as np


def trial_division(n):
    factor = defaultdict(int)
    tmp = int(np.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor[num] += 1
    factor[n] += 1
    return factor


def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = np.array(list(map(int, input().split())))
mod = 10**9 + 7
numbers = defaultdict(int)
for a_i in a:
    for i, v in trial_division(a_i).items():
        numbers[i] = max(v, numbers[i])

l = 1
for i, v in numbers.items():
    l *= i ** v
    l %= mod

r = powmod(a, mod-2, mod)
ans = 0
for i in r:
    ans += l * i
    ans %= mod
print(int(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
prime = 10**9 + 7
ans = 0

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

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

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

lcm = lcm_list(A)

for i in range(len(A)):
    ans += (lcm // A[i]) % prime

ans %= prime

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    while b:
        r = a % b
        a,b = b,r
    return a

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

MOD = 10**9 + 7

N = int(input())
a = [int(x) for x in input().split()]

m = 1
for e in a:
    m = lcm(m, e)

ans = 0
for e in a:
    ans += m // e
    ans %= MOD

print(ans)