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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@lru_cache(maxsize=None)
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    if b == 0:
        return a
    return gcd(b, a % b)

@mt
def slv(N, A):
    m = 10**9+7
    l = 1
    for a in A:
        l = a * l // gcd(a, l)

    l %= m
    M = Mod(10**9+7)
    ans = 0
    for a in A:
        ans = M.add(ans, M.div(l, a))

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 10000
    # A = [random.randint(1, 10**6) for _ in range(N)]
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

s = 0
for i in range(n):
    s += lcm // a[i]

ans = s % 1000000007
print(ans)

Submission status: Accepted

Solution code:
import fractions
n=int(input())
a=list(map(int,input().split()))
l=1
for i in a:
    m=l
    l=fractions.gcd(m,i)
    l=i*m//l
p=0
for i in a:
    p+=l//i
print(p%(10**9+7))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

MOD=10**9+7

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

N=int(input())
A=list(map(int, input().split()))
ans=1
lcm=A[0]
for i in range(1, N):
  prelcm=lcm
  lcm=lcm_base(prelcm, A[i])
  ans=ans*(lcm//prelcm)+lcm//A[i]
print(ans%MOD)

Submission status: Accepted

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

mod = 10**9+7
mm = a[0]

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

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

for i in range(1,n):
    mm = lcs(mm,a[i])

ans = 0
for i in range(n):
    ans += mm//a[i]

print(ans%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import fractions as f

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    #lcm=np.lcm.reduce(A)
    lcm=A[0]
    for i in range(1,N):
        lcm=lcm*A[i]//f.gcd(lcm,A[i])

    ans=0
    for i in range(N):
        ans+=lcm//A[i]
    print(ans%MOD)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

def calc_lcm(a):
    ans = a[0]
    N = len(a)
    for i in range(1, N):
        ans = ans * a[i] // fractions.gcd(ans, a[i])
    return ans

N = int(raw_input())
a = map(int, raw_input().split())

LCM = calc_lcm(a)

ans = 0
for i in range(N):
    ans = ans + LCM/a[i]

print ans%(10**9+7)

Submission status: Accepted

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

def gcd(a,b):
    return gcd(b,a%b) if b != 0 else a
mod = 10**9+7

def lcm(a,b):
    return a*b%mod * pow(gcd(a,b),mod-2,mod) % mod

num = {}

for i in range(n):
    nown=a[i]
    tmp = {}
    for i in range(2,int(nown**0.5) + 5):
        while nown % i ==0:
            nown//=i
            if(i in tmp):
                tmp[i]+=1
            else:
                tmp[i] = 1
    if nown != 1:
        tmp[nown] = 1    
    for key in tmp:
        if (key in num):
            num[key] = max(num[key],tmp[key])
        else:
            num[key] = tmp[key]

kobai = 1
for key in num:
    kobai *= pow(key, num[key],mod)
    kobai %= mod
    
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import fractions

N=int(raw_input())
A = map(int, raw_input().split())

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


l = reduce(lcm, A)

res = 0
for i in range(N):
    res += l/A[i]

print res % (10**9+7)

Submission status: Accepted

Solution code:
import fractions

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

ans = 0
for i in range(N):
    ans = (ans + L // A[i]) #% 1000000007

print(ans%1000000007)

Submission status: Accepted

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

Submission status: Accepted

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


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


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


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

B = [0] * N
for i in range(N):
    B[i] = tmp // A[i]

print(sum(B) % mod)

Submission status: Accepted

Solution code:
from fractions import gcd

MOD = 1000000007
N = int(input())
A = list(map(int, input().split()))
lcm = 1
for c in A:
    g = gcd(lcm, c)
    lcm *= c // g
ans = 0
for c in A:
    ans += lcm // c
print(ans % MOD)

Submission status: Accepted

Solution code:
import fractions
N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
answer = 0


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

g = A[0]
for i in range(1, N):
    p = fractions.gcd(g, A[i])
    g = g*A[i]//p
    
g = g%mod
for i in A:
    answer += (g*modinv(i))%mod
    
print(answer%mod)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

n = int(input())
as_ = list(map(int, input().strip().split()))


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


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


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


lcm_as = lcm_list(as_)

b_sum = sum([lcm_as // a for a in as_]) % 1000000007

print(b_sum)

Submission status: Accepted

Solution code:
def examA():
    N, M = LI()
    if N==M:
        print("Yes")
    else:
        print("No")
    return

def examB():
    A, B = LI()
    if A>B:
        ans = str(B)*A
    else:
        ans = str(A)*B
    print(ans)
    return

def examC():
    N = I()
    P = LI()
    minP = N+1
    ans = 0
    for i in range(N):
        if minP>P[i]:
            minP=P[i]
            ans +=1
    print(ans)
    return

def examD():
    N = I()
    ans = 0
    keep = [[0]*10 for _ in range(10)]
    for i in range(1,N+1):
        l = int(str(i)[0]); r = int(str(i)[-1])
        keep[l][r]+=1

    for i in range(1,N+1):
        l = int(str(i)[0])
        r = int(str(i)[-1])
        ans += keep[r][l]

    print(ans)
    return

def examE():
    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
    N = I()
    A = LI()
    CA = 1
    d = defaultdict(int)
    for i in range(N):
        now = factorization(A[i])
        for key,j in now:
            d[key] = max(d[key],j)
    for key,i in d.items():
        CA *=key**i
        CA %=mod
    ans = 0
#    print(CA,d)
    for i in range(N):
        now = CA *pow(A[i],mod-2,mod)
        ans += now
        ans %=mod
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Accepted

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



def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

l = [0] * (10 ** 6 + 1)

for i in range(n):
    soi = factorize(a[i])
    for j in range(len(soi)):
        l[soi[j][0]] = max(l[soi[j][0]], soi[j][1])

saiko = 1

for i in range(2, 10**6):
    saiko = (saiko * i ** l[i]) % mod

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


def invmod(j):
    return pow(j, MOD - 2, MOD)


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

MOD = 10 ** 9 + 7


l = 1
ans = 0
for i in range(N):
    g = gcd(l, A[i])
    multip = A[i] * invmod(g) % MOD
    l *= multip
    ans *= multip
    ans += l * invmod(A[i]) % MOD
    ans %= MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import deque

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

def LCM(a, b):
  return a * b // GCP(a, b)

def solve():
  MOD = 10**9 + 7

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

  T = deque(A)
  while len(T) > 1:
    T.append(LCM(T.pop(), T.pop()))

  L = T.pop()

  ans = 0
  for i in range(N):
    ans += L // A[i]

  print(ans % MOD)

solve()

Submission status: Accepted

Solution code:
import copy
import fractions
from functools import reduce

N = int(input().strip())
A = list(map(int, input().strip().split()))
m = int(1e9 + 7)
#m = 1000000007
#print(m)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

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

ans = 0
x = lcm(*A)
for i in range(N):
  ans += (x // A[i])
print(ans % m)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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


divisor = 10 ** 9 + 7
len_arr = int(input())
arr = list(map(int, input().split()))

gcd_all = reduce(lcm, arr)
if min(arr) == gcd_all:
    print(len_arr)
else:
    ans = sum([gcd_all // elem for elem in arr]) % divisor
    print(ans)

Submission status: Accepted

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

LCM = 1
for i in a:
    LCM = LCM // fractions.gcd(LCM,i) * i

ans = 0
for i in a:
    ans += (LCM // i)

ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import fractions
 
import math
from functools import reduce
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
n = int(input())
a = list(map(int,input().split()))

c=0

z=lcm_list(a)

for i in range(0,n):
  c+=(z//a[i])
#print(z)
print(c%((10**9)+7))

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 // gcd(a, b) * b

def llcm(l):
    return reduce(lcm, l)

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

def main():
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split()))
    l = llcm(A) % MOD
    r = 0
    for i, a in enumerate(A):
        r = (r + l * modinv(a, MOD)) % MOD
    return r

print(main())

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
def lcm(x,y):
    return (x * y) // gcd(x, y)
MOD = 10**9+7


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

l = reduce(lcm,a)%MOD
ans=0
for i in range(n):
    ans+=l*pow(a[i],MOD-2, MOD)
    ans%=MOD

print(int(ans))

Submission status: Accepted

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

from fractions import gcd

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    s = 0
    m = 1
    for i, Ai in enumerate(A):
        g = gcd(m, Ai)
        Ai_g = Ai // g
        s = s * Ai_g % MOD
        m *= Ai_g
        s = (s + (m // Ai) % MOD) % MOD
    print(s)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
N = int(input())
a = list(map(int, input().split()))
c = a[0]
b = 1
if N > 1:
  for i in range(1, N):
    d = fractions.gcd(c, a[i])
    b = b * a[i] // d + c // d
    b %= (10 ** 9 + 7)
    c = c * a[i] // d
print(b)

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)

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:
N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
def gcd(x,y):
    if x<y:x,y=y,x
    if y==0:return x
    return gcd(y,x%y)
a = 1
for i in range(N):
    a = a*A[i]//gcd(a,A[i])
ans = 0
for i in range(N):
    ans+= a//A[i]
print(ans%mod)

Submission status: Accepted

Solution code:
def prime_factorize(n):
    i = 2
    res = {}
    while i * i <= n:
        if n % i != 0:
            i += 1
            continue
        res[i] = 0
        while n % i == 0:
            res[i] += 1
            n //= i
        i += 1
    if n != 1:
        res[n] = 1
    return res


n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
lcm_ppf = prime_factorize(aaa[0])
for a in aaa[1:]:
    for p, c in prime_factorize(a).items():
        if p in lcm_ppf:
            lcm_ppf[p] = max(lcm_ppf[p], c)
        else:
            lcm_ppf[p] = c

lcm = 1
for p, c in lcm_ppf.items():
    lcm = lcm * pow(p, c, MOD) % MOD
# print(lcm)

ans = 0
for a in aaa:
    ra = pow(a, MOD - 2, MOD)
    ans = (ans + lcm * ra) % MOD
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7

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

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

LCM = A[0]
for i in range(1,N):
    GCD = gcd(LCM,A[i])
    LCM = LCM*A[i]//GCD
LCM %= MOD
ans = 0

for i in range(N):
    ans += LCM*pow(A[i],MOD-2,MOD)
    ans %= MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

MOD = 1000000007

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

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

a_lcm = lcm(*a) % MOD

def pow(x, y):
    if y == 0:
        return 1
    ans = 1
    while y > 1:
        if y % 2 != 0:
            ans *= x
            ans %= MOD 
        x *= x
        x %= MOD 
        y //= 2
    return ans * x % MOD

ans = 0
for ai in a:
  ans += (a_lcm * pow(ai, MOD - 2)) % MOD
  ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def lcmm(l):return reduce(lcm,l)
a = int(input())
List=list(map(int,input().split()))
b = lcmm(List)
c = 0
for i in range(a):
  c = c + b // List[i]
print(c%1000000007)

Submission status: Accepted

Solution code:
from functools import reduce

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


def lcm(x, y):
    a, b = x, y
    while y != 0:
        x, y = y, x % y
    return (a * b) // x


lc = reduce(lcm, d)

ans = 0
for i in d:
    ans += lc // i

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

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

N=input()
A=map(int, sys.stdin.readline().split())

mod=10**9+7
def lcm(a, b):
    g=gcd(a, b)
    return a*b/gcd(a, b)

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

ans=0
for a in A:
    b=lc*pow(a,mod-2,mod)
    ans+=b

print ans%mod

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

def lcm(l):
    return reduce(lambda x, y: (x * y) // fractions.gcd(x, y), l, 1)

base = lcm(A)
print(sum(map(lambda n: base // n, A))%d)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,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
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
from collections import defaultdict
d=defaultdict(int)
for i in a:
    s=factorization(i)
    for x,y in s:
        if d[x]<y:
            d[x]=y
lcm=1
for val in d:
    #print(d[val],val,d[val]*val)
    lcm=lcm*pow(val,d[val],MOD)
    lcm%=MOD
#print(lcm)
#print(d)
count=0
for val in a:
    y=modinv(val,MOD)
    x=lcm*y
    #print((y*val)%MOD)
    x%=MOD
    #print(x,count)
    count+=x
    count%=MOD
print(count)

Submission status: Accepted

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


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


c = 0
for i, a in enumerate(A):
    if i == 0:
        c = a
    else:
        c = lcm(c, a)

result = 0
for a in A:
    result += c // a

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
from heapq import heapify, heappop, heappush
from itertools import combinations, permutations
from bisect import bisect, bisect_left

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    c = a * b
    while a % b > 0:
        a, b = b, a % b
    return b

def solve():
    input = sys.stdin.readline
    mod = 7 + 10 ** 9
    N = int(input())
    A = [int(a) for a in input().split()]
    if N == 1: print(1)
    else:
        lcm = A[0]
        for i in range(1, N):
            gcd_a = gcd(lcm, A[i])
            lcm = lcm * A[i] // gcd_a
        lcm %= mod
        sumB = 0
        for i,a in enumerate(A):
            sumB += lcm * pow(a, mod - 2, mod)
            sumB %= mod

        print(sumB)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# coding:utf-8
from fractions import gcd

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

N = int(input())
A = [int(n) for n in input().split(' ')]
div_n = 10 ** 9 + 7
min_a = min(A)
lcm = A[0]

for a in A:
    lcm = calc_lcm(lcm, a)

if min_a == lcm:
    print((1*N) % div_n)
else:
    stack = 0
    for a in A:
        stack += lcm // a
    print(stack % div_n)

Submission status: Accepted

Solution code:
mod = 10**9+7
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

def prime_decomposition(n):
  i = 2
  d = {}
  while i * i <= n:
    while n % i == 0:
      n //= i
      if i not in d:
          d[i] = 0
      d[i] += 1
    i += 1
  if n > 1:
    if n not in d:
        d[n] = 1
  return d

da = defaultdict(lambda:0)
for i in range(N):
    d = prime_decomposition(A[i])
    for k in d:
        da[k] = max(da[k],d[k])
m = 1
for k in da:
    m *= pow(k,da[k],mod)
    m %= mod
ans = 0
for i in range(N):
    ans += m*pow(A[i],mod-2,mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import fractions as f
MOD=10**9+7
fac=[i for i in range(10**6+1)]
inv=[0]*(10**6+1)
inv[1]=1
for i in range(2,10**6+1):
    inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
#print(inv)
MOD=10**9+7
n=int(input())
a=list(map(int,input().split()))
cnt=a[0]
for i in range(n):
    cnt=(a[i]*cnt)//f.gcd(a[i],cnt)
ans=0
cnt=cnt%(10**9+7)
for i in range(n):
    ans+=inv[a[i]]*cnt
    ans=ans%(10**9+7)
    #print(ans)
print(ans)

Submission status: Accepted

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

import fractions
lcm = 1
prevlcm = 1
ans = 0
for i in range(n):
    ai = a[i]
    lcm = ai * lcm // fractions.gcd(ai, lcm)
    if prevlcm == lcm:
        ans = ans + (lcm // ai)
    else:
        ans = ans * (lcm // prevlcm) + (lcm // ai)
    #print(i, lcm, ans)
    prevlcm = lcm

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

Submission status: Accepted

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

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

import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    for i in range(cnt, last + 1):
      if x % i == 0:
        x //= i
        p[i] = 1
        cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        cnt = i + 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p


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

p = prime(A[0])

for i in range(1, N):
  q = prime(A[i])
  for n in q:
    if n in p:
      p[n] = max(p[n], q[n])
    else:
      p[n] = q[n]

inv = Inv(MOD)
t = 1
for n in p:
  t = t * inv.modpow(n, p[n]) % MOD

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

Submission status: Accepted

Solution code:
N = int(input())
list = 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 // gcd (a, b)

alllcm = 1

for i in range(N):
  alllcm = lcm(alllcm, list[i])

ans = 0

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
import fractions
def lcm(x,y):
  return (x * y) // fractions.gcd(x, y)
r = A[0]
for i in range(N-1):
  r = lcm(r,A[i+1])
ans = 0
for i in range(N):
  ans += r//A[i]
print(ans%1000000007)

Submission status: Accepted

Solution code:
from sys import stdin
import fractions
mod = 10**9+7
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
ans = 0
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, pow(b, mod-2,mod))

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

l = 1
for i in A:
    l = lcm(l,i)
    
for j in A:
    ans += div(l,j)
    ans %= mod
    
print(ans)

Submission status: Accepted

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

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

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


b = [cnt // a[i] for i in range(n)]
print(sum(b)%(10**9+7))

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)

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

Submission status: Accepted

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

def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1 % v2)

A.sort()
a1 = A[0]

for a2 in A[1:]:
    a3 = gcd(a1, a2)
    a1 = a1 * a2 // a3

v = a1
total = 0
for a in A:
    total += v // a 
#    while total > 1000000007:
#        total -= 1000000007

total %= 1000000007
print(total)

Submission status: Accepted

Solution code:
import math
# Python3 program to compute LCM of  
# array elements modulo M 
MAX = 1000003
  
mod = 1000000007
  
prime = [0 for i in range(MAX)] 
  
max_map = dict() 
  
# function to return a^n 
def power(a, n): 
      
    if n == 0: 
        return 1
    p = power(a, n // 2) % mod 
    p = (p * p) % mod 
      
    if n & 1: 
        p = (p * a) % mod 
    return p 
  
# function to find the smallest prime 
# factors of numbers upto MAX 
def sieve(): 
    prime[0], prime[1] = 1, 1
    for i in range(2, MAX): 
        if prime[i] == 0: 
            for j in range(i * 2, MAX, i): 
                if prime[j] == 0: 
                    prime[j] = i 
            prime[i] = i 
  
# function to return the LCM modulo M 
def lcmModuloM(arr, n): 
      
    for i in range(n): 
        num = arr[i] 
          
        temp = dict() 
          
        # temp stores mapping of prime factors  
        # to its power for the current element 
        while num > 1: 
               
            # factor is the smallest prime 
            # factor of num 
            factor = prime[num] 
              
            # Increase count of factor in temp 
            if factor in temp.keys(): 
                temp[factor] += 1
            else: 
                temp[factor] = 1
                  
            # Reduce num by its prime factor 
            num = num // factor 
              
        for i in temp: 
            # store the higest power of every prime 
            # found till now in a new map max_map 
            if i in max_map.keys(): 
                max_map[i] = max(max_map[i], temp[i]) 
            else: 
                max_map[i] = temp[i] 
              
    ans = 1
      
    for i in max_map: 
          
        # LCM is product of primes to their 
        # higest powers modulo M 
        ans = (ans * power(i, max_map[i])) % mod 
    return ans 
  
# Driver code 
sieve()
n = int(input())
a = list(map(int, input().split()))
if len(a) == 1:
    print(1)
    exit()
mod = 10**9+7
lcm = lcmModuloM(a, len(a))
ans = 0
for i in a:
    ans+=pow(i, mod-2, mod)
    ans%=mod
ans*=lcm
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

MOD = int(1e9+7)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


def main():
    N = int(input())
    A = list(map(int, input().split()))
    front = [1] * (N+1)
    back = [1] * (N+1)
    for i in range(N):
        front[i+1] = front[i] * A[i] % MOD
    for i in range(N)[::-1]:
        back[i] = back[i+1] * A[i] % MOD
    used = defaultdict(int)
    ans = 0
    divprod = 1
    for i in range(N):
        use = defaultdict(int)
        a = A[i]
        for x in range(2, int(a**0.5 + 1)):
            while a % x == 0:
                use[x] += 1
                a //= x
            if a == 1:
                break
        if a != 1:
            use[a] += 1
        for u in use:
            divprod = divprod * (u ** min(used[u], use[u])) % MOD
            used[u] = max(use[u], used[u])
        ans = (ans + front[i] * back[i+1]) % MOD
    ans = div(ans, divprod)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import fractions
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

#最小公倍数
def union_lcm(lists):
    if len(lists)==1:
        return lists[0]
    elif len(lists)>1:
        num=lists[0]
        for i in range(1,len(lists)):
            num=num*lists[i]//fractions.gcd(num,lists[i])
        return num


#最大公約数
def union_gcd(lists):
    if len(lists)==1:
        return lists[0]
    elif len(lists)>1:
        num=lists[0]
        for i in range(1,len(lists)):
            num=fractions.gcd(num,lists[i])
        return num
mod=10**9+7   
n=int(input())
lists=list(map(int,input().split()))
a=union_lcm(lists)
c=0
a=a%mod

for i in range(n):
    c+=a*modinv(lists[i],mod)
    c=c%mod
print(c)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))


mod = 10 ** 9 + 7

l = 1
ans = 0
for i in A:
    l = (l * i) // gcd(l,i)
    ans += pow(i, mod-2, mod)
    ans %= mod
l %= mod
ans = (l * ans) % mod

print(ans)