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: Runtime Error

Solution code:
def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
a = []
n = int(input())
a = list(map(int, input().split()))
d = a[0]
for i in range (1, n):
  d = lcm(d, a[i])
sum = 0
for i in range (0, n):
  sum = sum + d // a[i]
  sum %= (int)(1000000007)
print((int)(sum))

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

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

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

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

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

lcm = lcm_list(list)

ans = 0

for i in range(N):
  ans += int(lcm / list[i])

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

Submission status: Runtime Error

Solution code:
import fractions
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
def func(x,y):
    return (x*y)//fractions.gcd(x,y)
AB = reduce(func, A, 1)
sumB = 0
for ii in range(N):
    sumB += (AB/A[ii])%(10**9+7)
print(int(sumB%(10**9+7)))

Submission status: Runtime Error

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

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

LCM = lcm(A)

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

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

from functools import reduce

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

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

L = reduce(lcm, a)

# print(L)

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

print(ans)

Submission status: Runtime Error

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

def gcd(x, y):
  b = max(x, y)
  s = min(x, y)
  r = b % s
  while r != 0:
    b = s
    s = r
    r = b % s
  return s

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

class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invL(s, a, n):
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L

t = lcm(A[0], A[1])
inv = Inv(MOD)
for i in range(2, N):
  t = lcm(t, A[i]) % MOD

ans = 0
for i in range(N):
  ans = (ans + t * inv.invx(A[i])) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

lcm = 1
for i in s:
    lcm = (lcm * i) // math.gcd(lcm, i)

