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:
import math
MOD = 10**9+7

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

MAX = 10**6
C = [0 for _ in range(MAX+1)]
A.sort()
for a in A:
  C[a] += 1
MAX = max(A[-1],2)

ans = 1
P = [1 for _ in range(MAX+1)] #素数かどうか
P[0] = 0
P[1] = 0
lim = min(math.sqrt(MAX) + 1,MAX-1)
S = [0 for _ in range(MAX+1)] #最小公倍数の素因数分解したもの
for i in range(2,int(lim+2)):
  #素数でないなら以下の手順を行わない
  if P[i] == 0:
    continue
  #エラトステネスの篩
  k = i*2
  while k <= MAX:
    P[k] = 0
    k += i
  ind = 0
  k = 1
  while k <= MAX:
    k *= i
    ind += 1
  k = k // i 
  ind -= 1
  #最大のべきを調べる
  while k > 1:
    l = k
    flag = False
    while l <= MAX:
      if C[l] > 0:
        flag = True
        break
      l += k
    if flag:
      break
    k = k // i
    ind -= 1
  S[i] = ind
  
ans = 1
for i in range(N+1):
  ans *= pow(i,S[i],MOD)
  ans %= MOD
  
#モジュラ逆数
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    #if g != 1:
        #raise Exception('modular inverse does not exist')
    #else:
    return x % m
      
B = [0 for _ in range(MAX+1)]
ans_2 = 0
for a in A:
  if B[a] > 0:
    ans_2 += B[a]
  else:
    B[a] = modinv(a, MOD)
    ans_2 += B[a]    
  ans_2 %= MOD 

#print(ans, ans_2, P, S, B)
print((ans * ans_2) % MOD)

Submission status: Runtime Error

Solution code:
import math
MOD = 10**9+7

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

MAX = 10**6
C = [0 for _ in range(MAX+1)]
A.sort()
for a in A:
  C[a] += 1
MAX = A[-1]

ans = 1
P = [1 for _ in range(MAX+1)] #素数かどうか
P[0] = 0
P[1] = 0
lim = math.sqrt(MAX) + 1
S = [0 for _ in range(MAX+1)] #最小公倍数の素因数分解したもの
for i in range(2,int(lim+2)):
  #素数でないなら以下の手順を行わない
  if P[i] == 0:
    continue
  #エラトステネスの篩
  k = i*2
  while k <= MAX:
    P[k] = 0
    k += i
  ind = 0
  k = 1
  while k <= MAX:
    k *= i
    ind += 1
  k = k // i 
  ind -= 1
  #最大のべきを調べる
  while k > 1:
    l = k
    flag = False
    while l <= MAX:
      if C[l] > 0:
        flag = True
        break
      l += k
    if flag:
      break
    k = k // i
    ind -= 1
  S[i] = ind
  ans *= pow(i,ind,MOD)
  ans %= MOD
    
#モジュラ逆数
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    #if g != 1:
        #raise Exception('modular inverse does not exist')
    #else:
    return x % m
      
B = [0 for _ in range(MAX+1)]
ans_2 = 0
for a in A:
  if B[a] > 0:
    ans_2 += B[a]
  else:
    B[a] = modinv(a, MOD)
    ans_2 += B[a]    
  ans_2 %= MOD 

#print(ans, ans_2, P, S, B)
print((ans * ans_2) % MOD)

Submission status: Runtime Error

Solution code:
import math
MOD = 10**9+7

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

MAX = 10**6
C = [0 for _ in range(MAX+1)]
A.sort()
for a in A:
  C[a] += 1
MAX = A[-1]

ans = 1
P = [1 for _ in range(MAX+1)] #素数かどうか
P[0] = 0
P[1] = 0
lim = math.sqrt(MAX) + 1
S = [0 for _ in range(MAX+1)] #最小公倍数の素因数分解したもの
for i in range(2,int(lim+2)):
  #素数でないなら以下の手順を行わない
  if P[i] == 0:
    continue
  #エラトステネスの篩
  k = i*2
  while k <= MAX:
    P[k] = 0
    k += i
  ind = 0
  k = 1
  while k <= MAX:
    k *= i
    ind += 1
  k = k // i 
  ind -= 1
  #最大のべきを調べる
  while k > 1:
    l = k
    flag = False
    while l <= MAX:
      if C[l] > 0:
        flag = True
        break
      l += k
    if flag:
      break
    k = k // i
    ind -= 1
  S[i] = ind
  ans *= pow(i,ind,MOD)
  ans %= MOD
    
