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:
from functools import reduce

MOD = 10 ** 9 + 7

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

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

def lcmArr(a):
    return reduce(getLcm, a)

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

lcm = lcmArr(a)
lcm %= MOD
ret = 0
for val in a:
    ret += lcm * pow(val, MOD - 2, MOD)
    ret %= MOD
print(ret)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
lcm = a[0]

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

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

N,*A = map(int,read().split())

MOD = 10 ** 9 + 7

lcm = reduce(lambda x,y: x*y//gcd(x,y), A)

answer = sum(lcm//x for x in A)
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = np.array(read().split(),np.int64)

MOD = 10 ** 9 + 7

U = 10 ** 6 + 10
is_prime = np.zeros(U, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3,U,2):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::p+p] = 0

M = 10 ** 3
small_primes = np.where(is_prime[:M])[0].tolist()

B = A.copy()
lcm = 1
for p in small_primes:
    e = 0
    while np.any(A % p == 0):
        e += 1
        A[A % p ==0] //= p
    lcm *= p**e
    lcm %= MOD

for x in set(A.tolist()):
    lcm *= x
    lcm %= MOD

answer = sum(pow(x, MOD-2, MOD) for x in B.tolist()) % MOD
answer *= lcm
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

N,*A = map(int,read().split())

MOD = 10 ** 9 + 7

lcm = reduce(lambda x,y: y//gcd(x,y)*x, A)
lcm %= MOD

coef = sum(pow(x, MOD-2, MOD) for x in A)
answer = lcm * coef % MOD

print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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


def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)

class InverseTable:
    __slots__ = ['In', 'fac', 'Ifac']

    def __init__(self, mod, maxnum):
        self.In = [0, 1]; self.fac = [1, 1]; self.Ifac = [1, 1]
        for i in range( 2, maxnum + 1 ):
            self.fac.append( ( self.fac[-1] * i ) % mod )
            self.In.append( ( -self.In[mod % i] * (mod//i) ) % mod )
            self.Ifac.append( (self.Ifac[-1] * self.In[-1]) % mod )
        
    def cmb(self, n, r):
        if ( r<0 or r>n ): return 0
        r = min(r, n-r)
        return self.fac[n] * self.Ifac[r] * self.Ifac[n-r] % mod

it = InverseTable(mod, 10**6)

for ai in A:
    pro=lcm(pro,ai)
for ai in A:
    ans+=it.In[ai]
    ans%=mod
print((pro*ans)%mod)

# pro2=1
# for ai in A:
#     pro2=(pro2*ai)%mod
#     pro=gcd(pro,ai)
# for ai in A:
#     count+=pro//ai
#     count%=mod
# print(count)

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
mod = 10**9 +7
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
cur_prime = {}
for i in range(N):
    S = factorization(A[i])
    for j in range(len(S)):
        if S[j][0] not in cur_prime:
            cur_prime[S[j][0]] = S[j][1]
        else:
            cur_prime[S[j][0]] = max(S[j][1],cur_prime[S[j][0]])
A_lcm = 1
key = list(cur_prime.keys())
value = list(cur_prime.values())
for i in range(len(key)):
    for j in range(value[i]):
        A_lcm *= key[i]
        A_lcm %= mod
ans = 0
for i in range(N):
    ans += A_lcm*pow(A[i],mod-2,mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
P = [1 for _ in range(10**6+1)]
P[0]=0
P[1]=0
for i in range(2,10**3+1):
    for j in range(i*i,10**6+1,i):
        P[j] = 0
Q = {}
for i in range(2,10**6+1):
    if P[i]==1:
        Q[i] = 0
Q1 = sorted(list(Q.keys()))
p = 10**9+7
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    a = A[i]
    for b in Q1:
        if a%b==0:
            cnt = 0
            while a%b==0:
                a = a//b
                cnt += 1
            Q[b] = max(Q[b],cnt)
            if a==1:break
        elif b>1000 and a>1:
            Q[a] = max(Q[a],1)
            break
        else:continue
lcmA = 1
for b in Q:
    cnt = 1
    for i in range(Q[b]):
        cnt = (cnt*b)%p
    lcmA = (lcmA*cnt)%p
tot = 0
for i in range(N):
    tot = (tot+lcmA*pow(A[i],p-2))%p
print(tot)

Submission status: Accepted

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

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

def lcm(x, y):
    return x/gcd(x, y)*y
 
l = A[0]
for a in A:
    l = lcm(l, a)
 
res = 0
for a in A:
    res = (res + (l * pow(a, MOD - 2, MOD)) % MOD) % MOD
 
print(res)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from functools import reduce

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

def gcd(a, b):
    # 大きい方を被除数、小さい方を除数とする
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend

    # 最大公約数を見つけるまで繰り返す
    while dividend % divider != 0:
        # 除算を行い、その除数を次回の被除数、剰余を次回の除数として処理を繰り返す
        r = dividend % divider
        dividend = divider
        divider = r

    # 一方がもう一方を割り切れた時点で、その除数を最大公約数とみなせる
    return divider


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

def modinv(x):
    return pow(x, mod-2, mod)

L = reduce(lcm, a)

for i in range(n):
    # ans += (L // a[i])
    ans += L * modinv(a[i])

print(ans % mod)

Submission status: Accepted

Solution code:
from functools import reduce

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

def gcd(a, b):
    # 大きい方を被除数、小さい方を除数とする
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend

    # 最大公約数を見つけるまで繰り返す
    while dividend % divider != 0:
        # 除算を行い、その除数を次回の被除数、剰余を次回の除数として処理を繰り返す
        r = dividend % divider
        dividend = divider
        divider = r

    # 一方がもう一方を割り切れた時点で、その除数を最大公約数とみなせる
    return divider


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

def modinv(x):
    return pow(x, mod-2, mod)

b = list(set(a))
# for i in range(n):

# L = reduce(lcm, a)
L = reduce(lcm, b)

# print(L)

for i in range(n):
    # ans += (L // a[i])
    ans += L * modinv(a[i])

print(ans % mod)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read

from fractions import gcd

N,*A = map(int,read().split())

lcm = 1
answer = 0
for x in A:
  n = x//gcd(lcm,x)
  lcm *= n
  answer *= n
  answer += lcm//x
  
answer %= (10**9 + 7)
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

N,*A = map(int,read().split())

MOD = 10 ** 9 + 7

lcm = 1
answer = 0
for x in A:
  n = x//gcd(lcm,x)
  lcm *= n
  answer *= n
  answer += lcm//x
  
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

N,*A = map(int,read().split())

MOD = 10 ** 9 + 7

lcm = 1
answer = 0
for x in A:
  n = x//gcd(lcm,x)
  lcm *= n
  answer *= n 
  answer %= MOD
  answer += lcm//x % MOD
  
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
import fractions 

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

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

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

ret = 0
for a in A:
    ret += (_lcm // a)

print(ret%MODE)

Submission status: Accepted

Solution code:
import fractions

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    prev_lc = 1
    ans = 0
    for i in A:
        lc = lcm(prev_lc, i)
        ans = ans * (lc // prev_lc) + lc // i
        prev_lc = lc
    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
if n == 1:
	print(1)
else:
	lcm = a[0] * a[1] // gcd(a[0], a[1])
	for x in a[2:]:
		lcm = lcm * x // gcd(lcm, x)
	lcm %= MOD
	ans = 0
	for x in a:
		ans += lcm * pow(x, MOD-2, MOD)
		ans %= MOD
	print(ans)

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
l = 1
ans = 0
for i in a:
  l = lcm(l, i)

for i in a:
  ans += l//i

print(ans % 1000000007)

Submission status: Accepted

Solution code:
from functools import reduce

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

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

def lcm_list(A): return reduce(lcm, A)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
L = lcm_list(A)
ans = 0
for a in A:
    ans += L // a
print(ans % MOD)

Submission status: Accepted

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

N = pow(10,9)+7
def gcd(a,b):
    if a==0:return b
    return gcd(b%a,a)

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

hcm = arr[0]
for i in range(1,n):
    hcm = lcm(hcm,arr[i])

res = 0
for num in arr:
    res += (hcm//num)
    

print(res%N)

Submission status: Accepted

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

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

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

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
L = lcm_list(A)
ans = 0
for a in A:
    ans += L // a
print(ans % MOD)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

def gcd(x, y):
  while y: x, y = y, x % y
  return x

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

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

answer = 0
for a in A:
  answer += tmp * pow(a, MOD - 2, MOD)
  
print(answer % MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

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

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

LCM = 1
for v in a:
    LCM = lcm(LCM,v)

LCM %= MOD

def pow(a,n,mod):
    ret = 1
    tmp = a
    while n:
        if n & 1:
            ret *= tmp
            ret %= mod
        tmp *= tmp
        tmp %= mod
        n >>= 1
    return ret

def inv(a,mod):
    return pow(a,mod-2,mod)


ans = 0
for v in a:
    ans += LCM * inv(v,MOD)
    ans %= MOD;

print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

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

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

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

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

ans = 0
for i in a:
    ans += g // i

print(ans % mod)

Submission status: Accepted

Solution code:
import fractions


mod = 10 ** 9 + 7

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


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

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

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

Submission status: Accepted

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

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

INF=10**9+7

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

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

ans=0
for a in A:
    ans+=(temp//a)

print(ans%INF)

Submission status: Accepted

Solution code:
from fractions import gcd
P = 10**9 + 7
N = 1000001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
n=int(input())
a=list(map(int,input().split()))
lcm=a[0]
mod=10**9+7
for i in range(1,n):
  lcm=(lcm//gcd(lcm,a[i]))*a[i]
ans=0
lcm%=mod
for i in range(n):
  ans=(ans+lcm*inv[a[i]])%mod
print(ans%mod)

Submission status: Accepted

Solution code:
#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)
B = int(input())
L = list(map(int, input().split()))
d=L[0]
mod=1000000007
for i in range(B):
  d=lcm(d,L[i])
ans=0
for i in range(B):
  ans+=d//L[i]
print(ans%mod)

Submission status: Accepted

Solution code:
def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)


def LCM(a: int, b: int) -> int:
    return a * b // GCD(a, b)


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

MAX_a = max(a)
iinv = [1] * (MAX_a + 1)
for i in range(2, MAX_a + 1):
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD

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

lcm %= MOD

ans = 0
for i in range(n):
    ans += lcm * iinv[a[i]]
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
L = A[0]
for a in A[1:]:
    L = L * a // gcd(L, a)

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

print(ans%1000000007)

Submission status: Accepted

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

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

lcm = lcm_list(inp_list)

ans = 0

for i in inp_list:
    ans += lcm // i


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

Submission status: Accepted

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

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

lcm = lcm_list(inp_list)

ans = 0
mod = 10**9+7

for i in inp_list:
    ans += lcm // i



print(ans % mod)

Submission status: Accepted

Solution code:
import functools
import fractions
MOD = 10**9+7


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


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


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

    l = lcm(x)
    ans = 0
    for i in range(n):
        ans += l // x[i]

    print(ans % MOD)


main()

Submission status: Accepted

Solution code:
#!python3

from fractions import gcd
iim = lambda: map(int, input().rstrip().split())

def factor(n):
    ans = []
    i = 0
    while n & 1 == 0:
        n >>= 1
        i += 1

    if i > 0:
        ans.append((2, i))

    for i in range(3, int(n**.5) +1, 2):
        x, y = divmod(n, i)

        if y == 0:
            j = 1
            x1 = x
            while True:
                x1, y = divmod(x, i)
                if y == 0:
                    x = x1
                    j += 1
                else:
                    ans.append((i, j))
                    break
            n = x

    if n > 1:
        ans.append((n, 1))
    return ans

def resolve():
    N = int(input())
    A = list(iim())
    mod = 10**9 + 7

    lcm = 1
    #c2 = dict()
    #for a in A:
    #    for n, m in factor(a):
    #        if n in c2:
    #            c2[n] = max(c2[n], m)
    #        else:
    #            c2[n] = m

    #lcm = 1
    #for n, m in c2.items():
    #    lcm *= n**m%mod % mod
    for a in A:
        lcm = lcm // gcd(lcm, a) * a
    lcm %= mod

    s = 0
    for a in A:
        s += lcm*pow(a, mod-2, mod)%mod
        s %= mod

    print(s)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def factor(n):
    ans = []
    i = 0
    while n & 1 == 0:
        n >>= 1
        i += 1

    if i > 0:
        ans.append((2, i))

    for i in range(3, int(n**.5) +1, 2):
        x, y = divmod(n, i)

        if y == 0:
            j = 1
            x1 = x
            while True:
                x1, y = divmod(x, i)
                if y == 0:
                    x = x1
                    j += 1
                else:
                    ans.append((i, j))
                    break
            n = x

    if n > 1:
        ans.append((n, 1))
    return ans

def resolve():
    N = int(input())
    A = list(iim())
    mod = 10**9 + 7

    c = 1
    c2 = dict()
    for a in A:
        for n, m in factor(a):
            if n in c2:
                c2[n] = max(c2[n], m)
            else:
                c2[n] = m

    c3 = 1
    for n, m in c2.items():
        c3 *= n**m%mod % mod

    s = 0
    for a in A:
        s += c3*pow(a, mod-2, mod)%mod
        s %= mod

    print(s)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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)

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

N = int(input())
A = list(map(int, input().split()))
answer = 0
mod = 10**9 + 7
LCM = lcm(*A)

for i in range(N):
    answer += LCM // A[i]

print(answer % mod)

Submission status: Accepted

Solution code:
from fractions import gcd 

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

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

lcm_number=1

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

count=0
for i in range(N):
   count+=lcm_number//A[i]

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

Submission status: Accepted

Solution code:
# テストケースによってTLEするのか確認するために再提出
import fractions
from functools import reduce
 
MOD = 10**9 + 7
 
def main():
    N = int(input())
    A = list(map(int, input().split()))
 
    def lcm_base(x, y):
        return (x * y) // fractions.gcd(x, y)
 
    def lcm_list(numbers):
        return reduce(lcm_base, numbers, 1)
 
    l = lcm_list(A)
    ans = 0
 
    for x in A:
        ans += l // x
        
    print(ans % MOD)
 
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

def mul(C1, C2):
    return C1 + C2

def div(C1, C2):
    return C1 - C2

def gcd(C1, C2):
    return C1 & C2

def lcm(C1, C2):
    for k, v in C2.items():
        C1[k] = max(C1[k], v)
    return C1
    # return C1 | C2

N = INT()
A = LIST()

# 素因数の状態で全体のLCMを出す
A2 = [factorize(a) for a in A]
l2 = Counter()
for a in A2:
    l2 = lcm(l2, a)

# 通常の値に戻す
l = 1
for k, v in l2.items():
    l *= pow(k, v, MOD)
    l %= MOD

ans = 0
for a in A:
    ans += fermat(l, a, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

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

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

md = 10 ** 9 + 7
def main():
    n = II()
    aa = LI()
    l = 1
    for a in aa:
        l = lcm(l, a)
    l = mint(l)
    ans = sum(l / a for a in aa)
    print(ans)

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

def mul(C1, C2):
    return C1 + C2

def div(C1, C2):
    return C1 - C2

def gcd(C1, C2):
    return C1 & C2

def lcm(C1, C2):
    return C1 | C2

N = INT()
A = LIST()

# 素因数の状態で全体のLCMを出す
A2 = [factorize(a) for a in A]
l2 = Counter()
for a in A2:
    for k, v in a.items():
        l2[k] = max(l2[k], v)

# 通常の値に戻す
l = 1
for k, v in l2.items():
    l *= pow(k, v, MOD)
    l %= MOD

ans = 0
for a in A:
    ans += fermat(l, a, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

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

mod = 10 ** 9 + 7
n = int(input())
l = [int(i) for i in input().split()]
product  = 1
for i in l:
    product = lcm(product,i)

ans = 0 
for i in l:
    ans += product // i
ans %= mod
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd (a, b)
def lcm_n(nums):
    return functools.reduce(lcm, nums)

n = ni()
a = na()
a_lcm = lcm_n(a)
ans = 0
for ai in a:
    ans += a_lcm // ai
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd #直して
n = int(input())
a = list(map(int, input().split()))

mod = 10**9+7
l = 1
for i in range(n):
    l = a[i]*l // gcd(l, a[i])


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

d = 0
for i in range(n):
    d += modinv(a[i])

print((l*d) % mod)

Submission status: Accepted

Solution code:
from fractions import gcd #直して
n = int(input())
a = list(map(int, input().split()))

mod = 10**9+7
l = 1
for i in range(n):
    l = a[i] // gcd(l, a[i]) * l
    

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

d = 0
for i in range(n):
    d += modinv(a[i])

print((l*d) % mod)

Submission status: Accepted

Solution code:
def gcd(a,b):
    while b!=0:
        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()))
a_lcm=A[0]
Mod=10**9+7

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

#a_lcm%=Mod

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

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

#リストの最小公倍数
def lcmlist(lista):
    if len(lista) == 1:
        return lista[0]
    else:
        from functools import reduce
        return reduce(lcm,lista)
LCM = lcmlist(A)
ans = 0
for i in A:
    ans += LCM//i
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
from functools import reduce

MOD = 10 ** 9 + 7

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

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

n, *A = map(int, sys.stdin.read().split())

def main():
    l = reduce(lcm, A, 1) % MOD

    res = 0
    for a in A:
        res += l * pow(a, MOD-2, MOD) % MOD
        res %= MOD
    
    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
def gcd(a,b):
    while b!=0:
        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()))
a_lcm=A[0]
Mod=10**9+7

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

a_lcm%=Mod

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

Submission status: Accepted

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

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


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

MOD = 10**9+7
ans = 0
t = 1
for i in l:
    t = lcm(t,i)

for i in l:
    ans +=t//i
print(ans%MOD)

Submission status: Accepted

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

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

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

n = int(input())
A = list(map(int, input().split()))
k = lcm_list(A)
r = 0
ln = list(range(n))
for i in ln:
    r += k//A[i]
print(r%(10**9+7))

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
sieve=[1]*10001
i=2
while i*i<=10001:
    if sieve[i]:
        for j in range(i+i,10001,i):
            sieve[j]=0
        
    i+=1    
lol=[]
for i in range(2,10001):
    if sieve[i]:
        lol.append(i)
mod=10**9+7
def gcd(x,y):
    if x==0:
        return y
    return gcd(y%x,x)    
x=int(input())
a=list(map(int,input().split()))
d=defaultdict(int)
for i in a:
    k=0

    while lol[k]*lol[k]<=i:
        c=0
        #print("AScasc",i)
        j=lol[k]
        if i%j==0:    
            while i%j==0:
                i//=j
                c+=1
            d[j]=max(c,d[j])    
        k+=1    
    if i>=2:
        c=1
        d[i]=max(c,d[i])
        
y=0
s=d.keys()
#print(s,d)
z=1
for i in s:
    z*=pow(i,d[i])
for i in a:
    y+=((z%mod)*pow(i,mod-2,mod))%mod
print(y%mod)

Submission status: Accepted

Solution code:
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

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

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

MOD = 10 ** 9 + 7

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

c = p[0]
for x in p[1:]:
    c = c * x // gcd(c, x)

ans = 0
for x in p:
    ans += c // x

print(ans % MOD)

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd
    from functools import reduce
    mod=1000000000+7
    n=int(input())
    a=[int(i) for i in input().split()]
    l=reduce(lambda x,y:x//gcd(x,y)*y,a)
    ans=sum(map(lambda x:l//x,a))
    print(ans%mod)
main()

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd
    from functools import reduce
    def lcm(c,d):
        return c//gcd(c,d)*d
    mod=1000000000+7
    n=int(input())
    a=[int(i) for i in input().split()]
    l=reduce(lcm,a)
    ans=sum(map(lambda x:l//x,a))
    print(ans%mod)
main()

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd
    from functools import reduce
    def lcm(c,d):
        return c//gcd(c,d)*d
    mod=10**9+7
    n=int(input())
    a=[int(i) for i in input().split()]
    l=reduce(lcm,a)
    ans=sum(map(lambda x:l//x,a))
    print(ans%mod)
main()