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 -*-

import sys
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)

N = INT()
A = LIST()

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

B = [0] * N
for i, a in enumerate(A):
    B[i] = l // a

ans = 0
for b in B:
    ans += b
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(1000000)

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

P = 10 ** 9 + 7

def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        r = a % b
        a, b = b, r
    
    return b

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


def q_lcm(q, a):
    for k in q:
        a = a // gcd(k, a)
    return a

q = deque()

q.append(1)

for a in A:
    x = q_lcm(q, a)
    if x != 1:
        q.append(x)

_lcm = 1
for x in q:
    _lcm = _lcm * x % P

def mod_mult(a, N):
    if N == 0:
        return 1
    if N % 2 == 0:
        x = mod_mult(a, N // 2)
        return x * x % P
    else:
        x = mod_mult(a, N // 2)
        return x * x * a % P

def mod_s(a, b):
    b_inv = mod_mult(b, P - 2)
    return a * b_inv % P

total = 0

for a in A:
    _s = mod_s(_lcm, a)
    total += _s
    total %= P

print(total)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

a_ = list(set(a))
n_ = len(a_)

lcm = 1
for i in range(n_):
    lcm = lcm * a_[i] // fractions.gcd(lcm, a_[i])

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

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

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_list(numbers):
    return reduce(lcm_base, numbers, 1)

denom = int(1e9+7)

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

lcm_A = lcm_list(A)

tot = 0
for elem in A:
    tot = (tot + lcm_A//elem)%denom
    
print(tot)

Submission status: Time Limit Exceeded

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

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x
z=lcm(A)
MOD=10**9+7
cnt=0
for i in range(N):
  cnt+=(z//A[i])%MOD
print(cnt%MOD)

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()))
mod=10**9+7
ans=0

m=lcm_list(A)
for i in range(n):
    ans+=(m//A[i])%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007

def gcd(a, b):
    t = 1
    while (b != 0):
        t = a % b
        a = b
        b = t
    return a

def lcm(a, b):
    m = a // gcd(a, b)
    m *= b
    # m %= mod
    return m

def modinv(a):
    b = mod
    u = 1
    v = 0
    while (b):
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u

    u %= mod
    if (u < 0):
        u += mod
    return u

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    
    lc = 1
    for i in range(N):
        lc = lcm(lc, A[i])

    ans = 0
    for i in range(N):
        # r = lc * modinv(A[i])
        r = lc // A[i]
        ans += r
        ans %= mod

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math

def gcd(a, b):
    if (a < b) :
        tmp = a
        a = b
        b = tmp
        
    r = a % b
    while (r != 0) :
        a = b
        b = r
        r = a % b
    return b

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




N = int(input())

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



koubai = int(1)
for i in range(N):
    koubai = lcm(koubai, A[i])

ans = int(0)
for i in range(N):
    ans += koubai // A[i]
    
ans %= 1000000007

print(ans)

Submission status: Time Limit Exceeded

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

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

N = int(input())
A =list(map(int,input().split()))
 
if N== 1:
    print(1)
    exit(0)
else:
    tmp = lcm(A[0],A[1])
    for i in range(1,N):
        tmp = lcm(tmp,A[i])
#print(tmp)
ans = 0
for i in range(0,N):
    ans += tmp//A[i]
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import fractions
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = a[0]
dict_data = {}
for i in range(1, n):
    if a[i] not in dict_data:
        dict_data[a[i]] = 1 
        ans = ans * a[i] // fractions.gcd(ans, a[i])
total = 0
for i in range(0, n):
    b = ans // a[i]
    total += b % (10**9 + 7)
print(total % (10**9 + 7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

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

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

P = 10**9 + 7
N = 1000001
inv_t = [0]+[1]
for i in range(2,N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

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

#kyodai=lcm_list(A)
kyodai=A[0]
for i in range(1,n):
    kyodai=lcm_base(kyodai,A[i])

ans=0

for i in range(n):
    ans+=kyodai*inv_t[A[i]]
    ans=ans%P

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
    else:
        return gcd(y, x % y)

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

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

ans = 0
for i in range(n):
	ans += (num//a[i]) % 1000000007
	if ans > 1000000007:
		ans = ans%1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import sys
sys.setrecursionlimit(20000)

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

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

def lcm_numbers(*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()))
B = [0 for _ in range(N)]
mod = 10**9+7

ll = lcm_list(A)

for i in range(N):
    B[i] = (ll//A[i])%mod
print(int(sum(B)%mod))

Submission status: Time Limit Exceeded

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

    return gcd(b, a % b)

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

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    mm = 1000000007
    lcm_a = a[0]

    for i in range(0, n):
        lcm_a = lcm(lcm_a, a[i])

    ans = 0
    for i in range(0, n):
        ans = (ans + lcm_a//a[i]) % mm

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

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

n = int(input())
A = list(map(int, input().split()))
k = lcm_list(A)
r = 0
ln = list(range(n))
for i in ln:
    r += k//A[i]
    if r > 10**9+7:
        r %= 10**9+7
print(r)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
 
import fractions
A.sort(reverse=True) 
k=A[0]
 
for i in range(N-1):
  if k%A[i+1]!=0:
    l=fractions.gcd(A[i+1],k)
    k=k*A[i+1]//l
    #print(A[i+1],k,l)
#print(k)
x=0
for i in range(N):
  x+=k//A[i]
  x=x%1000000007
print(x)

Submission status: Time Limit Exceeded

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

inp_list = list(map(int,(input().split())))

lcm = lcm_list(inp_list)

arr_inp = np.array(inp_list)

arr_inp = lcm // arr_inp

print(np.sum(arr_inp)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import fractions
    import sys
    input = sys.stdin.readline
    N = int(input())
    a = tuple(map(int,input().split()))
    g = a[0]
    MOD = 10**9+7
    for t in a:
        #g = g*a[i]//fractions.gcd(g,a[i])
        g = divmod(g*t,fractions.gcd(g,t))[0]
    res = 0
    for t in a:
        res += divmod(g,t)[0]%MOD
    print(res%MOD)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
#a, b = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])

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

print(c)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
# from functools import lru_cache

M = 10 ** 9 + 7

# @lru_cache(maxsize=None)
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m

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

lcm_ = A[0]
for a in A[1:]:
    lcm_ = lcm_ * a // gcd(lcm_, a)

ans = 0
for a in A:
    m = modinv(a, M)
    ans = (ans + lcm_ * m) % M

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

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)

def main():
    n = II()
    a_s = LI()
    v = lcm_list(a_s)
    ans = 0
    for i in a_s:
        
        ans += (v // i) % MOD
        ans = ans % MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


def main():
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9+7

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

    b = [None]*n
    for i in range(n):
        b[i] = lcm//a[i] % mod

    print(sum(b) % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007

def gcd(a, b):
    t = 1
    while (b != 0):
        t = a % b
        a = b
        b = t
    return a

def lcm(a, b):
    m = a // gcd(a, b)
    m *= b
    # m %= mod
    return m

def modinv(a):
    b = mod
    u = 1
    v = 0
    while (b):
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u

    u %= mod
    if (u < 0):
        u += mod
    return u

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    
    lc = 1
    for i in range(N):
        lc = lcm(lc, A[i])

    ans = 0
    for i in range(N):
        r = lc * modinv(A[i])
        ans += r
        ans %= mod

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
al = list(map(int, input().split()))


# GCD
def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

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

def lcmlist(l):
    res = l[0]
    for x in l[1:]:
        res = lcm(res, x)
    return res

l = lcmlist(al)
res = 0
for a in al:
    res += l//a
    res %= 10**9+7

print(res)

Submission status: Time Limit Exceeded

Solution code:
import fractions

n = int(input())
a = list(map(int, input().split()))
b = [0] * n
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] / fractions.gcd(ans, a[i])
for i in range(n):
    b[i] = ans / a[i]
print(int(sum(b) % ((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)

n = int(input())
a = [int(i) for i in input().split()]
ans = 0
mod = 10**9+7
l = a[0]
for i in range(1,n):
    l = lcm(l,a[i])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from fractions import gcd
from functools import reduce

N = int(input())

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

L = reduce((lambda x, y: x // gcd(x, y) * y), A)

res = 0

MOD = 10**9+7

for a in A:
  res = (res + L//a % MOD) % MOD

print(res)

Submission status: Time Limit Exceeded

Solution code:
def lcm(a):
  from fractions import gcd
  x = a[0]
  for i in range(1, len(a)):
    x = (x * a[i] // gcd(x, a[i]))
  return x

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

mod = 1000000000 + 7
min = lcm(a)
sum = 0
for i in range(n):
  sum = sum + (min//a[i])%mod 
  
print(sum%mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import fractions 
from functools import reduce
arr = list(map(int,input().split()))

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

def lcma(numbers):
    return reduce(lcm_base, numbers, 1)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)    
a = lcma(arr)
ans = 0

for i in arr:
    ans+= (a//i)%1000000007
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce


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


def lcm_list(n):
    return reduce(lcm, n)


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

mod = 10 ** 9 + 7

L = lcm_list(a)
ans = 0
for i in a:
    ans = (ans + (L // i) % mod) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:

def main():
  import sys
  input = sys.stdin.readline

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

  from fractions import gcd
  from functools import reduce

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

  L = reduce(lcm, T)

  B = [None] * N

  for i in range(N):
    B[i] = (L // A[i]) % mod

  print(sum(B) % mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

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

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)

v=lcm(*c)
ans=0

for i in range(n):
    ans+=v//c[i]
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Hello World program in Python
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(raw_input())
A = map(int, raw_input().split())
l = 1
for x in A:
    l = lcm(l, x)
ans, mod = 0, 1000000007
for x in A:
    ans = (ans + l/x) % mod
print(ans)

Submission status: Time Limit Exceeded

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

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


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

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

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

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math

def gcd(a, b):
    if (a < b) :
        tmp = a
        a = b
        b = tmp
        
    r = a % b
    while (r != 0) :
        a = b
        b = r
        r = a % b
    return int(b)

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




N = int(input())

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



koubai = int(1)
for i in range(N):
    koubai = int(lcm(koubai, A[i]))

ans = int(0)
for i in range(N):
    ans += int(koubai // int(A[i]))
    
ans %= int(1000000007)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(a,b):
    return a*b//gcd(a,b)
mod=10**9+7
N = int(input())
A = list(map(int,input().split()))

if N==1:
    print(1)
    exit()

Gcd = lcm(A[0],A[1])
ans = Gcd//A[0]+Gcd//A[1]
temp = Gcd//A[1]
#print(temp)

for i in range(1,N-1):
    Gcd = lcm(A[i],A[i+1])
    temp2 = Gcd//A[i]
    Gcd2 = lcm(temp,temp2)
    #print(Gcd)
    #print(temp)
    #print(temp2)
    #print(Gcd2)
    a = Gcd2//temp
    b = Gcd2//temp2

    temp = Gcd//A[i+1]*b

    a %= mod
    b %= mod
    ans *= a
    ans %= mod
    #Gcd %= mod
    c = A[i+1]
    d = Gcd//c
    d %= mod
    ans += d*b
    #ans += Gcd//A[i+1]*b
    ans %= mod


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
lcm = A[0]
for i in range(1,N):
    lcm = (lcm*A[i])//gcd(lcm,A[i])
MOD = 10**9+7
ans = 0
for a in A:
    b = lcm//a
    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

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

factors = [None] * N

lcms = Counter()
for i,a in enumerate(A):
    factors[i] = factorize(a)
    for k,v in factors[i].items():
        if k in lcms:
            lcms[k] = max(lcms[k], v)
        else:
            lcms[k] = v

ans = 0
for fs in factors:
    a = 1
    for k,v in lcms.items():
        a *= pow(k, v - fs[k], MOD)
        a %= MOD
    ans += a
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
M = 10**9+7
n = int(input())
a = tuple(map(int, input().split()))

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

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


a_lcm = lcm(*a)
ans = 0

for i in range(n):
    ans += (a_lcm // a[i])
    ans %= M

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

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 reduce(lcm_base, numbers, 1)

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

lcm_A = lcm_list(A)

for item in A:
    B+=(lcm_A//item)

print(B%div)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):    #求最大公约数
    if b==0:
        return a
    else:
        return gcd(b,a%b)
a=[]
n=int(input())
mod=1000000007
ans=0
sum=0
s=input().split(" ")
for i in range(0, n):
    k=int(s[i])
    if i==0:
        ans=k
    else:
        u=ans
        ans = ((u * k) // gcd(u, k))
#print(ans)
for i in range(0, n):
    sum=(sum+ans//(int(s[i])))%mod
print(sum)

Submission status: Time Limit Exceeded

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

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

n = int(input())
a = list(map(int, input().split()))
l = 1
for ai in a:
    l = lcm(l, ai)

ans = 0
mod = 10**9 + 7
for ai in a:
    ans += l // ai
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


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


# def power(x, y):
#     if y == 0:
#         return 1
#     elif y == 1:
#         return x % MOD
#     elif y % 2 == 0:
#         return power(x, y//2)**2 % MOD
#     else:
#         return power(x, y//2)**2 * x % MOD


# def div(a, b):
#     return (a * power(b, MOD-2)) % MOD


def LCM(a, b):
    return a*b//GCD(a, b)
    # return div(power(a, b), GCD(a, b))


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

    # 最小公倍数
    lcm = 1
    for a in A:
        lcm = LCM(lcm, a)
    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:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N=int(input())
a=list(map(int,input().split()))
calc=(lcm(a))  # 実行結果: 12

ans=0
for item in a:
    ans+=(calc)//item
    ans%=(10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
import sys
input = sys.stdin.readline
MOD = 10**9+7

n = int(input())
A = list(map(int, input().split()))
B = set(A)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
As = list(map(int, input().split()))
# def gcd(n, m):
#     # 最大公約数
#     a = max(n,m)
#     b = min(n,m)
#     while b:
#         a, b = b, a % b
#     return a

lcm = 1

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

mod = 10**9+7
ans = 0
ans = sum([(lcm//a)%mod for a in As])
print(ans%mod)

Submission status: Time Limit Exceeded

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

import numpy as np

def gcd(x: int, y: int):
  while(y!=0):
    tmp = x%y
    x = y
    y = tmp
  #if (y == 0):
  #  return x
  #else:
  #  return gcd(y, x%y)
  return x

g = 1
for i in range(N):
  g = g * A[i] // gcd(g, A[i])
an = 0
MOD = 10**9+7

for x in A:
  #print(g,g//x)
  an += g//x
  an %= MOD

print(an)

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  from fractions import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  N = int(input())
  A = tuple(map(int,input().split()))
  MOD = 10**9+7
  
  L = 1
  for a in A:
    L = lcm(a,L)
  ans = 0
  for a in A:
    ans += L//a
  print(ans%MOD)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:



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

mod=10**9+7

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


lcm=a[0]

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



sm=0

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

print(sm)

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
from functools import reduce

input = sys.stdin.readline

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


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

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

def lcm_list(numbers):
    return reduce(lcm, numbers)

index = lcm_list(list(set(A)))

MOD = 10**9 + 7

ans = 0

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

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys,fractions
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

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

u = 10**9+7

from functools import reduce

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

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

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

gcd = gcd_list(l)
L = [l[i]//gcd for i in range(N)]
lcm = lcm_list(L)

# print(lcm,gcd,'aaa')
ANS = 0
for i in range(N):
    elm = L[i]
    ANS += (lcm//elm)
    ANS %= u
print(ANS)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
import fractions
n = int(input())
a = list(map(int, input().split()))
ans = a[0]
dict_data = {}
for i in range(1, n):
    if a[i] not in dict_data:
        dict_data[a[i]] = 1 
        ans = ans * a[i] // fractions.gcd(ans, a[i])
total = 0
for i in range(0, n):
    b = ans // a[i]
    total += b % (10**9 + 7)
print(total % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

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

ans = 0
for i in range(n):
	ans += (num//a[i]) % 1000000007
	if ans > 1000000007:
		ans = ans%1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
def main():
  n=int(input())
  a=list(map(int,input().split()))
  a1=a[0]
  for i in a:
    a1=(i*a1)//fractions.gcd(i,a1)
  x=[a1//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys #追加                                                                                                                          
sys.setrecursionlimit(500*500)

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return int(x)

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

LCM = lcm(A)

ans = 0
for a in A:
    ans += LCM//a
    ans %= 1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
M = 10**9+7
n = int(input())
a = tuple(map(int, input().split()))

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

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


a_lcm = lcm(*a)
ans = 0

for i in range(n):
    ans += (a_lcm // a[i])%M
    ans %= M

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7
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()))
fact = [1]*(N+1)
rfact = [1]*(10**7)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % mod
rfact[N] = r = pow(fact[N], mod-2, mod)
value = lcm_list(A)
ans = 0
for i in range(N):
    ans += value//A[i]
    #ans += value*rfact[A[i]]
    #print(value,A[i],mod)
    #ans += (value*rfact[A[i]])%mod
    #print(value,A[i],rfact[A[i]],mod)
print(ans%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()))
A.sort(reverse=True)

lcm = A[0]

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

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())
t = list(map(int, input().split()))
l=[]
ans = t[0]
for i in range(1, n):
    ans = ans * t[i] // fractions.gcd(ans, t[i])
for j in range(n):
    l.append(ans//t[j])
print(sum(l)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

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 reduce(lcm_base, numbers, 1)

N = int(input())
A = list(map(int,input().split()))
B = []
div = 10**9+7

lcm_A = lcm_list(A)

for item in A:
    B.append(lcm_A//item)

print(sum(B)%div)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math

def gcd(a, b):
    if (a < b) :
        tmp = a
        a = b
        b = tmp
        
    r = a % b
    while (r != 0) :
        a = b
        b = r
        r = a % b
    return int(b)

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




N = int(input())

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



koubai = int(1)
for i in range(N):
    koubai = int(lcm(koubai, A[i]))

ans = int(0)
for i in range(N):
    ans += int(koubai // int(A[i]))
    ans %= int(1000000007)

print(ans)