#モジュラ逆数
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
      
B = [0 for _ in range(MAX+1)]
ans_2 = 0
for a in A:
  if B[a] > 0:
    ans_2 += B[a]
  else:
    B[a] = modinv(a, MOD)
    ans_2 += B[a]    
  ans_2 %= MOD 

#print(ans, ans_2, P, S, B)
print((ans * ans_2) % MOD)

Submission status: Runtime Error

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
a=list(map(int,input().split()))

Mod=10**9+7
M=10**6 #書き換え
fac=[0]*M
finv=[0]*M
inv=[0]*M

#finvに逆元、facに階乗のmod
def COMinit():
  fac[0]=fac[1]=1
  finv[0]=finv[1]=1
  inv[1]=1
  for i in range(2,M):
    fac[i]=(fac[i-1]*i%Mod)%Mod
    inv[i]=Mod-inv[Mod%i]*(Mod//i) %Mod
    finv[i]=(finv[i-1]*inv[i]%Mod)%Mod
def COM(n,k):
  if n<k:
    return 0
  if n<0 or k<0:
    return 0
  return (fac[n]*(finv[k]*finv[n-k]%Mod)%Mod)%Mod

COMinit()

def factorize(n):
    fct={}
    temp=n
    if temp<4:
        fct[temp]=1
    else:
        e=0
        while temp%2==0:
            temp=temp//2
            e+=1
        if e>0:
            fct[2]=e
    
    for b in range(3,int(n**0.5)+1,2):
        e=0
        while temp%b == 0:
            temp=temp//b
            e+=1
        if e>0:
            fct[b]=e
    if temp!=1:
        fct[temp]=1
    return fct

res={}
for i in a:
    f=factorize(i)
    for j in f:
        if j not in res:
            res[j]=f[j]
        else:
            res[j]=max(res[j],f[j])
c=1
ans=0
for i in res:
    c*=pow(i,res[i],Mod)
    c%=Mod
for i in a:
    ans+=c*inv[i]
    ans%=Mod
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

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

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

Submission status: Runtime Error

Solution code:
from fractions import gcd 

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

lcm = As[0]*As[1]//gcd(As[0],As[1])

for i in range(2,N):
  c = gcd(lcm, As[i])
  lcm *= As[i]//c
  
rlt = 0
for a in As:
  rlt += lcm//a
  rlt %= P

print(rlt)

Submission status: Runtime Error

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################

## return the list of prime numbers in [2,N], using eratosthenes sieve
## around 800 ms for N = 10**6  by PyPy3 (7.3.0) @ AtCoder
def PrimeNumSet(N):
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] > Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


show_flg=False
show_flg=True

n=I()
a=sorted(LI())

N=10**2
prs=PrimeNumSet(N)

l=defaultdict(int)
for i in range(n):
    t=a[i]
    for p in prs:
        if t%p==0:
            c=0
            while t%p==0:
                t//=p
                c+=1
            l[p]=max(l[p],c)
    if t!=1:
        l[t]=1

ans=0
for i in range(n):
    t=a[i]
    tmp=1
    for p in l:
        c=0
        if t%p==0:
            while t%p==0:
                t//=p
                c+=1
        tmp*=pow(p,l[p]-c,mo)
        tmp%=mo
        #show(p,l[p]-c,a[i])
    ans+=tmp
print(ans%mo)

Submission status: Runtime Error

