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

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
mod =M
import sys
sys.setrecursionlimit(pow(10, 8))

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-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

from collections import defaultdict
N=input()
xs = map(int, input().split())
ys = []
d = defaultdict(int)
for x in xs:
    ps = prime_decomposition(x)
    psd = defaultdict(int)
    for p, c in ps:
        psd[p] = c
        d[p] = max(d[p], c)
    ys.append(psd)
r = 0
for ps in ys:
    t = 1
    for p in d:
        t = t*power(p,d[p]-ps[p])
    r = (r+t)
print(r%M)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
    return gcd(b,a%b) if b else a
def lcm(a,b):
    return a*b//gcd(a,b)
k=1
for i in range(n):
    k = lcm(k,a[i])
ans=0
for i in range(n):
    ans += k//a[i]
    ans %= 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
    return gcd(b,a%b) if b else a
def lcm(a,b):
    return a*b//gcd(a,b)
k=1
for i in a:
    k = lcm(k,i)
ans=0
for i in a:
    ans += k//i
    ans %= 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst1 = list(map(int,input().split()))
mod = 10**9+7

import fractions as math
#リスト l の最大公約数
def lcmlist(l):
    a = l[0]
    for i in range(len(l)):
        #change
        a = (a*l[i]) //math.gcd(a,l[i])
    return a

g = lcmlist(lst1)
ans = 0
for i in range(n):
    ans += g//lst1[i]%mod

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from functools import reduce

input = sys.stdin.readline

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = Counter()
    if n < 2:
        return result
    while n % 2 == 0:
        result[2] += 1
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n //= p
            result[p] += 1
        p += 2
    if n > 1:
        result[n] += 1
    return result

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = reduce(lambda x,y: x | y, [prime_factorization(a) for a in A])
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD); L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst1 = list(map(int,input().split()))
mod = 10**9+7

import fractions as math
#リスト l の最大公約数
def lcmlist(l):
    a = l[0]
    for i in range(len(l)):
        a = (a*l[i]) //math.gcd(a,l[i])
    return a

g = lcmlist(lst1)
ans = 0
for i in range(n):
    ans += g//lst1[i]%mod

print(ans%mod)

Submission status: Time Limit Exceeded

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

MOD=10**9+7
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)

