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: Accepted

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:
                for q in range(p * p, n + 1, 2 * p):
                    if self.table[q] == q:
                        self.table[q] = p

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

    def prime_factors(self, x):             # 素因数分解 O(logN)  (試し割りだとO(sqrt(N)))
        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):             # 素因数分解（個数のリスト） O(logN)
        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, mod=None):        # n個の最大公約数　X:n個のリスト  (O((logN)^2))
        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, mod)
        if mod == None:
            return res
        else:
            return res % mod

    def prime_lcm(self, X, mod=None):       # n個の最小公倍数　X:n個のリスト  (O((logN)^2))
        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


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


int(input())
N = 10**6 + 1
table = PrimeFactor(N)
A = list(map(int, input().split()))
MOD = 10**9+7
temp = table.prime_lcm(A,MOD)
res = 0
for a in A:
    res += temp*pow(a,MOD-2,MOD)
print(res%MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

import collections
lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])
#import math
#for v in a:
#    lcm = (lcm // math.gcd(lcm, v)) * v

ans = 0
for v in a:
    ans = ans + (lcm // v)
    #ans = (ans + (lcm // v)) % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

#import collections
#lcm_pf = collections.defaultdict(int)
#for i, v in enumerate(a):
#    j = 2
#    pf = {}
#    while j ** 2 <= v:
#        ext = 0
#        while v % j == 0:
#            ext += 1
#            v //= j
#        if ext:
#            pf[j] = ext
#            lcm_pf[j] = max(lcm_pf[j], ext)
#        j += 1
#    if v != 1:
#        pf[v] = 1
#        lcm_pf[v] = max(lcm_pf[v], 1)
#for p in lcm_pf:
#    lcm = lcm * (p ** lcm_pf[p])
import math
for v in a:
    lcm = (lcm // math.gcd(lcm, v)) * v

ans = 0
for v in a:
    ans = ans + (lcm // v)
    #ans = (ans + (lcm // v)) % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

ans = 0
for v in a:
    ans = ans + (lcm // v)
print(ans % MOD)

Submission status: Accepted

Solution code:
import math

mod = 10**9+7
N = int(input())
A = list(map(int, input().split()))
ans = 1
lcm = A[0]
for i in range(1, N):
    a = A[i]
    b = lcm
    gcd = math.gcd(a, b)
    lcm = (a*b)//gcd
    ans *= lcm//b
    ans += lcm//a
    ans %= mod
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
L = A[0]
for i in range(1,N):
    g = math.gcd(L,A[i])
    L = L*A[i]//g
ans = 0
L %= MOD
for i in range(N):
    ans += (L*pow(A[i],MOD-2,MOD))
    ans %= MOD
print(ans)

Submission status: Accepted

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

N = int(input())
A = list(map(int,input().split()))
A.sort()
MAX = max(A[-1],2)

C = [0 for _ in range(MAX+1)]

for a in A:
  C[a] += 1

ans = 1
P = [1 for _ in range(MAX+1)] #素数かどうか
P[0] = 0
P[1] = 0
S = [0 for _ in range(MAX+1)] #最小公倍数の素因数分解したもの
for i in range(MAX+1):
  #素数でないなら以下の手順を行わない
  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: Accepted

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

Submission status: Accepted

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+2 #書き換え
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: Accepted

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

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

p = 1000000007

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

k %= p

ans = 0
for i in range(n):
    ans += k * pow(a[i],p-2,p)
    ans %= p

print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
def lcm(x,y):
  return x*y//math.gcd(x,y)
l=reduce(lcm,a)
b=list(map(lambda x:l//x,a))
m=10**9+7
print(sum(b)%m)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

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

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

def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

ans = 0
for a in A:
    ans += my_pow(a, MOD - 2, MOD)
print((ans * l)% MOD)

Submission status: Accepted

Solution code:
def pow_r(x, n, P):
  if n == 0:
    return 1
  if n % 2 == 0:
    return pow_r(x ** 2 % P, n // 2, P)
  else:
    return x * pow_r(x ** 2 % P, n // 2, P) 

from fractions import gcd

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

rlt = 0
for a in As:
  rlt += lcm*pow_r(a, P-2, P) % P
  rlt %= P
print(rlt)

Submission status: Accepted

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

########################################################################################################################################################################
# Verified by
# https://yukicoder.me/problems/no/979

## return prime factors of N as dictionary {prime p:power of p}
## within 2 sec for N = 2*10**20+7
def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret

## return divisors of n as list
def divisor(n):
    div=[1]
    for i,j in primeFactor(n).items():
        div=[(i**k)*d for d in div for k in range(j+1)]
    return div

## 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):
    M=int(N**0.5)
    seachList=[i for i in range(2,N+1)]
    primes=[]
    while seachList:
        if seachList[0]>M:
            break
        primes.append(seachList[0])
        tmp=seachList[0]
        seachList=[i for i in seachList if i%tmp!=0]
    return primes+seachList


## retrun LCM of numbers in list b
## within 2sec for no of B = 10*5  and  Bi < 10**6
def LCM(b,mo=10**9+7):
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

show_flg=False
show_flg=True


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

L=LCM(a)

ans=0
for i in range(n):
    ans+=L*pow(a[i],mo-2,mo)
    ans%=mo

print(ans)

Submission status: Accepted

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**3
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
L=1
for i,j in l.items():
    L*=i**j
    L%=mo

ans=0
for i in range(n):
    ans+=L*pow(a[i],mo-2,mo)
    ans%=mo

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import sys


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


input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
LCM = 1
ans = 0
MOD = 1000000007
for x in A:
  LCM = lcm(LCM, x)
for x in A:
  ans += LCM // x

print(ans%MOD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = 10**9 + 7


def fact(N):
    res = {}
    tmp = N
    for i in range(2, int(N ** 0.5 + 1) + 1):
        cnt = 0
        while tmp % i == 0:
            cnt += 1
            tmp //= i
        if cnt > 0:
            res[i] = cnt
    if tmp != 1:
        res[tmp] = 1
    if res == {}:
        res[N] = 1
    return res


def modpow(n, p):
    res = 1
    while p > 0:
        if p & 1:
            res = res * n % MOD
        n = n * n % MOD
        p >>= 1
    return res


def modinv(n):
    b, u, v = MOD, 1, 0
    while b > 0:
        t = n // b
        n -= t * b
        n, b = b, n
        u -= t * v
        u, v = v, u
    u %= MOD
    if u < 0:
        u += MOD
    return u


def solve():
    N = Scanner.int()
    A = Scanner.map_int()
    L = defaultdict(int)
    for i in range(N):
        for k, v in fact(A[i]).items():
            L[k] = max(L[k], v)
    lcm = 1
    for k, v in L.items():
        lcm *= modpow(k, v)
        lcm %= MOD
    ans = 0
    for i in range(N):
        x = lcm * modinv(A[i]) % MOD
        ans += x
        ans %= MOD
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


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


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


MOD = 10**9 + 7


def solve():
    N = Scanner.int()
    A = Scanner.map_int()
    l = 1
    for a in A:
        l = lcm(a, l)
    ans = 0
    for a in A:
        ans += l // a
    ans %= MOD
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

from math import gcd
from functools import reduce
def resolve():
    def lcm_base(x, y):
        return (x * y) // gcd(x, y)

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

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

    num = lcm_list(A) % MOD
    ans = 0
    for a in A:
        ans += (num * pow(a, MOD - 2, MOD)) % MOD
    ans %= MOD

    print(ans)
    
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]



# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    primes_a = {}
    for a in A:
        prime_a = prime_fact(a)
        primes_a[a] = prime_a
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    ans = 0
    l = 1
    for p, n in L.items():
        l = l * pow(p, n, MOD) % MOD

    for i, a in enumerate(A):
        ans += l * pow(a, MOD-2, MOD) % MOD
    print(ans % MOD)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        for j in range(root+1):
            if n % i == 0 and n != 0:
                cnt += 1
                n = n // i
            else:
                break
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    primes_a = {}
    for a in A:
        prime_a = prime_fact(a)
        primes_a[a] = prime_a
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    ans = 0
    l = 1
    for p, n in L.items():
        l = l * pow(p, n, MOD) % MOD

    for i, a in enumerate(A):
        ans += l * pow(a, MOD-2, MOD) % MOD
    print(ans % MOD)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # 答えは sum(lcm(A) / A)
    L = 1
    for a in A:
        L = L * a // math.gcd(L, a)
    ans = 0
    for a in A:
        ans += L * pow(a, MOD - 2, MOD)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
def f(x):
  if x==1:
    return dict()
  y=x
  r=dict()
  for i in range(2,int(x**0.5)+1):
    if y%i==0:
      r[i]=0
      while y%i==0:
        r[i]+=1
        y=y//i
    if y==1:
      break
  if y!=1:
    r[y]=1
  return r

B=[f(A[i]) for i in range(N)]
def g(X):
  if len(X)==1:
    return X[0]
  a,b=g(X[:len(X)//2]),g(X[len(X)//2:])
  c=list(set(a.keys())|set(b.keys()))
  for i in range(len(c)):
    a[c[i]]=max(a.get(c[i],0),b.get(c[i],0))
  return a

G=g(B)
X=1
mod=10**9+7
P=0
Y=list(G.keys())
for i in range(len(Y)):
  X=X*pow(Y[i],G[Y[i]],mod)%mod
for i in range(N):
  P=(P+X*pow(A[i],mod-2,mod))%mod
print(P)

Submission status: Accepted

Solution code:
# エラトステネスの篩, フェルマーの小定理
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        c = 0
        while n % p == 0:
            n //= p
            c += 1
        result.append((p, c))
    return result


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

m = 1000000007

prime_table = make_prime_table(10 ** 6)

lcm_factors = {}
for a in A:
    for p, c in prime_factorize(a):
        if p not in lcm_factors or lcm_factors[p] < c:
            lcm_factors[p] = c

lcm = 1
for p in lcm_factors:
    lcm *= pow(p, lcm_factors[p], m)
    lcm %= m

result = 0
for i in range(N):
    result += lcm * pow(A[i], -1, m)
    result %= m
print(result)

Submission status: Accepted

Solution code:
# エラトステネスの篩, フェルマーの小定理
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        c = 0
        while n % p == 0:
            n //= p
            c += 1
        result.append((p, c))
    return result


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

m = 1000000007

prime_table = make_prime_table(10 ** 6)

lcm_factors = {}
for a in A:
    for p, c in prime_factorize(a):
        if p not in lcm_factors or lcm_factors[p] < c:
            lcm_factors[p] = c

lcm = 1
for p in lcm_factors:
    lcm *= pow(p, lcm_factors[p], m)
    lcm %= m

result = 0
for i in range(N):
    result += lcm * pow(A[i], m - 2, m)
    result %= m
print(result)