Solution code:
n=int(input(""))
lista=input("").split(" ")
listso=[]
def prime(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
listso+=prime(int(lista[0]))
for i in range(1,n):
    a=int(lista[i])
    for k in listso:
        if(a%k==0):
            a/=k
    listso+=prime(a)
   
c=1
for i in listso:
    c*=i
    

s=0
for i in lista:
    s+=c/int(i)
    s%=(10**9+7)
print(int(s))

Submission status: Runtime Error

Solution code:
n=int(input(""))
lista=input("").split(" ")
listso=[]
def prime(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
listso+=prime(int(lista[0]))
for i in range(1,n):
    a=int(lista[i])
    for k in listso:
        if(a%k==0):
            a/=k
    listso+=prime(a)
   
c=1
for i in listso:
    c*=i

s=0
for i in lista:
    s+=c/int(i)
    s%=(10**9+7)
print(int(s))

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_list(numbers):
    return reduce(lcm_base, numbers, 1)
N=int(input())
huga = list(map(int, input().split()))
X=lcm_list(huga)
sum1=0
for i in range (N):
    sum1+=(X/huga[i])%(10**9+7)
print(int(sum1))

Submission status: Runtime Error

Solution code:
def get_primes(n=10**6):
    primes = [2]
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if n <= p ** 2:
            return primes + data
        primes.append(p)
        data = [d for d in data if d % p != 0]


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # 答えは sum(lcm(A) / A)
    primes = get_primes(max(max(A), 2))
    lcm_pf = [0] * len(primes)
    a_pf = [[0] * len(primes) for _ in range(N)]
    # lcm(A) の素因数分解表示を計算
    for i, a in enumerate(A):
        for j, p in enumerate(primes):
            while a % p == 0:
                a_pf[i][j] += 1
                a //= p
            if a == 1:
                break
        for j in range(len(primes)):
            lcm_pf[j] = max(lcm_pf[j], a_pf[i][j])
    # sum(lcm(A) / A) を計算
    ans = 0
    for i in range(N):
        v = 1
        for j, p in enumerate(primes):
            e = lcm_pf[j] - a_pf[i][j]
            v *= p ** e
            v %= MOD
        ans += v
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def get_primes(n=10**6):
    primes = [2]
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if n <= p ** 2:
            return primes + data
        primes.append(p)
        data = [d for d in data if d % p != 0]


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # 答えは sum(lcm(A) / A)
    primes = get_primes(max(A))
    lcm_pf = [0] * len(primes)
    a_pf = [[0] * len(primes) for _ in range(N)]
    # lcm(A) の素因数分解表示を計算
    for i, a in enumerate(A):
        for j, p in enumerate(primes):
            while a % p == 0:
                a_pf[i][j] += 1
                a //= p
            if a == 1:
                break
        for j in range(len(primes)):
            lcm_pf[j] = max(lcm_pf[j], a_pf[i][j])
    # sum(lcm(A) / A) を計算
    ans = 0
    for i in range(N):
        v = 1
        for j, p in enumerate(primes):
            e = lcm_pf[j] - a_pf[i][j]
            v *= p ** e
            v %= MOD
        ans += v
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from functools import reduce

def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        r = x % y
        x = y
        y = r
    return y

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

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

def addmod(a, b):
    return (a+b) % MOD
  
  
N = int(input())
a_list = list(map(int, input().split()))
MOD = 10 ** 9 + 7

l = reduce(lcm, a_list) % MOD
ans = reduce(addmod, (l//a for a in a_list))

print(ans)

Submission status: Runtime Error

Solution code:
def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        r = x % y
        x = y
        y = r
    return y

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

    
N = int(input())
a_list = list(map(int, input().split()))
MOD = 10 ** 9 + 7
 
if N == 1:
    print(a_list[0])
    exit()
div = gcd(a_list[0], a_list[1])
lcm = (a_list[0] * a_list[1]) * inv(div)
 
for i in range(2, N):
    div = gcd(lcm, a_list[i])
    lcm = (lcm * a_list[i]) * inv(div)
    
ans = 0
for i in range(N):
    ans = (ans + lcm * inv(a_list[i]) % MOD
 
print(ans)

Submission status: Runtime Error

Solution code:
def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        r = x % y
        x = y
        y = r
    if y == 0:
        return 1
    return y

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

div = gcd(a_list[0], a_list[1])
lcm = (a_list[0] * a_list[1]) // div

for i in range(2, N):
    div = gcd(lcm, a_list[i])
    lcm = (lcm * a_list[i]) // div
    
ans = 0
for i in range(N):
    ans = (ans + lcm//a_list[i]) % MOD

print(ans)

Submission status: Runtime Error

Solution code:
def gcd(x, y):
    if x < y:
        x, y = y, x
    if y == 1:
        return 1
    while x % y != 0:
        r = x % y
        x = y
        y = r
    return y

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

div = gcd(a_list[0], a_list[1])
lcm = (a_list[0] * a_list[1]) // div

for i in range(2, N):
    div = gcd(lcm, a_list[i])
    lcm = (lcm * a_list[i]) // div
    
ans = 0
for i in range(N):
    ans = (ans + lcm//a_list[i]) % MOD

print(ans)

Submission status: Runtime Error

Solution code:
def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        r = x % y
        x = y
        y = r
    return y

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

div = gcd(a_list[0], a_list[1])
lcm = (a_list[0] * a_list[1]) // div

for i in range(2, N):
    div = gcd(lcm, a_list[i])
    lcm = (lcm * a_list[i]) // div
    
ans = 0
for i in range(N):
    ans = (ans + lcm//a_list[i]) % MOD

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
import sys
sys.setrecursionlimit(10 ** 7)
import math
def lcm(k):
    ans = k[0]
    for i in range(1, len(k)):
        ans = ans * k[i] // math.gcd(ans, k[i])
    return ans

l = lcm(a)
ans = 0
mod = 10**9+7
for i in range(n):
  ans+=l/a[i]
  ans%=mod
print(int(ans))

Submission status: Runtime Error

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

import fractions
def lcm(k):
    ans = k[0]
    for i in range(1, len(k)):
        ans = ans * k[i] // fractions.gcd(ans, k[i])
    return ans

l = lcm(a)
ans = 0
mod = 10**9+7
for i in range(n):
  ans+=l/a[i]
  ans%=mod
print(int(ans))

Submission status: Runtime Error

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

import fractions
def lcm(k):
    ans = k[0]
    for i in range(1, len(k)):
        ans = ans * k[i] // fractions.gcd(ans, k[i])
    return ans

l = lcm(a)
ans = 0
mod = 10**9+7
for i in range(n):
  ans+=int(l/a[i])
  ans%=(10**9+7)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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*pow(gcd(a,b), M-2, M)
#     return a//gcd(a, b)*b

def lcms(a):
    l = a[0]
    for num in a[1:]:
        l = lcm(l, num)
    return l

l = lcms(a)    
ans = 0
M = 10**9+7
for num in a:
    ans += (l*pow(num, M-2, M))
    ans %= M
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class Eratosthenes:
    def __init__(self, n):
        self.n = n
        self.min_factor = [-1] * (n + 1)
        self.min_factor[0], self.min_factor[1] = 0, 1

    def get_primes(self):
        primes = []
        is_prime = [True] * (self.n + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, self.n + 1):
            if not is_prime[i]:
                continue
            primes.append(i)
            self.min_factor[i] = i
            for j in range(i * 2, self.n + 1, i):
                is_prime[j] = False
                if self.min_factor[j] == -1:
                    self.min_factor[j] = i
        return primes

    def prime_factorization(self, n):
        res = []
        while n != 1:
            prime = self.min_factor[n]
            exp = 0
            while self.min_factor[n] == prime:
                exp += 1
                n //= prime
            res.append([prime, exp])
        return res

def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    MAX_A = max(A)

    er = Eratosthenes(MAX_A)
    er.get_primes()
    num = [0] * MAX_A
    for i in range(n):
        pf = er.prime_factorization(A[i])
        for p, ex in pf:
            num[p] = max(num[p], ex)

    LCM = 1
    for v in range(2, MAX_A):
        LCM *= pow(v, num[v], mod)
        LCM %= mod

    res = 0
    for a in A:
        res += LCM * pow(a, mod - 2, mod)
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict


class PrimeFactor():

    def __init__(self, n):                  # エラトステネス　O(N loglog N)
        self.n = n
        self.table = list(range(n+1))
        self.table[2::2] = [2]*(n//2)
        for p in range(3, int(n**0.5) + 2, 2):
            if self.table[p] == p:
                self.table[p * p::2 * p] = [p] * ((n - p * p - 1) // (2 * p) + 1)

    def is_prime(self, x):  # 素数判定　O(1)
        if x < 2:
            return False
        return self.table[x] == x

    def prime_factors(self, x):             # 素因数分解 O(logN)
        res = []
        if x < 2:
            return res
        while self.table[x] != 1:
            res.append(self.table[x])
            x //= self.table[x]
        return res

    def prime_counter(self, x):             # 素因数分解（個数のリスト）
        res = defaultdict(int)
        if x < 2:
            return res
        while self.table[x] != 1:
            res[self.table[x]] += 1
            x //= self.table[x]
        return res

    def prime_gcd(self, X):                 # n個の最大公約数　X:n個のリスト
        exponents = self.prime_counter(X[0])
        for x in X[1:]:
            Y = self.prime_counter(x)
            for prime, exp in exponents.items():
                if Y[prime] < exp:
                    exponents[prime] = Y[prime]
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp)
        return res

    def prime_lcm(self, X, mod=None):       # n個の最小公倍数　X:n個のリスト
        exponents = defaultdict(int)
        for x in X:
            for prime, exp in self.prime_counter(x).items():
                if exp > exponents[prime]:
                    exponents[prime] = exp
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp, mod)
        if mod == None:
            return res
        else:
            return res % mod

mod = 10 ** 9 + 7

N = int(input())
A = list(map(int, input().split()))
A.sort()
table = PrimeFactor(A[-1])
num = table.prime_lcm(A,mod)

res = 0
for a in A:
    res += num * pow(a, mod - 2, mod)

print(res % mod)

Submission status: Runtime Error

Solution code:
from math import lcm

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

lcm_a = 1
 
for i in range(N):
    lcm_a = lcm(lcm_a,A[i])
 
ans = 0
for i in range(N):
    ans += lcm_a//A[i]

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

Submission status: Runtime Error

Solution code:
from fractions import gcd


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


MOD = 1000000007

N = int(input())

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

lcm_ = 1
for a in A:
    lcm_ = lcm(lcm_, a)

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

ans %= MOD
print(int(ans))

Submission status: Runtime Error

Solution code:
import math


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


MOD = 1000000007

N = int(input())

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

lcm_ = 1
for a in A:
    lcm_ = lcm(lcm_, a)

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

ans %= MOD
print(int(ans))

Submission status: Runtime Error

Solution code:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
const int N=1e4+4;
const int V=1e6+4; 
int n;
int a[N];
int mx[V];
int sg[V];
ll ans;
int prime[V],tot;
bool vis[V],has[V];
vector<int> v;
inline void linear_shaker(int n) {
	vis[1]=true;
	for (register int i=2;i<=n;++i) {
		if (!vis[i]) prime[++tot]=i;
		for (int j=1;j<=tot&&i*prime[j]<=n;++j) {
			vis[i*prime[j]]=true;
			if (i%prime[j]==0) break;
		}
	}
}
inline int read() {
	int x=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x;
}
inline void smax(int &x,int y) {
	x=x>y?x:y;
}
inline void get(int x) {
	for (int i=1;i<=tot;++i) {
		while (x%prime[i]==0) {
			if (!has[prime[i]]) {
				has[prime[i]]=true;
				v.push_back(prime[i]);
			}
			x/=prime[i];
			++sg[prime[i]];
			smax(mx[prime[i]],sg[prime[i]]);
		}
		if (x==1) break;
	}
}
inline void rec(int x) {
	for (int i=1;i<=tot;++i) {
		while (x%prime[i]==0) {
			x/=prime[i];
			--sg[prime[i]];
		}
		if (x==1) break;
	}
}
inline void ask(int x) {
	ll cur=1;
	for (int i=0;i<v.size();++i) {
		int d=mx[v[i]]-sg[v[i]];
		while (d--) (cur*=1ll*v[i])%=MOD;
	}
	(ans+=cur)%=MOD;
}
int main() {
//	freopen("in3.txt","r",stdin);
	linear_shaker(N-4);
	int n=read();
	for (register int i=1;i<=n;++i) {
		a[i]=read();
		get(a[i]);
		rec(a[i]);
	}
	for (register int i=1;i<=n;++i) {
		get(a[i]);
		ask(a[i]);
		rec(a[i]);
	}
	printf("%lld\n",ans);
	return 0;
}

Submission status: Runtime Error

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

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

def main():
    MOD=1000000007
    n=int(input())
    M=1
    a=input().split()
    for i in range(0,n):
        a[i]=int(a[i])
        M=lcm(M,a[i])
    ans=0
    for i in range(0,n):
        ans+=M/a[i]
        ans%=MOD
    print(int(ans))

main()

Submission status: Runtime Error

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

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

def main():
    MOD=1000000007
    n=int(input())
    M=int(1)
    a=input().split()
    for i in range(0,n):
        a[i]=int(a[i])
        M=lcm(M,a[i])
    ans=0
    for i in range(0,n):
        ans+=M/a[i]
        ans%=MOD
    print(int(ans))

main()

Submission status: Runtime Error

Solution code:
#

import sys
input=sys.stdin.readline

MOD=10**9+7
kl = [0]*(10**6+1)

            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    for j in range(N):
        n=A[j]
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n/=i
                    cnt+=1
                if kl[i]<cnt:
                    kl[i]=cnt
        if n!=1:
            if kl[n]<1:
                kl[n]=1
                
    lcm=1
    for i in range(2,10**6+1):
        lcm*=pow(i, kl[i], MOD)

    modsum=0
    for i in range(N):
        modsum+=pow(A[i],MOD-2,MOD)

    ans = lcm*modsum%MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
#

import sys
input=sys.stdin.readline

MOD=10**9+7
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    kl=[0]*(10**6+1)
    for j in range(N):
        n=A[j]
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n/=i
                    cnt+=1
                if kl[i]<cnt:
                    kl[i]=cnt
        if n!=1:
            if kl[n]<1:
                kl[n]=1
                
    lcm=1
    for i in range(2,10**6+1):
        lcm*=pow(i, kl[i], MOD)
    ans=0
    for i in range(N):
        ans+=pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(lcm*ans%MOD)
    
    
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
#

import sys
input=sys.stdin.readline

MOD=10**9+7
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    kl=[0]*(10**6+1)
    for j in range(N):
        n=A[j]
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n/=i
                    cnt+=1
                if kl[i]<cnt:
                    kl[i]=cnt
        if n!=1:
            if kl[n]<1:
                kl[n]=1
                
    lcm=1
    for i in range(2,10**6+1):
        lcm*=i**kl[i]
        lcm%=MOD
    ans=0
    for i in range(N):
        ans+=lcm*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
#

import sys
input=sys.stdin.readline

MOD=10**9+7
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    kl={}
    for j in range(N):
        n=A[j]
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n/=i
                    cnt+=1
                if kl.get(i,"a")=="a" or kl[i]<cnt:
                    kl[i]=cnt
        if n!=1:
            if kl.get(n,"a")=="a" or kl[n]<cnt:
                kl[n]=cnt
                
    lcm=1
    for a,b in kl.items():
        lcm*=a**b
        lcm%=MOD
    ans=0
    for i in range(N):
        ans+=lcm*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

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

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

g = fractions.gcd(a[0],a[1]) #最大公約数
l = a[0]*a[1]//g #最小公倍数
mod = 10**9+7

if n == 2:
    print(l//a[0] + l//a[1])
    exit()
else:
    #全部の最小公倍数
    for i in range(n-2):
        g = a[i+1]*l//g
        l = l*a[i+2]//fractions.gcd(g,a[i+2])

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

Submission status: Runtime Error

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

g = fractions.gcd(a[0],a[1]) #最大公約数
l = a[0]*a[1]//g #最小公倍数
mod = 10**9+7

if n == 2:
    print(l//a[0] + l//a[1])
    exit()
else:
    #全部の最小公倍数
    for i in range(n-2):
        g = a[i]*a[i+1]//g
        l = l*a[i+2]//fractions.gcd(g,a[i+2])

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

Submission status: Runtime Error

Solution code:
import fractions
n = int(input())
a = list(map(int,input().split()))
g = fractions.gcd(a[0],a[1])
l = a[0]*a[1]//g
for i in range(n-2):
    g = l*a[i+2]//fractions.gcd(l,a[i+2])

ans = 0
for i in range(n):
    ans += g // a[i]
    ans % (10**9+7)
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
g = math.gcd(a[0],a[1])
l = a[0]*a[1]//g
for i in range(n-2):
    g = l*a[i+2]//math.gcd(l,a[i+2])

ans = 0
for i in range(n):
    ans += g // a[i]
    ans % (10**9+7)
print(ans%(10**9+7))