Problem:


Score : 500 points

Problem Statement

Given are N positive integers A_1,...,A_N.

Consider positive integers B_1, ..., B_N that satisfy the following condition.

Condition: For any i, j such that 1 \leq i < j \leq N, A_i B_i = A_j B_j holds.

Find the minimum possible value of B_1 + ... + B_N for such B_1,...,B_N.

Since the answer can be enormous, print the sum modulo (10^9 +7).

Constraints

1 \leq N \leq 10^4

1 \leq A_i \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the minimum possible value of B_1 + ... + B_N for B_1,...,B_N that satisfy the condition, modulo (10^9 +7).

Sample Input 1

3
2 3 4

Sample Output 1

13

Let B_1=6, B_2=4, and B_3=3, and the condition will be satisfied.

Sample Input 2

5
12 12 12 12 12

Sample Output 2

5

We can let all B_i be 1.

Sample Input 3

3
1000000 999999 999998

Sample Output 3

996989508

Print the sum modulo (10^9+7).



Sample input:
3
2 3 4


Sample output:
13

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

#https://qiita.com/maebaru/items/317af98e85e9f4db04f9
def prime_numbers(m):
    # 素数を保持するset
    primes = set()

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.add(n)
        n += 1

    return list(primes)
    
#https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8
def factorization(n,primes,primenum_count_for_lcm):
    temp = n
    for i in range(len(primes)):
        if temp%primes[i]==0:
            cnt=0
            while temp%primes[i]==0:
                cnt+=1
                temp //= primes[i]
            if primenum_count_for_lcm[i] < cnt:
                primenum_count_for_lcm[i] = cnt
        if temp < primes[i]:
            break

    if temp!=1:
        if 10**3<temp:
            primes.append(temp)
            primenum_count_for_lcm.append(1)
        else:    
            idx = primenum_count_for_lcm.index(temp)
            if primenum_count_for_lcm[idx] == 0:
                primenum_count_for_lcm[idx] = 1
            
    #if arr==[]:
    #    arr.append([n, 1])
    
    return primenum_count_for_lcm

primes = prime_numbers(int(10**6))
primes.sort()
primenum_count_for_lcm = [0]*len(primes)
for i in range(N):
    primenum_count_for_lcm = factorization(A[i],primes,primenum_count_for_lcm)

sugoilcm = 1
for i in range(len(primes)):
    sugoilcm *= primes[i]**primenum_count_for_lcm[i]

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000000+7
def lcm(x, y):
    import fractions
    return (x * y) // fractions.gcd(x, y)

n = int(input())
dat = list(map(int, input().split()))
dat.sort(reverse=True)
dat2 = []

base = 1
for i in range(len(dat)):
    base = lcm(base, dat[i])
res = 0

for i in range(len(dat)):
    res += base // dat[i]

print(res%MOD)

Submission status: Time Limit Exceeded

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

from fractions import gcd
from functools import reduce

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

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

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

