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:
import math
import decimal
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

class Library():
    @staticmethod
    def Swap(a,b):
        return [b,a]

    @staticmethod
    def myRound(a,dig=0): # 四捨五入
        p = 10 ** dig
        return (a * p * 2 + 1) // 2 / p

    @staticmethod
    def Roundup(a,dig=0): # 切り上げ
        if a < 0:
            return int(a)
        else:
            return int(a + 0.9)

    @staticmethod
    def Gcd(a,b): #最大公約数
        if (a<b):
            a,b = Library.Swap(a,b)
        if (b==0):
            return a
        else:
            return Library.Gcd(b,a%b)

    @staticmethod
    def Lcm(a,b): #最小公倍数
        return a//Library.Gcd(a,b)*b

    @staticmethod
    def Divisors(a): # 約数列挙
        divisors = []
        for i in range(1,int(a**0.5)+1):
            if a%i==0:
                divisors.append(i)
                if i!=a//i:
                    divisors.append(a//i)
        divisors.sort()
        return divisors

class Prime():
    # コンストラクタ
    # エラストテネスの篩
    def __init__(self,num):
        self.num = num
        self.sieve = [0] * (self.num + 1)
        self.sieve[0] = -1
        self.sieve[1] = -1
        for i in range(2,self.num + 1):
            if self.sieve[i] == 0:
                self.sieve[i] = i
                for j in range(i * i,self.num + 1,i):
                    self.sieve[j] = i
    
    # 素数判定
    def isPrime(self,num = None):
        if num is None:
            num = self.num
        if self.sieve[num] == num:
            return True
        else:
            return False
    
    # 素数列挙
    def PrimeNum(self,num = None):
        if num is None:
            num = self.num
        prime = []
        for i in range(2,num):
            if self.sieve[i] == i:
                prime.append(i)
        return prime
    
    # 素因数分解
    def PrimeFact(self,num = None):
        if num is None:
            num = self.num
        fact = []
        while self.sieve[num] != num:
            fact.append(self.sieve[num])
            num //= self.sieve[num]
        fact.append(num)
        return fact

def main():
    n = int(input())
    a = list(map(int,input().split()))
    prime = []
    p = Prime(max(a))
    for i in range(n):
        _p = p.PrimeFact(a[i])
        mp = {}
        for x in _p:
            mp[x] = mp.get(x,0) + 1
        prime.append(mp)
    lcm = {}
    for x in prime:
        for y in x.keys():
            lcm[y] = max(lcm.get(y,0),x.get(y))
    x = 1
    for l in lcm:
        x *= l ** lcm[l]
    ans = 0
    for i in range(n):
        ans += x // a[i]
        ans %= mod
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd

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

    l = 1
    for num in num_list:
        l *= num // gcd(l, num)

    answer = 0
    for num in num_list:
        answer += l // num
        answer %= int(1e9 + 7)

    print(int(answer))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd

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

    l = 1
    for num in num_list:
        l *= num // gcd(l, num)

    answer = 0
    for num in num_list:
        answer += l // num
        answer %= 10 ** 9 + 7

    print(int(answer))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

B = []
for i in range(N):
    B.append(ans//a[i])

print(sum(B) % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


n = int(input())
A = list(map(int,input().split()))
num = 1
ans = 0
for i in A:
  num = i // gcd(i,num) * num

for i in A:
  ans += num//i
  ans %= 1000000007
  
print(int(ans))

Submission status: Time Limit Exceeded

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

n = int(input())
A = list(map(int,input().split()))
num = 1
ans = 0
for i in A:
  num = i // gcd(i,num) * num

for i in A:
  ans += num//i
  ans %= 1000000007
  
print(int(ans))

Submission status: Time Limit Exceeded

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

n = int(input())
A = list(map(int,input().split()))
num = 1
ans = 0
for i in A:
  num = i // gcd(i,num) * num

for i in A:
  ans += num//i
  ans %= 1000000007
  
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
sys.setrecursionlimit(100000)
def lcm(x,y):
    return x/fractions.gcd(x,y)*y

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
sys.setrecursionlimit(100000)
def lcm(x,y):
    return x/fractions.gcd(x,y)*y

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

ans = 0
for a in A:
  ans += (l//a) % 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()))

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

l = A[0]
for a in A:
  if l % a != 0:
    l = l * a // gcd(l, a)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
p = 10**9 + 7

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import numpy as np

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
for i in a:
    l = i * l // (gcd(i, l))

print((l // np.array(a)).sum() % mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9+7

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

n = inn()
a = inl()
#l = a[0]
#for i in range(1,n):
#    l = l*a[i]//gcd(l,a[i])
l = reduce(lcm_base,a,1)
sm = 0
for i in range(n):
    sm = (sm + l//a[i])%R
print(sm)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9+7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
l = a[0]
for i in range(1,n):
    l = l*a[i]//gcd(l,a[i])
sm = 0
for i in range(n):
    sm = (sm + l//a[i])%R
print(sm)

Submission status: Time Limit Exceeded

Solution code:
import sys,fractions
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9+7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
l = a[0]
for i in range(1,n):
    l = l*a[i]//fractions.gcd(l,a[i])
sm = 0
for i in range(n):
    sm = (sm + l//a[i])%R
print(sm)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def prime_decomposition(n):
    table = defaultdict(int)

    i = 2
    while n % i == 0:
        n //= i
        table[i] += 1

    i = 3
    while i * i <= n:
        while n % i == 0:
            n //= i
            table[i] += 1
        i += 2

    if n > 1:
        table[n] += 1

    return table


def main():
    mod = 10 ** 9 + 7

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

    lcm_d = defaultdict(int)
    pds = []
    for x in a:
        pd = prime_decomposition(x)
        pds.append(pd)
        for prime, power in pd.items():
            lcm_d[prime] = max(lcm_d[prime], power)

    ret = 0
    for pd in pds:
        curr = 1
        for prime, power in lcm_d.items():
            for _ in range(power - pd[prime]):
                curr = (curr * prime) % mod
        ret = (ret + curr) % mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd  # python<=3.4

MOD=1000000007

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

el = 1
for ai in a:
  g = gcd(el,ai)
  el = el // g * ai

sum = 0
for ai in a:
  sum += el // ai

sum %= MOD
print(sum)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd  # python<=3.4

MOD=1000000007

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

el = 1
for ai in a:
  g = gcd(el,ai)
  el = el // g * ai

sum = 0
for ai in a:
    sum = (sum + el // ai) % MOD

print(sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def primes(n):
  primes = {}
  i = 2
  while n >= i ** 2:
    if n % i == 0:
      primes[i] = primes.get(i, 0) + 1
      n //= i
    else:
      i += 2 - (i + 1) % 2
  if n > 1: primes[n] = primes.get(n, 0) + 1

  return primes

A = list(map(lambda x: primes(int(x)), input().split()))
p = 10**9 + 7


lcm = {}
for a in A:
  for k, v in a.items():
    lcm[k] = max(lcm.get(k, 0), a[k])

ans = 0
for a in A:
  t = 1
  for k, v in lcm.items():
    t = t * k ** (v - a.get(k, 0)) % p
  ans = (ans + t) % p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,sys
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
input = stdin.readline
lili=lambda:list(map(int,sys.stdin.readlines()))
li = lambda:list(map(int,input().split()))
#for deque append(),pop(),appendleft(),popleft(),count()
I=lambda:int(input())
S=lambda:input().strip()
mod = 1000000007
MAX = 10000003
mod = 1000000007
prime = [0 for i in range(MAX)] 
max_map = dict() 
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 

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 

def lcmModuloM(arr, n): 
	for i in range(n): 
		num = arr[i] 
		temp = dict() 
		while num > 1:  
			factor = prime[num]
			if factor in temp.keys(): 
				temp[factor] += 1
			else: 
				temp[factor] = 1 
			num = num // factor
		for i in temp: 
			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: 
		ans = (ans * power(i, max_map[i])) % mod 
	return (int(ans)) 


def modInverse(a, m) :
    g = gcd(a, m)
    if (g != 1) :
        return(-1)
    else:
        return(powe(a, m - 2, m)) 
def powe(x, y, m) : 
	if (y == 0) : 
		return 1
	p = powe(x, y // 2, m) % m 
	p = (p * p) % m 

	if(y % 2 == 0) : 
		return p 
	else : 
		return ((x * p) % m) 
def gcd(a, b) : 
	if (a == 0) : 
		return b 
		
	return gcd(b % a, a)
	
n=I()
a=li()
sieve()
lcm=lcmModuloM(a,n)
lcm=lcm%mod
#print(lcm)
ans=0
for i in a:
    k=(modInverse(i,mod))%mod
    #print(k)
    ans+=((lcm%mod)*k)%mod
    ans=ans%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,sys
from collections import Counter, defaultdict, deque
from sys import stdin, stdout
input = stdin.readline
lili=lambda:list(map(int,sys.stdin.readlines()))
li = lambda:list(map(int,input().split()))
#for deque append(),pop(),appendleft(),popleft(),count()
I=lambda:int(input())
S=lambda:input().strip()
mod = 1000000007
MAX = 10000003
mod = 1000000007
prime = [0 for i in range(MAX)] 
max_map = dict() 
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 

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 

def lcmModuloM(arr, n): 
	for i in range(n): 
		num = arr[i] 
		temp = dict() 
		while num > 1:  
			factor = prime[num]
			if factor in temp.keys(): 
				temp[factor] += 1
			else: 
				temp[factor] = 1 
			num = num // factor
		for i in temp: 
			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: 
		ans = (ans * power(i, max_map[i])) % mod 
	return (int(ans)) 


def modInverse(a, m) :
    g = gcd(a, m)
    if (g != 1) :
        return(-1)
    else:
        return(powe(a, m - 2, m)) 
def powe(x, y, m) : 
	if (y == 0) : 
		return 1
	p = powe(x, y // 2, m) % m 
	p = (p * p) % m 

	if(y % 2 == 0) : 
		return p 
	else : 
		return ((x * p) % m) 
def gcd(a, b) : 
	if (a == 0) : 
		return b 
		
	return gcd(b % a, a)
	
n=I()
a=li()
sieve()
lcm=lcmModuloM(a,n)
lcm=lcm%mod
#print(lcm)
ans=0
for i in a:
    k=(modInverse(i,mod))%mod
    #print(k)
    ans+=((lcm%mod)*k)%mod
    ans=ans%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
p = 10**9 + 7

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

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

print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9+7

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

primes = sieve(10**6)

def primeFactorization(n):
    ans = [0 for _ in range(len(primes))]
    temp = n
    for i in range(len(primes)):
        while temp%primes[i] == 0:
            ans[i] += 1
            temp /= primes[i]
    return ans

AFactorized = list(map(primeFactorization, A))
# print(AFactorized)

lcm = [0 for _ in range(len(primes))]
for i in range(len(primes)):
    for j in AFactorized:
        lcm[i] = max(lcm[i], j[i])

# print(lcm)

lcm_val = 1
for i in range(len(primes)):
    lcm_val *= pow(primes[i], lcm[i], mod)

# print(lcm_val)
ans = 0
for a in A:
    ans += lcm_val * pow(a, mod-2, mod)
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

lm = A[0]
for a in A[1:]:
    lm = lcm(lm, a)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

ans = 0

for a in A:
    ans += ( lm//a )
    ans %= Mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)
    g = A[0]
    for v in A:
        tmp = gcd(g, v)
        g = g * v // tmp
    ret = 0
    for v in A:
        ret += g // v
        ret %= MOD
    print(ret)
    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:
import fractions
import sys
input = sys.stdin.readline
def lcm(X,Y):
    x=X
    y=Y
    if y>x:
        x,y=y,x
    while x%y!=0:
        x,y=y,x%y
    return X*Y//y
N = int(input())
a = tuple(map(int,input().split()))
g = 1
res = 0
MOD = 10**9+7
for elem in a:
    g = lcm(g,elem)
res = sum((g//elem for elem in a))
print(res%MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
MOD = 10**9+7
for elem in a:
    g *= elem//fractions.gcd(g,elem)
res = sum((g//elem for elem in a))
print(res%MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = tuple(map(int,input().split()))
g = 1
MOD = 10**9+7
for elem in a:
    g *= elem//fractions.gcd(g,elem)
res = 0
for elem in a:
    res += g//elem
print(res%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000100)

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

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

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

if N == 1:
    lcmAll = A[0]
else:
    lcmAll = lcm(A[0], A[1])
    if N > 2:
        for i in range(2, N):
            lcmAll = lcm(lcmAll, A[i])

BIG_PRIME = 1000000007
ans = 0
for i in range(N):
    d = lcmAll // A[i]
    d %= BIG_PRIME
    ans += d
    ans %= BIG_PRIME

print(str(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()))
g = 1
MOD = 10**9+7
for elem in a:
    g *= elem//fractions.gcd(g,elem)
res = sum([g//elem for elem in a])
print(res%MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
MOD = 10**9+7
for elem in a:
    g *= elem//fractions.gcd(g,elem)
res = 0
for elem in a:
    res += g//elem
print(res%MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def solve():
    MOD = 10**9 + 7
    maxA = 10**6

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

    isPrimes = [False]*2 + [True]*(maxA-1)
    minFs = [1] * (maxA+1)
    for i in range(2, int(maxA**0.5) + 1):
        if isPrimes[i]:
            for x in range(i*i, maxA+1, i):
                isPrimes[x] = False
                minFs[x] = i

    def getPrimeFactors(x):
        anss = []
        while minFs[x] > 1:
            anss.append(minFs[x])
            x //= minFs[x]
        if x != 1:
            anss.append(x)
        return anss

    PFss = []
    Primes = set()
    for A in As:
        PFs = getPrimeFactors(A)
        cnt = Counter(PFs)
        PFss.append(cnt)
        Primes |= cnt.keys()

    cntP = Counter()
    for PFs in PFss:
        for key, num in PFs.items():
            cntP[key] = max(cntP[key], num)

    lcmA = 1
    for key, num in cntP.items():
        lcmA *= pow(key, num, MOD)
        lcmA %= MOD

    def getInvs(n, MOD):
        invs = [1] * (n+1)
        for x in range(2, n+1):
            invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
        return invs

    invs = getInvs(10**6, MOD)

    ans = 0
    for A in As:
        ans += lcmA * invs[A]
        ans %= MOD

    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
import math
import decimal
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

class Library():
    @staticmethod
    def Swap(a,b):
        return [b,a]

    @staticmethod
    def myRound(a,dig=0): # 四捨五入
        p = 10 ** dig
        return (a * p * 2 + 1) // 2 / p

    @staticmethod
    def Roundup(a,dig=0): # 切り上げ
        if a < 0:
            return int(a)
        else:
            return int(a + 0.9)

    @staticmethod
    def Gcd(a,b): #最大公約数
        if (a<b):
            a,b = Library.Swap(a,b)
        if (b==0):
            return a
        else:
            return Library.Gcd(b,a%b)

    @staticmethod
    def Lcm(a,b): #最小公倍数
        return a//Library.Gcd(a,b)*b

    @staticmethod
    def Divisors(a): # 約数列挙
        divisors = []
        for i in range(1,int(a**0.5)+1):
            if a%i==0:
                divisors.append(i)
                if i!=a//i:
                    divisors.append(a//i)
        divisors.sort()
        return divisors

class Prime():
    # コンストラクタ
    # エラストテネスの篩
    def __init__(self,num):
        self.num = num
        self.sieve = [0 for i in range(self.num + 1)]
        self.sieve[0] = -1
        self.sieve[1] = -1
        for i in range(2,self.num + 1):
            if self.sieve[i] == 0:
                self.sieve[i] = i
                for j in range(i + i,self.num + 1,i):
                    self.sieve[j] = i
    
    # 素数判定
    def isPrime(self,num = None):
        if num is None:
            num = self.num
        if self.sieve[num] == num:
            return True
        else:
            return False
    
    # 素数列挙
    def PrimeNum(self,num = None):
        if num is None:
            num = self.num
        prime = []
        for i in range(2,num):
            if self.sieve[i] == i:
                prime.append(i)
        return prime
    
    # 素因数分解
    def PrimeFact(self,num = None):
        if num is None:
            num = self.num
        fact = []
        while self.sieve[num] != num:
            fact.append(self.sieve[num])
            num //= self.sieve[num]
        fact.append(num)
        return fact

def main():
    n = int(input())
    a = list(map(int,input().split()))
    time1 = time.time()
    prime = []
    p = Prime(max(a))
    for i in range(n):
        _p = p.PrimeFact(a[i])
        mp = {}
        for x in _p:
            if x in mp.keys():
                mp[x] += 1
            else:
                mp[x] = 1
        prime.append(mp)
    lcm = {}
    for x in prime:
        for y in x.keys():
            if y in lcm.keys():
                lcm[y] = max(lcm[y],x[y])
            else:
                lcm[y] = x[y]
    b = []
    for x in prime:
        num = 1
        for y in lcm.keys():
            if y in x.keys():
                num *= y ** (lcm[y] - x[y])
                num %= mod
            else:
                num *= y ** lcm[y]
                num %= mod
        b.append(num)
    ans = 0
    for i in range(n):
        ans += b[i]
        ans %= mod
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import decimal
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

class Library():
    @staticmethod
    def Swap(a,b):
        return [b,a]

    @staticmethod
    def myRound(a,dig=0): # 四捨五入
        p = 10 ** dig
        return (a * p * 2 + 1) // 2 / p

    @staticmethod
    def Roundup(a,dig=0): # 切り上げ
        if a < 0:
            return int(a)
        else:
            return int(a + 0.9)

    @staticmethod
    def Gcd(a,b): #最大公約数
        if (a<b):
            a,b = Library.Swap(a,b)
        if (b==0):
            return a
        else:
            return Library.Gcd(b,a%b)

    @staticmethod
    def Lcm(a,b): #最小公倍数
        return a//Library.Gcd(a,b)*b

    @staticmethod
    def Divisors(a): # 約数列挙
        divisors = []
        for i in range(1,int(a**0.5)+1):
            if a%i==0:
                divisors.append(i)
                if i!=a//i:
                    divisors.append(a//i)
        divisors.sort()
        return divisors

class Prime():
    # コンストラクタ
    # エラストテネスの篩
    def __init__(self,num):
        self.num = num
        self.sieve = [0 for i in range(self.num + 1)]
        self.sieve[0] = -1
        self.sieve[1] = -1
        for i in range(2,self.num + 1):
            if self.sieve[i] == 0:
                self.sieve[i] = i
                for j in range(i + i,self.num + 1,i):
                    self.sieve[j] = i
    
    # 素数判定
    def isPrime(self,num = None):
        if num is None:
            num = self.num
        if self.sieve[num] == num:
            return True
        else:
            return False
    
    # 素数列挙
    def PrimeNum(self,num = None):
        if num is None:
            num = self.num
        prime = []
        for i in range(2,num):
            if self.sieve[i] == i:
                prime.append(i)
        return prime
    
    # 素因数分解
    def PrimeFact(self,num = None):
        if num is None:
            num = self.num
        fact = []
        while self.sieve[num] != num:
            fact.append(self.sieve[num])
            num //= self.sieve[num]
        fact.append(num)
        return fact

def main():
    n = int(input())
    a = list(map(int,input().split()))
    time1 = time.time()
    prime = []
    for i in range(n):
        p = Prime(a[i])
        _p = p.PrimeFact()
        mp = {}
        for x in _p:
            if x in mp.keys():
                mp[x] += 1
            else:
                mp[x] = 1
        prime.append(mp)
    lcm = {}
    for x in prime:
        for y in x.keys():
            if y in lcm.keys():
                lcm[y] = max(lcm[y],x[y])
            else:
                lcm[y] = x[y]
    b = []
    for x in prime:
        num = 1
        for y in lcm.keys():
            if y in x.keys():
                num *= y ** (lcm[y] - x[y])
                num %= mod
            else:
                num *= y ** lcm[y]
                num %= mod
        b.append(num)
    ans = 0
    for i in range(n):
        ans += b[i]
        ans %= mod
    print(ans)
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

ans = 0

for a in A:
    ans += ( lm//a )
    ans %= Mod

print(ans)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

n = input()
arr = list(map(int, input().split()))
tmp = arr[0]
for i in arr:
    tmp = tmp*i//gcd(tmp,i)
ans = sum(tmp//a for a in arr)
ans = ans % (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7


def gcd(a: int, b: int) -> int:
    while b != 0:
        a, b = b, a - (a // b) * b

    return a


def lcm(iterable):
    a = iterable[0]

    for b in iterable:
        a = a * b // gcd(a, b)

    return a


def inv_mod(x: int):
    return pow(x, MOD - 2)


def pow(x: int, n: int) -> int:
    res = 1
    while n > 0:
        if n & 1 == 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1

    return res


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

    lcm_an = lcm(an)

    ans = 0
    for a in an:
        ans = (ans + lcm_an * inv_mod(a)) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7


def gcd(a, b):
    while b != 0:
        a, b = b, a - (a // b) * b

    return a


def lcm(iterable):
    a = iterable[0]

    for b in iterable:
        a = a * b // gcd(a, b)

    return a


def inv_mod(x):
    return pow(x, MOD - 2)


def pow(x, n):
    res = 1
    while n > 0:
        if n & 1 == 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1

    return res


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

    lcm_an = lcm(an)

    ans = 0
    for a in an:
        ans = (ans + lcm_an * inv_mod(a)) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools

MOD = int(1e9) + 7


def lcm(a, b):
    c, d = a, b
    while d != 0:
        c, d = d, c % d
    return a // c * b


class Inv:

    @classmethod
    def pow(cls, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % MOD
            x = x * x % MOD
            n >>= 1
        return ret

    @classmethod
    def inv(cls, x: int) -> int:
        return cls.pow(x, MOD - 2)


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

v = functools.reduce(lcm, A)
ans = 0
for a in A:
    ans = (ans + v // a) % MOD
print(ans)

Submission status: Time Limit Exceeded

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

def lcm(x, y):
    return (x * y) // gcd(x, y)
def main():
    n = int(sys.stdin.readline())
    a = list(map(int,input().split()))
    
    l = a[0]
    for i in range(n):
        l = lcm(l, a[i])
    sum = 0
    for i in range(n):
        sum += l // a[i]
    print(sum % 1000000007)
main()

Submission status: Time Limit Exceeded

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

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

def lcm(x, y):
    return (x * y) // gcd(x, y)
l = a[0]
for i in range(n):
    l = lcm(l, a[i])
sum = 0
for i in range(n):
    sum += l // a[i]
print(sum % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

def lcm(x, y):
    return (x * y) // gcd(x, y)
l = a[0]
for i in range(n):
    if i == 0:
        continue
    l = lcm(l, a[i])
sum = 0
for i in range(n):
    sum += l // a[i]
    sum %= 1000000007
print(sum)