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:
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i,b in enumerate(a):
        if i==0: pass
        x = (x * b) // gcd(x, b)
    return x

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

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(sorted(list(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:
import fractions
def main():
  _=int(input())
  a=list(map(int,input().split()))
  a1=a[0]
  fgcd=fractions.gcd
  for i in a:
    a1=(i*a1)//fgcd(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:

from math import *

def gcd(x, y): 

	while(y): 
		x, y = y, x % y 

	return x

mod=10**9+7

n=int(raw_input())
a=list(map(int,raw_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:
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 = [int(n) for n in input().split()]
#s=input().split(" ")
for i in range(0, n):
    k=s[i]
    if i==0:
        ans=k
    else:
        u=ans
        ans = ((u * k) // gcd(u, k))
for i in range(0, n):
    sum=(sum+ans//(int(s[i])))%mod
print(sum)

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 extGCD(a, b):
    """
    拡張ユークリッド互除法により
    ax + by = gcd(a, b)となるようなx, yを求める
    """
    # print(a, b)
    if a == 0:
        return 0, 1
    s, t = extGCD(b % a, a)
    return t-(b//a)*s, s


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


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

    # 最小公倍数
    lcm = 1
    for a in A:
        lcm = LCM(lcm, a)
    ma = [modinv(a, MOD) for a in A]

    tot = 0
    for a in ma:
        tot += lcm * a
        tot %= MOD
    print(tot)

    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

l = int(l)
MOD = 1000000007

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

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    for xx in range(1000001):
        a,b=b,a%b
        if b==0:
            break
    return a

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

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:
from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
def lcm(a,b):
    return (a * b // gcd(a, b))
h = reduce(lcm, A)
B = [(h // A[i] % MOD) for i in range(N)]
print(sum(B) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b): 
    while (a != b): 
        if (a > b): 
            a = a - b 
        else: 
            b = b - a 
    return a 

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

LCM = arr[0]
MOD = 1000000007

for num in arr:
	LCM = (num*LCM)//(gcd(num, LCM))

# print(LCM)
s = 0


for num in arr:
	s = (s + ( LCM//num ))%MOD

print(s)

# 499998500001000000

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#E
n=int(input())
a=tuple(map(int,input().split()))
import fractions
def lcm1(a,b):
    return a*b//fractions.gcd(a,b)

def main():
    lcm=a[0]
    b_sum=0
    
    for i in range(1,n):
        lcm=lcm1(lcm,a[i])

    num=10**9+7
    for i in range(n):
        b_sum+=(lcm//a[i])%num

    print(b_sum%num)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
lcm = A[0]
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

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:
# cook your dish here
def gcd(a,b): 
    if a == 0: 
        return b 
    return gcd(b % a, a) 
def lcm(a,b): 
    return (a*b) // gcd(a,b) 
n=int(input())
a=list(map(int,input().strip().split()))[:n]
k=a[0]
for i in range(n):
    k=lcm(k,a[i])
ans=0
for i in range(n):
    ans=ans+k//a[i]
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math

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

B0 = A[0]
if N == 1:
    ans = 1
else:
    for a in A:
        B0 = (B0 * a) // fractions.gcd(B0,a)
    B = [B0//A[0]]
    for i in range(1,N):
        B.append(A[0]*B[0]//A[i])
    
    ans = 0
    for b in B:
        ans += b
        ans = ans % (10**9 + 7)

print(ans)

Submission status: Time Limit Exceeded

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


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

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

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


if __name__ == '__main__':
    main()

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)

ans = 0

for i in inp_list:
    ans += lcm // i
    if ans > (10**9+7):
        ans -= (10**9+7)


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

Submission status: Time Limit Exceeded

Solution code:
import fractions
n=int(input())
a = list(map(int, input().split()))
ans = a[0]

mmm=10**9+7
 

for i in range(1, len(a)):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
    
result=0
for item in a:
  temp=ans//item
  result=(result+temp)%mmm
 
print(result)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b): 
    if(b==0): 
        return a 
    else: 
        return gcd(b,a%b) 
n = int(input())
a = [int(i) for i in input().split()]

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

for i in range(n):
    gg = lcm // a[i]
    gg %= mod
    ans += gg
    ans %= 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=input()
hoge=list(map(int,input().split()))
tmp=lcm_list(hoge)
ans=0
mod=10**9+7
for i in hoge:
    ans+=tmp//i
    ans%=mod
ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import fractions
N = int(input())
A = [int(i) for i in input().split()]


C = collections.Counter(A)

mod = 10**9 + 7

lcm = 1
for a in C.keys():
    lcm = lcm*a//fractions.gcd(lcm, a)
# print(lcm)

ans = 0
for k, v in C.items():
    ans += lcm//k*v
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys

input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = [0] * n
sum_b = 0
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] / fractions.gcd(ans, a[i])
for i in range(n):
    b[i] = ans / a[i]
    sum_b += b[i]

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

Submission status: Time Limit Exceeded

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

MOD = 1000000000 + 7

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

GCD = {}


def gcd(x, y):
    if x < y:
        x, y = y, x

    if (x, y) in GCD:
        return GCD[(x, y)]

    if y == 0:
        return x
    else:
        res = gcd(y, x % y)
        GCD[(x, y)] = res
        return res


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


l = lcm(A[0], A[1])
ans = l // A[0] + l // A[1]

for i in range(2, N):
    new_l = lcm(l, A[i])
    ans *= new_l // l
    ans += new_l // A[i]
    ans %= MOD
    l = new_l

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

denom = int(1e9+7)

N = int(input())
A = [int(i) for i in input().split()]
A.sort()
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:
import fractions
def main():
    mod = 10**9 + 7
    N = int(input())
    A = [int(x) for x in input().split()]
    sub1 = 1 
    for i in A[:N//2]:
        sub1 = sub1 * i // fractions.gcd(sub1, i)
    sub2 = 1
    for i in A[N//2:]:
        sub2 = sub2 * i // fractions.gcd(sub2, i)
    sub = sub1*sub2 // fractions.gcd(sub1,sub2)
    ans = 0
    for i in range(N):
        ans += sub//A[i]
        ans %= mod
    print(ans%mod)
if __name__ == '__main__':
    main()

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()]
a.sort()
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:
from fractions import gcd
import sys 
input = sys.stdin.readline

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])%mod
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)
    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:
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())
arr = [int(i) for i in input().split()]
lcm = 1
for x in arr:
    lcm = _lcm(lcm, x)
s = 0
mod = int(1e9 + 7)
for x in arr:
    s += lcm // x
    s %= mod
print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
#リストの最小公倍数
def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort()
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) #B[0]
answer = x % MOD
B = np.array(A[1:])
answer += ((first * x // B) % MOD).sum()

print(answer%MOD)

Submission status: Time Limit Exceeded

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

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

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

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

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 
    if total > 10**9 + 7:
        total = total % (10**9 + 7)
print(total % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
def find_lcm(num1, num2): 
    if(num1>num2): 
        num = num1 
        den = num2 
    else: 
        num = num2 
        den = num1 
    rem = num % den 
    while(rem != 0): 
        num = den 
        den = rem 
        rem = num % den 
    gcd = den 
    lcm = (num1 * num2)/int(gcd) 
    return lcm
 
n = int(input())
l = list(map(int, input().split()))
lcm = 1 
  
for i in range(0, len(l)): 
    lcm = find_lcm(lcm, l[i])
 
ans = 0
 
for i in range(0, len(l)):
  ans += lcm / l[i]
 
print(int(ans % 1000000007))

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
MOD = 10**9+7
#-------------------------------------------------------------------
#gcd (最大公約数)(greatest common divisor)
#-------------------------------------------------------------------
# Python3.4以前なら、
from fractions import gcd
import fractions
from functools import reduce
#-------------------------------------------------------------------
#lcm (最小公倍数)
#-------------------------------------------------------------------
def lcm_base(a, b):
	return ((a * b) // gcd(a, b))

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

def lcm_list(nums):
	return lcm(*nums)
#-------------------------------------------------------------------

n = int(input())

A =        list( map(int, input().split()) )	# 1 2 3 4 5 ...

x = lcm_list(A)

ans=0
for a in A:
	b = x // a
	ans+=b
	ans = ans % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
def main():
  _=int(input())
  a=list(map(int,input().split()))
  a1=a[0]
  fgc=fractions.gcd
  for i in a:
    a1=(i*a1)//fgc(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:
from fractions import gcd
from functools import reduce

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

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


c = 1
for i in range(N):
    c = gcd(c, A[i])

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

l = int(l)
MOD = 1000000007

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

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

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




N = int(input())





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

Submission status: Time Limit Exceeded

Solution code:
import fractions


def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


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


mod = 10**9+7 #出力の制限


MAX = 10000003
  
prime = [0 for i in range(MAX)] 
  
max_map = dict() 
  
# function to return a^n 
def power(a, n): 
      
    if n == 0: 
        return 1
    p = power(a, n // 2) % mod 
    p = (p * p) % mod 
      
    if n & 1: 
        p = (p * a) % mod 
    return p 
  
# function to find the smallest prime 
# factors of numbers upto MAX 
def sieve(): 
    prime[0], prime[1] = 1, 1
    for i in range(2, MAX): 
        if prime[i] == 0: 
            for j in range(i * 2, MAX, i): 
                if prime[j] == 0: 
                    prime[j] = i 
            prime[i] = i 
  
# function to return the LCM modulo M 
def lcmModuloM(arr, n): 
      
    for i in range(n): 
        num = arr[i] 
          
        temp = dict() 
          
        # temp stores mapping of prime factors  
        # to its power for the current element 
        while num > 1: 
               
            # factor is the smallest prime 
            # factor of num 
            factor = prime[num] 
              
            # Increase count of factor in temp 
            if factor in temp.keys(): 
                temp[factor] += 1
            else: 
                temp[factor] = 1
                  
            # Reduce num by its prime factor 
            num = num // factor 
              
        for i in temp: 
            # store the higest power of every prime 
            # found till now in a new map max_map 
            if i in max_map.keys(): 
                max_map[i] = max(max_map[i], temp[i]) 
            else: 
                max_map[i] = temp[i] 
              
    ans = 1
      
    for i in max_map: 
          
        # LCM is product of primes to their 
        # higest powers modulo M 
        ans = (ans * power(i, max_map[i])) % mod 
    return ans 
  
# Driver code 
sieve() 
lc = lcmModuloM(a, N)

ans = 0
for i in range(N):
    ans += mod_inv(a[i],mod)

print((ans*lc%mod))

Submission status: Time Limit Exceeded

Solution code:

import sys,fractions
sys.setrecursionlimit(10**5)
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:
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
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)

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

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

Submission status: Time Limit Exceeded

Solution code:
import math
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()]
lc = A[0]
for i in range(1, N):
    lc = lcm(lc, A[i])

mod = 10 ** 9 + 7
s = 0
for i in range(N):
    s = (s + lc // A[i]) % mod

print(s)

Submission status: Time Limit Exceeded

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

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

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

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))
t = 10**9+7
for i in ln:
    r += k//A[i]
    if r > t:
        r %= t
print(r)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
    if x==0:
        return y
    return gcd(y%x,x)    
x=int(input())
a=list(map(int,input().split()))
k=a[0]

for i in range(1,x):
    k=(k*a[i])//gcd(k,a[i])
s=0
mod=10**9+7
for i in a:
    s=(s+(k//i))%mod
print(s%mod)

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)
        if a == 1:
            return 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:
from functools import reduce
from fractions import gcd

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

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

debug = False

if debug:
    n = 10000
    aaa = [ a*100+1 for a in range(n) ]
else:
    n = int(input())
    aaa = get_nums_l()

# g = reduce(gcd, aaa)
# x = reduce(lambda a,b:a*b, aaa)
g = lcm(aaa)

ans = 0
for a in aaa:
    ans = (ans + g//a) % (10**9+7)
print(ans % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from fractions import gcd
@lru_cache(maxsize=None)
def lcm(x, y):
    return (x // gcd(x, y)) * y
MOD = 10 ** 9 + 7  
n = int(input())
A = list(map(int, input().split()))
A.sort()
l = 1
for i in A:
  l = lcm(l, i)
  
B = [(l // i) % MOD for i in A]

ans = sum(B) % MOD

print(ans)

Submission status: Time Limit Exceeded

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

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:
def computeGCD(x, y):
   while(y):
       x, y = y, x % y
   return x


def main():
    n = int(input())
    a = list(map(int, input().split()))
    m = {}
    def lcm(x, y):
        if x > y:
             x, y = y, x
        key = (x, y)
        if key in m:
            return m[key]
        res = x * y // computeGCD(x, y)
        m[key] = res
        return res
 
    def rec(ls):
        if len(ls) == 1:
            return ls[0]
        elif len(ls) == 2:
            return lcm(ls[0], ls[1])
        return lcm(rec(ls[:len(ls) // 2]), rec(ls[len(ls) // 2:]))
    l = rec(a)
    ans = 0
    for i in range(n):
        ans += l // a[i]
        ans %= 10**9 + 7
    # print(m)
    print(ans)
if __name__ == "__main__":
    main()

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

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)

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:
N = int(input())
a = list(map(int, input().split()))
mod=10**9+7
import fractions
lcm_m = a[0]%mod
for i in range(1, N):
#    lcm_m = lcm_m * a[i] // fractions.gcd(lcm_m, a[i])
#    lcm_m = (lcm_m%(10^9+7))*(a[i]%(10^9+7))//(fractions.gcd(lcm_m,a[i])%(10^9+7))
#    lcm_m = (lcm_m%(10**9+7))*a[i]//(fractions.gcd(lcm_m%(10**9+7),a[i]))
#    lcm_m = ((lcm_m%mod)*(a[i]%mod))%mod//(fractions.gcd(lcm_m,a[i]))
    lcm_m = ((lcm_m)*(a[i]%mod))//(fractions.gcd(lcm_m,a[i]))
#print(lcm_m)

#sol = 0
#for i in range(N):
#    sol += lcm_m / a[i]
#print(int(sol)%(10**9+7))
sol=sum([lcm_m//x for x in a])
print(sol%mod)
#print(sol)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n = int(input())
  a = tuple(map(int, input().split()))
  ov = 10**9+7
  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
  l = lcm(a)
  b= [l//i%ov for i in a]
  print(sum(b)%ov)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

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

LCM = arr[0]
MOD = 1000000007

for num in arr:
	LCM = (num*LCM)//(gcd(num, LCM))

# print(LCM)
s = 0


for num in arr:
	s = (s + ( LCM//num ))%MOD

print(s)

# 499998500001000000

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
from fractions import gcd

if n==1:
    print(1)
else:
    g=A[0]
    l=A[0]
    for i in range(n-1):
        g=gcd(l,A[i+1])
        l*=(A[i+1]//g)
    ans=0
    for i in range(n):
        ans+=(l//A[i])%mod        
    print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
B = [i for i in range(N)]
MOD = 10 ** 9 + 7
def lcm(a,b):
    return a * b // gcd(a, b)
h = reduce(lcm, A)

for i in range(N):
    B[i] = (h // A[i] % MOD)

print(sum(B) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# abc152/abc152_e
import sys
from fractions import gcd
from functools import reduce

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

MOD = 10**9 + 7

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

def main():
    N = i2n()
    A = i2nn()
    A_lcm = int(reduce(lcm, A))
    res = 0
    for a in A:
        res = (res + A_lcm // a) % MOD
    print(res)
    return

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce

MOD = 10 ** 9 + 7

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

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

n, *a = map(int, sys.stdin.read().split())

def main():
    l = reduce(lcm, a, 1)
    res = 0
    for i in a:
        res += l // i % MOD
        res %= MOD
    return res
    
if __name__ == '__main__':
    ans = main()
    print(ans)