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:

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


def pow(a, b, mod=10 ** 9 + 7):
    if b == 0:
        return 1
    elif b == 1:
        return a
    elif b % 2 == 0:
        return (pow(a, b // 2) ** 2) % mod
    else:
        return (a * pow(a, b // 2) ** 2) % mod


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


def factorize(x):
    ans = {}
    v = 2
    while v * v <= x:
        if x % v == 0:
            ans[v] = 0
            while x % v == 0:
                x //= v
                ans[v] += 1
        v += 1
    if x != 1:
        ans[x] = 1
    return ans


def merge(d, c):
    for k, v in c.items():
        if k not in d:
            d[k] = v
        d[k] = max(d[k], v)


tmp = {}
for v in A:
    merge(tmp, factorize(v))
t = 1
mod = 10 ** 9 + 7
for k, v in tmp.items():
    t *= k ** v
    t %= mod
ans = 0
for a in A:
    ans += t * inv(a)
print(ans % mod)

Submission status: Accepted

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

#arr：最小公倍数の対象とする配列
MOD = 10**9 + 7
def lcm(arr):
    primes = {}
    for val in arr:
        p = 2
        while p * p <= val:
            if val % p == 0:
                cnt = 0
                while val % p == 0:
                    cnt += 1
                    val //= p
                if p not in primes:
                    primes[p] = cnt
                else:
                    primes[p] = max(cnt, primes[p])
            p += 1
     
        if val != 1:
            if val not in primes:
                primes[val] = 1
    lcma = 1
    for p in primes:
        lcma = lcma * pow(p, primes[p], MOD) 
    return lcma

b = lcm(arr)

ans=0
for i in range(n):
    ans+=(b//arr[i])

print(ans%MOD)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

    lcm_of_all_a = functools.reduce(lambda x, y: lcm(x, y), a, 1)
    lcm_of_all_a %= mode   # THIS LINE IS KEY POINT

    b = map(lambda x: lcm_of_all_a * inverse(x, mode) % mode, a)
    return sum(b) % mode


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
m=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)
mod=10**9+7
n=lcm_list(a)
ans=0
for i in range(m):
    ans+=(n//a[i])
print(ans%mod)

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 else a
def lcm(a,b):
    return a*b//gcd(a,b)
k=1
for i in a:
    k=lcm(k,i)
ans=0
for i in a:
    ans+=k//i
ans%=10**9+7
print(ans)

Submission status: Accepted

Solution code:
import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

    lcm_of_all_a = functools.reduce(lambda x, y: lcm(x, y), a, 1)
    lcm_of_all_a %= mode

    b = map(lambda x: lcm_of_all_a * inverse(x, mode) % mode, a)
    return sum(b) % mode


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

Solution code:
import sys
from pprint import pprint
from fractions import gcd

mod = 10**9+7

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

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

b = []
for a_i in a:
    b_i = modinv(a_i, mod)
    b.append(b_i)

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

# calc lcm for a
cur = 1
for a_i in a:
    cur =  lcm(cur, a_i)

# sum lcm / a_i for a using mod inverse a (= b)
ans = 0
for b_i in b:
    ans += cur * b_i
ans %= mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

import fractions as math
#リスト l の最大公約数
def lcmlist(l):
    a = l[0]
    for i in range(len(l)):
        a = int(a)
        a = a*l[i]//math.gcd(a,l[i])
    return int(a)

g = lcmlist(lst1)
ans = 0
for i in range(n):
    ans += g//lst1[i]
print(ans%mod)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)
k=1
for i in range(n):
    k = lcm(k,a[i])
ans=0
for i in range(n):
    ans += k//a[i]
ans %= 1000000007
print(ans)

Submission status: Accepted

Solution code:
import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

    lcm_of_all_a = functools.reduce(lambda x, y: lcm(x, y), a, 1)
    lcm_of_all_a %= mode

    result = 0
    for e in a:
        result += lcm_of_all_a * inverse(e, mode) % mode
        result %= mode
    return result


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

Solution code:
def gcd(a, b):
  while(b > 0):
    a %= b
    a, b = b, a
  return a
def lcm(a, b):
  return a * b // gcd(a,b)
n = int(input())
md = int(1e9 + 7)
a = [int(e) for e in input().split()]
x = 1
for j in range(n):
  x = lcm(x, a[j])
ans = 0
for i in range(n):
  ans += x // a[i]
ans %= md
print(ans)

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

LCM=A[:]
num=N
while num>1:
    for i in range(1,num,2):
        LCM[i//2]=lcm(LCM[i-1],LCM[i])
    if num&1:
        LCM[num//2]=LCM[num-1]
    num=(num+1)//2

ans=0
l=LCM[0]%MOD
for a in A:
    ans+=l*pow(a,MOD-2,MOD)
    ans%=MOD

print(ans)

Submission status: Accepted

Solution code:
import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

    lcm_of_all_a = functools.reduce(lambda x, y: lcm(x, y), a, 1)
    lcm_of_all_a %= mode

    result = 0
    for e in a:
        result += lcm_of_all_a * inverse(e, mode) % mode
        result %= mode
    return result


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

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

MOD=10**9+7
def gcd(a,b):
    while b: a,b=b,a%b
    return a
def lcm(a,b): return a*b//gcd(a,b)

LCM=A[:]
num=N
while num>1:
    for i in range(1,num,2):
        LCM[i//2]=lcm(LCM[i-1],LCM[i])
    if num&1:
        LCM[num//2]=LCM[num-1]
    num=(num+1)//2

ans=0
l=LCM[0]%MOD
for a in A:
    ans+=l*pow(a,MOD-2,MOD)
    ans%=MOD

print(ans)

Submission status: Accepted

Solution code:
import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

    lcm_of_all_a = 1
    for e in a:
        lcm_of_all_a = lcm(lcm_of_all_a, e)

    lcm_of_all_a %= mode
    result = 0
    for e in a:
        result += lcm_of_all_a * inverse(e, mode) % mode
        result %= mode
    return result


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Accepted

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

import fractions

X = A[0]
for i in range(1, N):
    X = X*A[i] // fractions.gcd(X, A[i])

output = 0
D =10**9+7
X = X%D

for i in range(N):
    output += X*pow(A[i],D-2,D)%D
    output = output % (10**9+7)
print(int(output))

Submission status: Accepted

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

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

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

from fractions import gcd

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

b = a[:]
N = len(bin(n))-1
for i in range(N):
    d = 1<<i
    for k in range(d,n,2*d):
        a[k-d] = lcm(a[k],a[k-d])
m = a[0]

ans = 0
for i in b:
    ans += m//i

print(ans%MOD)

Submission status: Accepted

Solution code:
from fractions import gcd

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

MOD = 10 ** 9 + 7  
N = int(input())
A = list(map(int, input().split()))
 
l = 1
for i in A:
  l = lcm(l, i)
  
ans = 0
for a in A:
  ans += l // a
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys

MOD=10**9+7

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

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

print(ans%MOD)

Submission status: Accepted

Solution code:
P = 10**9 + 7
N = 1000001
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

n = int(input())
lili = list(map(int,input().split()))
import copy
lili2 = copy.copy(lili)
#a>b
inin = 1
lili = list(set(lili))
for i in range(2,10 ** 3+2):
    count = 0
    for j in range(len(lili)):
        if lili[j] % i != 0: continue
        now = 0
        while (lili[j] % i == 0):
            now += 1
            lili[j] = lili[j] // i
        count = max(count,now)
    inin = inin * (i ** count) % P
lili = list(set(lili))
for i in range(len(lili)):

    inin = inin * lili[i] %P

ans = 0
for i in range(n):
    ans += inin * (pow(lili2[i],P-2,P)) %P
    ans % P
print(ans %P)

Submission status: Accepted

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
def inv(x):
  r=[1,0,x]
  w=[0,1,mod]
  while w[2]!=1:
    q=r[2]//w[2]
    r2=w
    w2=[r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
    r=r2
    w=w2
  return w[0]

import collections

P=collections.defaultdict(int)
ans=0
for a in A:
  ans=(ans+inv(a))%mod
  pf={}
  for i in range(2,int(a**0.5)+1):
    while a%i==0:
      pf[i]=pf.get(i,0)+1
      a//=i
  if a>1:
    pf[a]=1
  for p in pf.keys():
    P[p]=max(P[p],pf[p])
for p in P.keys():
  ans=(ans*pow(p,P[p],mod))%mod

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
import fractions


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

    x = 1
    for a in A:
        x = (a * x) // fractions.gcd(a, x)

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

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
MOD = 10 ** 9 + 7  
n = int(input())
A = list(map(int, input().split()))

l = 1
for i in A:
  l = lcm(l, i)
  
ans = 0
for a in A:
  ans += l // a

print(ans % MOD)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

def lcm_mod(a, mod=-1):
    x = a[0]
    if mod == -1:
        for i in range(1, len(a)):
            x = (x * a[i]) // gcd(x, a[i])
    else:
        for i in range(1, len(a)):
            x *= (a[i] * mod_inv(gcd(x, a[i]), P)) % P
    return x

_,a = [list(map(int, s.split())) for s in open(0)]

P = 10**9 + 7
N = max(a)

lcm_ = lcm_mod(a, P)

ans = 0
for x in a:
    ans += int((lcm_*mod_inv(x,P))%P)
print(int(ans%P))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from fractions import gcd
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
def gyaku(a):
    return pow(a,mod-2,mod)
if n==1:
    print(1)
else:
    gya=[0]*(n)
    g=A[0]
    l=A[0]
    gya[0]=gyaku(A[0])
    for i in range(n-1):
        g=gcd(l,A[i+1])
        l*=(A[i+1]//g)
        gya[i+1]=gyaku(A[i+1])
    ans=0
    for i in range(n):
        ans+=l*gya[i]
        ans%=mod
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
import collections

P=collections.defaultdict(int)
ans=0
for a in A:
  ans=(ans+pow(a,mod-2,mod))%mod
  pf={}
  for i in range(2,int(a**0.5)+1):
    while a%i==0:
      pf[i]=pf.get(i,0)+1
      a//=i
  if a>1:
    pf[a]=1
  for p in pf.keys():
    P[p]=max(P[p],pf[p])

for p in P.keys():
  ans=(ans*pow(p,P[p],mod))%mod

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
mod = 10 ** 9 + 7

N = INT()
A = LIST()

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

ans = 0
for x in A:
    ans += tmp//x
print(ans%mod)

Submission status: Accepted

Solution code:
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x
  
N = int(input())
lst = list(map(int, input().split()))
const = 10**9 + 7

def solve(arr):
    ab = lcm(arr)
    sum = 0
    for a in arr:
        sum += ab // a
    return sum % const

answer = solve(lst)

print(int(answer))

Submission status: Accepted

Solution code:
import fractions


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


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

Submission status: Accepted

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

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

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    l = int(1)
    for e in a:
        l = lcm(l,e)
    s = int(0)
    for e in a:
        s += l//e
    mod = int(1000000007)
    print(int(s % mod))

Submission status: Accepted

Solution code:
MOD = (10**9) + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

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

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


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


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


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    k = A[0]
    for a in A[1:]:
        k = lcm(k, a)
    k = modint(k)
    ans = modint(0)
    for a in A:
        ans += k/a
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def lcm(a,b):
    return a*b//fractions.gcd(a,b)
ans = l[0]
for i in range(1,n):
    ans = lcm(ans,l[i])
    

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

Submission status: Accepted

Solution code:
MOD = (10**9) + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

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

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


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


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


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    k = A[0]
    for a in A[1:]:
        k *= a//gcd(k, a)
    k = modint(k)
    ans = modint(0)
    for a in A:
        ans += k/a
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

P = 10**9 + 7
N = (10**6)+1
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

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

mod = 10**9+7
lcm = 1
B = [0]*N

for i in range(N):
    lcm = (lcm // fractions.gcd(lcm, A[i])) * A[i]

ans = 0
lcm %= mod
for i in range(N):
    ans += (lcm * inv_t[A[i]]) % mod
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
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()))

mod = 10 ** 9 + 7
N = 1000002

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

base = a[0]
for ai in a:
    base = lcm(base, ai)
base %= mod
ans = 0
for ai in a:
    ans = (ans + base * inv_t[ai]) % mod
print(ans)

Submission status: Accepted

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

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

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

res = 0;
for i in range(n):
    res = res + (lc // a[i])

print(res % 1000000007)

Submission status: Accepted

Solution code:
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m


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


N = int(input())
A = list(map(int, input().split()))
A.sort()
lcm_value = A[0]
for i in range(1, N):
    lcm_value = lcm(lcm_value, A[i])

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

print(ans % mod)

Submission status: Accepted

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

mod = 10**9 + 7


lcm = 1
for a in A:
    lcm = lcm*a//fractions.gcd(lcm, a)
# print(lcm)

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