LCM=A[:]
num=N
while num>1:
    for i in range(1,num,2):
        LCM[i//2]=lcm(LCM[i-1],LCM[i])
    if num&1:
        LCM[num//2]=LCM[num-1]
    num=(num+1)//2

ans=0
l=LCM[0]
for a in A:
    ans+=l*pow(a,MOD-2,MOD)
    ans%=MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from functools import reduce

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = Counter()
    if n < 2:
        return result
    while n % 2 == 0:
        result[2] += 1
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n //= p
            result[p] += 1
        p += 2
    if n > 1:
        result[n] += 1
    return result

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = reduce(lambda x,y: x | y, [prime_factorization(a) for a in A])
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD); L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

import fractions

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

output = 0
D =10**9+7
for i in range(N):
    output += X*pow(A[i],D-2,D)%D
    output = output % (10**9+7)
print(int(output))

Submission status: Time Limit Exceeded

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

import fractions

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

output = 0
D =10**9+7
for i in range(N):
    output += X*pow(A[i],D-2,D)%D
    output = output % (10**9+7)
print(int(output))

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


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

c = lcm_list(a)

b = 0

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys
input = sys.stdin.readline

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

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

b = [cnt // a[i] for i in range(n)]
print(sum(b) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

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

    result = 0
    for e in a:
        result += lcm_of_all_a * inverse(e, mode) % mode
        result %= mode
    return result


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

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

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

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

output = 0
for i in range(N):
    output += X*pow(A[i],10**9+5,10**9+7)%(10**9+7)
    output = output % (10**9+7)
print(output)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7

n=int(input())

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

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

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

lcma=1

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

ans=0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
t=1
for i in a:
  t=t/gcd(t,i)*i
ans=0
MOD=1000000007
for i in a:
  ans+=t//i
  ans%=MOD
print(int(ans+0.0000001))

Submission status: Time Limit Exceeded

Solution code:
import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

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

    result = 0
    for e in a:
        result += lcm_of_all_a * inverse(e, mode) % mode
        result %= mode
    return result


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
import fractions
X = A[0]
for i in range(1, N):
    X = X // fractions.gcd(X, A[i]) * A[i]

output = 0
for i in range(N):
    output += X*pow(A[i],10**9+5,10**9+7)%(10**9+7)
    output = output % (10**9+7)
print(output)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # tmp = lcm(*a)
    mod=pow(10,9) + 7
    m=0
    ans=0
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = (tmp*a[i]) // fractions.gcd(tmp,a[i])
    
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m%mod
    ans = ans % mod
    print(ans)


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7

n=int(input())

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

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

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

lcma=1

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

ans=0

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

print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
import fractions



def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

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

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

    print(ans % MOD)



    
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
lst1 = list(map(int,input().split()))
mod = 10**9+7
 
def GCD(a,b):
    if b == 0:
        return a
    else:
        return GCD(b,a%b)
def LCM(a,b):
    return (a//GCD(a,b)*b)

l = 1
for i in lst1:
    l = LCM(l,i)

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

Submission status: Time Limit Exceeded

Solution code:
import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # tmp = lcm(*a)
    mod=pow(10,9) + 7
    m=0
    ans=0
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = (tmp*a[i]) // fractions.gcd(tmp,a[i])
    
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m
    ans = ans % mod
    print(ans)


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # tmp = lcm(*a)
    mod=10**9 + 7
    m=0
    ans=0
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = (tmp*a[i]) // fractions.gcd(tmp,a[i])
    
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m
    ans = ans % mod
    print(ans)


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

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

    result = 0
    for e in a:
        result += lcm_of_all_a * inverse(e, mode)
        result %= mode
    return result


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

Solution code:
def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    return gcd(d,s%d) if d else s
  for i in l:
    f=i*f//gcd(i,f)
  ans=sum([f//x%mod for x in l])%mod
  print(ans)
  
if __name__=="__main__":s()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import  fractions
from functools import reduce
import sys
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # tmp = lcm(*a)
    mod=10**9 + 7
    m=0
    ans=0
    tmp = a[0]
    for i in range(1,len(a)):
        tmp = (tmp*a[i]) // fractions.gcd(tmp,a[i])
    
    for i,v in enumerate(a):
        m=tmp//v
        ans+=m%mod
    ans = ans % mod
    print(ans)


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
lcm = dict()
mod = 10**9+7
for a in A:
    n = 2
    while a != 1:
        c = 0
        while a % n == 0:
            a //= n
            c += 1
        if not n in lcm:
            lcm[n] = 0
        lcm[n] = max(lcm[n], c)
        n += 1
l = 1
for n in lcm.keys():
    l *= pow(n, lcm[n], mod)
    n %= mod
ans = 0
for a in A:
    p = pow(a, mod-2, mod)
    ans += (l*p)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

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

n=max(A)

#is_prime[i]にはi-1画素数か否かを示すboolが入る，[0]に1の素数判定がある．
is_prime = [True]*(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 for i in range(1, n+1) if is_prime[i-1]]
#print(table)

lcm=[0]*len(table)
p=[1]*len(table)



for i in range(N):
    a=A[i]
    for j in range(len(table)):
        if a<table[j]:
            break
        if a%p[j]==0:
            a=a//p[j]
            while a%table[j]==0:
                a=a//table[j]
                lcm[j]+=1
                p[j]*=table[j]
                
        
l=1
for j in range(len(table)):
    l*=p[j]
    

ans=0
mod=10**9+7

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

Submission status: Time Limit Exceeded

Solution code:
import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7
    lcm_of_all_a = functools.reduce(lambda x, y: lcm(x, y), a, 1)

    result = 0
    for e in a:
        result += lcm_of_all_a * inverse(e, mode)
        result %= mode
    return result


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Time Limit Exceeded

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

def main():

    n=int(input())
    a = [int(x) for x in input().split()]
    ans = 1

    mmm=10**9+7
    for i in a:
        ans = (ans *i )// fractions.gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = 1

    mmm=10**9+7
    for i in a:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

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]
for i in range(1,n):
  lcm = lcm*a[i] // gcd(lcm,a[i])
mod=pow(10,9)+7
ans=0
for x in a:
  ans+=lcm//x
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#a, b = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mod = (10 ** 9) + 7


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

p = lcm(A)
#print (p)

sum = 0
for i in range(N) :
  sum += p//A[i]

print (int(sum%mod))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
L = 1
def lcm(x,y):
    return x//gcd(x,y)*y
for a in A:
    L = lcm(L,a)
print(sum([L//a for a in A])%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7

N = INT()
A = LIST()

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

ans = 0
for x in A:
    ans = (ans+tmp//x)%mod
print(ans)

Submission status: Time Limit Exceeded

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

num = a[0]
for i in range(1, n):
	num = (num // fractions.gcd(num, a[i]))*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
import sys
input = sys.stdin.readline

def main():

    n=int(input())
    a = [int(x) for x in input().split()]
    ans = a[0]

    mmm=10**9+7
    for i in a[1:]:
        ans = (ans *i )// fractions.gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

n=max(A)

#is_prime[i]にはi-1画素数か否かを示すboolが入る，[0]に1の素数判定がある．
is_prime = [True]*(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 for i in range(1, n+1) if is_prime[i-1]]
#print(table)

lcm=[0]*len(table)
p=[1]*len(table)



for i in range(N):
    for j in range(len(table)):
        a=A[i]
        if a%p[j]==0:
            a=a//p[j]
            while a%table[j]==0:
                a=a//table[j]
                lcm[j]+=1
                p[j]*=table[j]
                
        
l=1
for j in range(len(table)):
    l*=p[j]
    

ans=0
mod=10**9+7

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7
    lcm_of_all_a = functools.reduce(lambda x, y: lcm(x, y), a, 1)
    b = map(lambda x: (lcm_of_all_a * inverse(x, mode)) % mode, a)
    return sum(b) % mode


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()

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

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
L = 1
def lcm(x,y):
    return x//gcd(x,y)*y
for a in A:
    L = lcm(L,a)
ans=0
for a in A: ans+=L//a
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import fractions
    import sys
    input = sys.stdin.readline
    n=int(input())
    a = [int(x) for x in input().split()]
    ans = a[0]

    mmm=10**9+7
    for i in a[1:]:
        ans = (ans *i )// fractions.gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

if __name__ == '__main__':
    main()

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):
        if tmp // A[i] != 0:
            tmp = lcm(tmp,A[i])

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

Submission status: Time Limit Exceeded

Solution code:
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m


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


N = int(input())
A = list(map(int, input().split()))
A.sort()
lcm_value = A[0]
for i in range(1, N):
    lcm_value = lcm(lcm_value, A[i])

# print(lcm_value)
mod = 10**9+7
ans = 0
for i in range(N):
    ans += (lcm_value // A[i]) % mod

print(ans % mod)

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()))
    ans = a[0]

    mmm=10**9+7
    for i in a[1:]:
        ans = (ans *i )// fractions.gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

def get_inv_t(N, P):
    inv_t = [0,1]
    for i in range(2,N+1):
         inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
    return inv_t

def lcm_mod(a, mod=-1):
    x = a[0]
    if mod == -1:
        for i in range(1, len(a)):
            x = (x * a[i]) // gcd(x, a[i])
    else:
        for i in range(1, len(a)):
            x *= (a[i] * inv_t[gcd(x, a[i])]) % P
    return x

_,a = [list(map(int, s.split())) for s in open(0)]

P = 10**9 + 7
N = max(a)

inv_t = get_inv_t(N, P)
lcm_ = lcm_mod(a, P)

ans = 0
for x in a:
    ans += int((lcm_*inv_t[x])%P)
print(int(ans%P))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys
input = sys.stdin.readline

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

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


b = [cnt // a[i] for i in range(n)]
print(sum(b)%(10**9+7))