l = lcm_list(arr)
solarr = [l//i for i in arr]
sol = 0
for i in solarr:
  sol += i
  sol %= mod
print(sol)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import numpy as np

n = int(input())
a = list(map(int, 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

a_lcm = lcm(a)
aa = np.array(a)
aa = a_lcm // aa
aa = aa.tolist()
ans = 0
for i, n in enumerate(aa):
    ans += n
    if i%100==0:
        ans %= 10**9+7

ans %= 10**9+7

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

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

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

    ans = 0
    mod = 10**9 + 7
    for i in a:
        ans += lcm // i
        ans %= mod
    print(ans)

main()

Submission status: Time Limit Exceeded

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

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

div = 10**9 + 7
lcm_num = lcm(a)
ans = 0

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

print(ans%div)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import time
n = int(input())
a = list(map(int, input().split()))
t1 = time.time()
mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
g = 1
flag = 1
for i in range(n):
    g = a[i] * g // gcd(a[i], g)
    #g %= mod
    t2 = time.time()
    if t2 - t1 > 0.5:
        flag = 0
        break

if flag == 1:
    ans = 0
    for i in range(n):
        ans += g * modinv(a[i])
        ans %= mod
    print(ans)

else:
    ans = 0

    for i in range(n):
        g = 1
        for j in range(n):
            if i == j:
                continue
            else:
                g *= a[j]
                g %= mod
        ans += g
        ans %= mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  MOD=10**9+7
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  ans=0
  import numpy as np
  A=np.array(A)
  ans=0
  for i in range(N):
    ans+=z//A[i]
  print(ans%MOD)
  
if __name__=='__main__':
  main()

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

cm = reduce(lambda a,b: a*b, aaa)

ans_0 = [ cm//a for a in aaa ] 
gcd_ = reduce(gcd, ans_0)

# gcd_ = reduce(gcd, aaa)
# x = [ a//gcd_ for a in aaa ]
# lcm_ = gcd_ * reduce(lambda a,b: a*b, x)
# lcm_ = (lcm(aaa))

ans = 0
for a in ans_0:
    ans = (ans + a//gcd_) % (10**9+7)
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 = list(map(int,input().split()))
    MOD = 10**9+7
    g1 = 1
    for t in a[:N//2]:
        g1 = divmod(g1*t,fractions.gcd(g1,t))[0]

    g2 = 1
    for t in a[N//2:]:
        g2 = divmod(g2*t,fractions.gcd(g2,t))[0]
    res = 0
    g = fractions.gcd(g1,g2)

    r1 = (g2//g)%MOD
    for t in a[:N//2]:
        res += divmod(g1,t)[0]%MOD
    res = res*r1%MOD

    res2 = 0
    r2 = (g1//g)%MOD
    for t in a[N//2:]:
        res2 += divmod(g2,t)[0]%MOD
    res2 = res2*r2%MOD
    print((res+res2)%MOD)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
N=input()
I=input()
a=I.split()
a.sort(reverse=True)
s=0
x=int(a[0])
for i in range(len(a)-1):
    b=int(a[i+1])
    z=x*b
    if(x<b):
        tmp=x
        x=b
        b=tmp
    r=x%b
    while r!=0:
        x=b
        b=r
        r=x%b
    x=z/b
u=[]
n=[]
c=0
l=0
o=int(math.sqrt(x))
pivot=sum(1 for y in a if int(y)>=o)
pivot=pivot-1
l = 0
for j in range(len(a)):
    if(j>=pivot):
        c=0
        for k in reversed(range(0,l)):
            if(a[j]==u[k]):
                s=s+u[k]
                l=k+1
                c=1
                break
        if(c==0):
            s=s+x/int(a[j])
    else:
        u.append(x/int(a[j]))
        s=s+int(u[j])
        l=l+1
print(int(s)%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from decimal import *
import fractions
import numpy as np

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

lcm = np.abs(A[0])
for i in range(1, n):
    lcm = (np.abs(lcm) / np.abs(fractions.gcd(lcm, A[i]))) * np.abs(A[i])

ans = 0
for j in range(n):
    ans += np.abs(lcm) / np.abs(A[j])
    ans = np.abs(ans) % np.abs(mod)

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:

import fractions as fr
import functools as ft
#import math as fr


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // fr.gcd(a, lcm_)
#    print(lcm_)
    
#ans = 0
#for a in an:
#    ans += lcm_ // a
#    ans = ans % prime if ans >= prime else ans

ans = ft.reduce(lambda x,y: (x + lcm_//y)%prime, an ,0 )

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 * y) // gcd(x, y)

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

x = A[0]
for i in range(N):
    x = lcm(x, A[i])

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

print(sums)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    return gcd(r, b)
    
def lcm(x, y):
    return (x * y) // gcd(x, y)

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

l = 1
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:
import math
import sys
import fractions

sys.setrecursionlimit(100000)

res = 1e9 + 7

def gcd(a, b):
    if a < b:
        return gcd(b, a)
    if b == 0:
        return a
    else:
        c = a % b % res
        return gcd(b, c)

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

ans = float(As[0] % res)
for i in range(1, N):
     ans = ans // gcd(ans, As[i]) * As[i]

# lcm_num = lcm_list(As)

sum = 0.0

for i in range(N):
  sum += int((ans / As[i]) % res)

print(int(sum % res))

Submission status: Time Limit Exceeded

Solution code:
def compute_lcm(x, y):
   # choose the greater number
   if x > y:
       greater = x
   else:
       greater = y
   while(True):
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1
   return lcm
   
n=int(input())
a=[]
res=int(1)
m=1000000007
sum=0
a = [int(i) for i in input().split()]
for i in range(n):
    res=compute_lcm(res,a[i])
    
for i in range(n):
    sum=sum+((res/a[i])%m)
sum%=m    
print (int(sum))

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    while a%b!=0:
        t=a%b
        a=b
        b=t
    return b
buf=[]
mul=1

n=int(input())
i=0;
for x in input().split():
    buf.append(int(x))  
    mul=mul*(buf[i]/gcd(mul,buf[i]))
    i+=1
sum=0
for i in range(n):
    buf[i]=mul/buf[i]
    sum+=buf[i]
    sum%=1000000007
print(int(sum))

Submission status: Time Limit Exceeded

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

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

count=0
for i in A:
    count+=a/i

print(round(count%((10**9)+7)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import fractions
from functools import reduce
n = int(input())

A = tuple(map(int, input().split()))
mod = 10**9 + 7
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
Z = lcm(*A)
ans = sum(Z//a%mod for a in A)%mod
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
A.sort()
lcm = 1
for i in A:
    lcm = (lcm*i)//GCD(lcm,i)
ans = 0
for i in A:
    ans += lcm//i
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
lcm = A[0]
B = [0]*N
dev = 10**9+7

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

for i in range(N):
  B[i] = lcm // A[i]

print(sum(B)%dev)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import time
n = int(input())
a = list(map(int, input().split()))
t1 = time.time()
mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
g = 1
flag = 1
for i in range(n):
    g = a[i] * g // gcd(a[i], g)
    #g %= mod
    t2 = time.time()
    if t2 - t1 > 0.5:
        flag = 0
        break

if flag == 1:
    ans = 0
    for i in range(n):
        ans += g * modinv(a[i])
        ans %= mod
    print(ans)

else:
    ans = 0

    for i in range(n):
        g = 1
        for j in range(n):
            if i == j:
                continue
            else:
                g *= a[j]
                g %= mod
        ans += g
    print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

M = 10 ** 9 + 7

cache = {}

def calc_factors(n):
	org_n = n
	if n in cache:
		return cache[n]
	max = math.ceil(math.sqrt(n))
	data = {}
	x = 2
	while x <= max:
		if n % x == 0:
			if x in data:
				data[x] += 1
			else:
				data[x] = 1
			n //= x
			max = math.ceil(math.sqrt(n))
		else:
			x += 1
	if n != 1:
		if n in data:
			data[n] += 1
		else:
			data[n] = 1
	cache[org_n] = data
	return data

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

total_factors = {}
factors_list = []

for A in A_list:
	factors = calc_factors(A)
	factors_list.append(factors)
	for factor, count in factors.items():
		if factor not in total_factors:
			total_factors[factor] = count
		elif total_factors[factor] < count:
			total_factors[factor] = count

total = 0
for A, factors in zip(A_list, factors_list):
	B = 1
	for factor, count in total_factors.items():
		if factor in factors:
			count -= factors[factor]
#		for _ in range(count):
#			B = (B * factor) % M
		B = (B * pow(factor, count, M)) % M
	total = (total + B) % M

print(total)

Submission status: Time Limit Exceeded

Solution code:
import fractions

N = int(input())
a_list = list(map(int, input().split()))
x = a_list[0]
for i in range(1, N):
    x = x * a_list[i] // fractions.gcd(x, a_list[i])
mod = 10 ** 9 + 7
t = 0
for a in a_list:
    b = x // a
    t += b % mod

ans = t % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**5)
def GCD(a, b):
  a, b = max(a,b), min(a, b)
  if a%b == 0:
    return b
  else:
    return GCD(b, a%b)
N = int(input())
A = list(map(int, input().split()))
L = 1
for a in A:
  g = GCD(a, L)
  L = a*L//g
ans = 0
for a in A:
  ans += L//a
print(ans%(7+10**9))

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

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

    return a

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

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

g = a[0]
l = 1

for i in a[1:]:
    g = gcd(g, i)

for i in range(n):
    a[i] //= g

for i in a:
    l = lcm(l, i)

s = 0

for i in a:
    s = (s + l // i) % MOD

print(s)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import time
n = int(input())
a = list(map(int, input().split()))
t1 = time.time()
mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
g = 1
flag = 1
for i in range(n):
    g = a[i] * g // gcd(a[i], g)
    #g %= mod
    t2 = time.time()
    if t2 - t1 > 0.8:
        flag = 0
        break

if flag == 1:
    ans = 0
    for i in range(n):
        ans += g * modinv(a[i])
        ans %= mod
    print(ans)

else:
    ans = 0

    for i in range(n):
        g = 1
        for j in range(n):
            if i == j:
                continue
            else:
                g *= a[j]
                g %= mod
        ans += g
    print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce 
def gcd(*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)

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

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

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

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

denom = int(1e9+7)

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

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

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

cm = reduce(lambda a,b: a*b, aaa)

ans_0 = [ cm//a for a in aaa ] 
gcd_ = reduce(gcd, ans_0)

# gcd_ = reduce(gcd, aaa)
# x = [ a//gcd_ for a in aaa ]
# lcm_ = gcd_ * reduce(lambda a,b: a*b, x)
lcm_ = (lcm(aaa))

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

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

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


n = int(input())

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

# 最大公倍数
target_num = lcm(*a)

b = []
for i in range(n):
    b.append(target_num//a[i])

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

Submission status: Time Limit Exceeded

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

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

def solve(N, A):
    mod = 10 ** 9 + 7
    lcm = lcm_list(A)
    ans = [lcm//a for a in A]
    return sum(ans) % mod


def main():
    read = sys.stdin.buffer.read
    
    N,*A = map(int,read().split())
    ans = solve(N, A)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import numpy as np

n = int(input())
a = list(map(int, 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

a_lcm = lcm(a)
aa = np.array(a)
aa = a_lcm // aa
aa = aa.tolist()
ans = 0
for i, n in enumerate(aa):
    ans += n
    if i%30==0:
        ans %= 10**9+7

ans %= 10**9+7

print(int(ans))

Submission status: Time Limit Exceeded

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

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


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

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


n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
ans=0
m=int(10**9+7)
g=1
l=1
'''
for x in a:
  if l%x!=0:
    g=gcd(l,x)
    l=l*x//g
'''
l=lcm(*a)

for x in a:
  ans+=(l//x)%m

print(ans%m)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))


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

MOD = 10 ** 9 + 7
ans = 0
for i, a in enumerate(A):
    ans += lcm // a
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(map(int,input().split()))
ans = 0
mod = int(1e9+7)
def gcd(a,b):
  while b != 0:
    a, b = b, a % b
  return a
# 最小公倍数
def lcm(a,b):
    return (a*b) // gcd(a,b)

g = 1
for i in range(n):
    g = lcm(g, s[i])
for i in range(n):
    ans += g // s[i] % mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
  MOD=10**9+7
  import sys
  input = sys.stdin.readline
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  ans=0
  import numpy as np
  A=np.array(A)
  ans=0
  for i in range(N):
    ans+=z//A[i]
  print(ans%MOD)
  
if __name__=='__main__':
  main()

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):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  if len(set(l))*2<=n:
    from itertools import groupby as gb
    sl,kl=[list(a) for a in zip(*[(q,len(list(w))) for q,w in gb(sorted(l))] )]
    for i in sl:
      f=i*f//gcd(i,f)
    ans=0
    for i,iy in enumerate(sl):
      ans+=(f//iy)*kl[i]%mod
    print(ans)
    exit()
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    ans+=(f//iu)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
for a in As:
    if a == 1:
        continue
    factors = factorization(a)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]

ans = 0
for a in As:
    ans += lcm//a
    ans %= mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
a = inpl()
g = 1
res = 0
for i in a:
    g = i*g//fractions.gcd(i,g)
for i in a:
    res += g//i
    res %= mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
ferumaC=300000
fac=[0 for i in range(ferumaC)]
fac[0]=1
ifac=[0 for i in range(ferumaC)]
ifac[0]=1
def mpow(x,n):
    num=1
    while n > 0:
        if n&1:
            num=num*x%mod
        x=x*x%mod
        n=n>>1
    return(num)

for i in range(0,ferumaC-1):
    fac[i+1]=(fac[i]*(i+1))%mod
    ifac[i+1]=ifac[i]*mpow(i+1,mod-2)%mod
def comb(a,b):
    if a==0 and b==0:return(1)
    if a<b or a<0:return(0)
    tmp=ifac[a-b]*ifac[b]%mod
    return(tmp*fac[a]%mod)


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

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

value=A[0]
for i in range(1,N):
    value=lcm(value,A[i])
count=0
for a in A:
    count+=value*(mpow(a,mod-2))%mod
    count%=mod
print(count)

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)


def solve(N, As):
    l = lcm_list(As)
    res = 0
    for i in range(N):
        res = (res + l // As[i]) % (10 ** 9 + 7)
    return res


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

print(solve(N, As))

Submission status: Time Limit Exceeded

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

#最小公倍数
def lcm(x,y):
    return x*y//gcd(x,y)

mod=10**9+7
t=a[0]
for i in a:
    t=lcm(t,i)

ans=0
for i in a:
    ans+=t//i
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(4100000)
    input = sys.stdin.readline
    from fractions import gcd
    from collections import Counter

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

    values_counts = Counter(A).most_common()

    L = values_counts[0][0]
    for v, c in values_counts[1:]:
        L = L * v // gcd(L, v)

    ans = 0
    for v, c in values_counts:
        ans += (L // v) * c
        ans %= INF
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys

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

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):
    sum_b += ans / a[i]

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import numpy as np

n = int(input())
a = list(map(int, 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

a_lcm = lcm(a)
aa = np.array(a)
aa = a_lcm // aa
aa = aa.tolist()
ans = 0
for i, n in enumerate(aa):
    ans += n
    if i%10==0:
        ans %= 10**9+7

ans %= 10**9+7

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(a,b):
    return (a*b)//gcd(a,b)

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

Submission status: Time Limit Exceeded

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


mod = 10**9 + 7


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


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


lcm = lcm(S)

ans = 0
for a in A:
    ans += lcm//a
    # ans %= mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

for a in A:
    res += l//a

print(res % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import time
n = int(input())
a = list(map(int, input().split()))
t1 = time.time()
mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
g = 1
flag = 1
for i in range(n):
    g = a[i] * g // gcd(a[i], g)
    #g %= mod
    t2 = time.time()
    if t2 - t1 > 1:
        flag = 0
        break

if flag == 1:
    ans = 0
    for i in range(n):
        ans += g * modinv(a[i])
        ans %= mod
    print(ans)

else:
    ans = 0

    for i in range(n):
        g = 1
        for j in range(n):
            if i == j:
                continue
            else:
                g *= a[j]
                g %= mod
        ans += g
    print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import fractions

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

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

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

l = lcm(*A)

l = int(l)
MOD = 1000000007

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

print(ans)

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]
to = a[0]
for i in range(1, n):
	num = lcm(num, a[i])
	to *= a[i]

ans = 0
for i in range(n):
	ans += to//a[i]
print(((num*ans)//to)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
import functools
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def multiple(a, b):
    return a*b // euclid(a, b)
def lcm(nums):
        return functools.reduce(multiple, nums)

if __name__ == "__main__":
    mod = 10**9+7
    N = int(input())
    A = list(map(int, input().split()))
    ll = lcm(A)
    ans = 0
    for a in A:
        ans += (ll//a)%mod
        ans %= mod
    print(int(ans))

Submission status: Time Limit Exceeded

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

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

count=a[0]
for i in range(n-1):
    count=lcm(count,a[i+1])
ans=0
for i in range(n):
    ansa=count//a[i]
    ans+=ansa
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
ferumaC=300000
fac=[0 for i in range(ferumaC)]
fac[0]=1
ifac=[0 for i in range(ferumaC)]
ifac[0]=1
def mpow(x,n):
    num=1
    while n > 0:
        if n&1:
            num=num*x%mod
        x=x*x%mod
        n=n>>1
    return(num)

for i in range(0,ferumaC-1):
    fac[i+1]=(fac[i]*(i+1))%mod
    ifac[i+1]=ifac[i]*mpow(i+1,mod-2)%mod
def comb(a,b):
    if a==0 and b==0:return(1)
    if a<b or a<0:return(0)
    tmp=ifac[a-b]*ifac[b]%mod
    return(tmp*fac[a]%mod)


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

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

value=A[0]
for i in range(1,N):
    value=lcm(value,A[i])
count=0
for a in A:
    count+=value*(mpow(a,mod-2))
    count%=mod
print(count)