su = 0
for i in s:
    su = (su + lcm // i) % 1000000007

print(su)

Submission status: Runtime Error

Solution code:
def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
a = []
n = int(input())
a = list(map(int, input().split()))
d = a[0]
for i in range (1, n):
  d = lcm(d, a[i])
sum = 0
for i in range (0, n):
  sum = sum + d // a[i]
  sum %= 1000000007
print((int)(sum))

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

n=int(input())
a=list(map(int, input().split()))
A=lcm(a)
ans=0

for i in a:
    ans+=A/i

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

Submission status: Runtime Error

Solution code:
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

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

Submission status: Runtime Error

Solution code:
from math import gcd

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

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

l = 1

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

s = 0

MOD = 10 ** 9 + 7

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

print(s)

Submission status: Runtime Error

Solution code:
import math
import numpy as np
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


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


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


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


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


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

tp = lcm_list(a)
# print(tp)
print(sum(tp//np.array(a)))

Submission status: Runtime Error

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N =int(input())
li = list(map(int,input().split()))
lcm_all = 1
for i in li:
  lcm_all =lcm(lcm_all, i)
sum = 0
k_mod = 1e9 + 7
for i in li:
  sum += lcm_all/i
  sum %= k_mod
print(int(sum))

Submission status: Runtime Error

Solution code:
import math
from functools import reduce


def MinB(x, y):
    return (x * y) // math.gcd(x, y)

def MinB_list(numbers):
    return reduce(MinB, numbers, 1)

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

tmp = MinB_list(AList)
result = 0
for i in range(0, N):
    result += tmp // AList[i]
    
print(result % (10 ** 9 + 7))

Submission status: Runtime Error

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

from numpy import lcm

l = lcm.reduce(a)

ans = 0
for e in a:
    add = l // e
    ans += add
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
import fractions
from functools import reduce

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

def lcm_list(l):
    return reduce(lcm, l, 1)


ans = 0

dev = 10 ** 9 + 7

n = int(input())

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

z = lcm_list(a) * 


for i in a:
    ans += z // i
    #ans = ans % dev

print(ans%dev)

Submission status: Runtime Error

Solution code:
from math import gcd
from functools import reduce

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

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

lcm = lcm(a)

count = 0
for i in a:
    count += (lcm // i) % 1000000007
    count %= 1000000007

print (count)

Submission status: Runtime Error

Solution code:
import math

N = input()

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

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

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

ans = 0
for i in A:
    ans += l // i

print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import fractions
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
def func(x,y):
    return (x*y)//fractions.gcd(x,y)
AB = reduce(func, A, 1)
sum = 0
for ii in range(N):
    sum += AB/A[ii]%(10**9+7)
print(int(sum%(10**9+7)))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
a = list(map(int, input().split(' ')))
nok = a[0]
mod = int(1e9 + 7)
for i in range(1, n):
    nok = nok * a[i] // math.gcd(nok, a[i])
ans = 0
for i in range(0, n):
    ans += nok // a[i]
print (ans % mod)

Submission status: Runtime Error

Solution code:
def find_lcm(num1, num2): 
    if(num1>num2): 
        num = num1 
        den = num2 
    else: 
        num = num2 
        den = num1 
    rem = num % den 
    while(rem != 0): 
        num = den 
        den = rem 
        rem = num % den 
    gcd = den 
    lcm = int(int(num1 * num2)/int(gcd)) 
    return lcm 

n=int(input())
l=[int(x) for x in input().split()]
if(n==1):
        print(1)
else:
        num1 = l[0] 
        num2 = l[1] 
        lcm = find_lcm(num1, num2) 
        for i in range(2, len(l)): 
            lcm = find_lcm(lcm, l[i])
        k=0
        for i in l:
                k=(k+lcm//i)%(10**9+7)
        print(k)

Submission status: Runtime Error

Solution code:
import fractions

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

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

g = lcm(a[0], a[1])

for val in a[2:]:
    g = lcm(g, val)

ans = 0
for val in a:
    ans += g//val % mod

print(ans % mod)

Submission status: Runtime Error

Solution code:
def find_lcm(num1, num2):
	if(num1>num2):
		num = num1
		den = num2
	else:
		num = num2
		den = num1
	rem = num % den
	while(rem != 0):
		num = den
		den = rem
		rem = num % den
	gcd = den
	lcm = int(int(num1 * num2)/int(gcd))
	return lcm

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

num1 = arr[0]
num2 = arr[1]
lcm = find_lcm(num1, num2)

for i in range(2, len(arr)):
	lcm = find_lcm(lcm, arr[i])

ans = 0
for i in arr:
	if( i != 0 ):
		ans += lcm // i

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

Submission status: Runtime Error

Solution code:
import math
import numpy as np
from fractions import gcd
import fractions
import statistics
import collections
from functools import reduce
import itertools
from collections import defaultdict
import bisect
from fractions import Fraction


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

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

num = lcm_list(A)

ans = 0

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

print(ans）

Submission status: Runtime Error

Solution code:
def lcm_core(a,b):
    g = gcd_core(a,b)
    return (a*b)//g

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

def lcm(arr):
    m = 10**9+7
    mcnt = 0
    l = lcm_core(arr[0],arr[1])
    for i in range(2,len(arr)):
        l = lcm_core(l,arr[i])
        mcnt += l//m
        l %= m
    return l,mcnt

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

# print(l)
m = 10**9+7

ans = 0
for i in range(n):
    temp = l + (m%arr[i])*mcnt
    # print(temp)
    ans += (temp//arr[i]) + (m//arr[i])*mcnt
    ans %= m

print(ans)

Submission status: Runtime Error

Solution code:
import fractions

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

# 最小公倍数の算出
ans = A[0]
for i in range(1, N):
    ans = ans * A[i] // fractions.gcd(ans, A[i])
koubai = ans

B = list(map(lambda x:koubai/x, A))
for b in B:
  res += b % (10**9+7)
  res = res % (10**9+7)

print(int(res))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

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

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

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

ans = 0
MOD = int(1e9 + 7)
for i in range(N):
    ans += int(l // A[i])
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

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

def lcm_list(l):
    return reduce(lcm, l, 1)


ans = 0

dev = 10 ** 9 + 7

n = int(input())

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

z = lcm_list(a)


for i in a:
    ans += z // i
    ans = ans % dev

print(ans)

Submission status: Runtime Error

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

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

total_times = 1
for i in listA:
  total_times = total_times * i

result = 0
prev = 1
for i in listA:
  result += total_times / i

print(int(result * lcm(listA) / total_times % (10 ** 9 + 7)))

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
def func(x,y):
    return (x*y)//math.gcd(x,y)
AB = reduce(func, A, 1)
sum = 0
for ii in range(N):
    sum += AB/A[ii]%(10**9+7)
print(int(sum%(10**9+7)))

Submission status: Runtime Error

Solution code:
# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def lcm(num1, num2): 
    if(num1>num2): 
        num = num1 
        den = num2 
    else: 
        num = num2 
        den = num1 
    rem = num % den 
    while(rem != 0): 
        num = den 
        den = rem 
        rem = num % den 
    gcd = den 
    lcm = int(int(num1 * num2)/int(gcd)) 
    return lcm 


MOD = 10**9+7

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

s = sum(modinv(a,MOD) for a in A)%MOD


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

s *= m
print(s%MOD)

Submission status: Runtime Error

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

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

total_times = 1
for i in listA:
  total_times = total_times * i

result = 0
prev = 1
for i in listA:
  result += total_times / i

print(int(result * lcm(a) / total_times % (10 ** 9 + 7)))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

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

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

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

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

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

def lcm_ls(num):
    return reduce(lcm, num, 1)


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

m = lcm_ls(ls)

ans = 0

for i in range(n):
    ans += m // ls[i]

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

Submission status: Runtime Error

Solution code:
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

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

for i in range(N):
    if i == 0:
        LCM = A[0]
    else:
        LCM = lcm(LCM,A[i])

for j in range(N):
    S = S + (LCM // A[j])

S = S % (10**9 + 7)
print(S)

Submission status: Runtime Error

Solution code:
from sys import stdin
from math import gcd
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
lcm = a[0]
for i in range(1,n):lcm = (lcm*a[i])//gcd(lcm,a[i])
b = [lcm // i for i in a]
print(sum(b)%1000000007)

Submission status: Runtime Error

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])
koubai = ans

B = list(map(lambda x:koubai/x, A))

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

Submission status: Runtime Error

Solution code:
import math
from functools import reduce

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

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

N = int(input())
A = [int(x) for x in input().split()]
t = lcm(A)

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

print(ans)

Submission status: Runtime Error

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

mod = 1e9+7
n = int(input())
a = list(map(int,input().split()))

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

ans = 0
for i in range(n):
	ans= (ans+now//a[i])%mod
print(int(ans))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#n,m = [int(i) for i in readline().split()]
#d = [int(i) for i in readline().split()]
MOD = 10**9+7

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

#m = 1000000
#a = list(range(m,m+2000))

from math import gcd
m = a[0]
for i in a:
    m = m//gcd(m,i)*i

ans = 0
for i in a:
    ans += (m//i)%MOD

print(ans%MOD)

Submission status: Runtime Error

Solution code:
# Contest: AtCoder Beginner Contest 152 (https://atcoder.jp/contests/abc152)
# Problem: E: Flatten (https://atcoder.jp/contests/abc152/tasks/abc152_e)

def rint():
    return int(input())


def rints():
    return list(map(int, input().split()))


from math import gcd
from functools import reduce
def lcm(a, b):
    return a * b // gcd(a, b)
n = rint()
a = rints()
l = reduce(lcm, a)
m = 10**9 + 7
print(sum(l // ai % m for ai in a) % m)

Submission status: Runtime Error

Solution code:
def lcm_core(a,b):
    g = gcd_core(a,b)
    return (a*b)//g

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

def lcm(arr):
    l = lcm_core(arr[0],arr[1])
    for i in range(2,len(arr)):
        l = lcm_core(l,arr[i])
    return l

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

Submission status: Runtime Error

Solution code:
def find_lcm(num1, num2):
	if(num1>num2):
		num = num1
		den = num2
	else:
		num = num2
		den = num1
	rem = num % den
	while(rem != 0):
		num = den
		den = rem
		rem = num % den
	gcd = den
	lcm = int(int(num1 * num2)/int(gcd))
	return lcm

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

num1 = arr[0]
num2 = arr[1]
lcm = find_lcm(num1, num2)

for i in range(2, len(arr)):
	lcm = find_lcm(lcm, arr[i])

ans = 0
for i in arr:
	ans += lcm // i

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

Submission status: Runtime Error

Solution code:
def lcd(x,y):
    g = gcd(x,y)
    return x*y//g
n = int(input())
a = list(map(int, input().split( )))

#最小公倍数でよいか？
#全てのjについてAiBiはAjで割り切れる
#途中でmod処理は無理
#計算時間は？
from fanctions import gcd:
mod =10**9+7

Ag　= 1
for i in range(n):
    Ag = lcd(Ag,a[i])

ans = 0

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

print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = map(int,input().split())
mod = 10**9+7
def power(a,b):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power(a,b//2)
        return d*d%mod
    elif b % 2 == 1:
        return a*power(a,b-1)%mod
import fractions
l = A[i]
g = A[i]
for i in range(1,N):
    x = A[i]
    g = fractions.gcd(l,x)
    l = l*x%g
l = l % mod
ans = 0
for i in range(N):
    ans += l*power(A[i],mod-2) % mod
ans = ans%mod
print(ans)