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()))
mod=10**9+7
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]
lcm=[0]*(max(a)+2)
for i in range(n):
  k=a[i]
  for j in range(1,int(a[i]**0.5)+1):
    cnt=0
    while k%(j+1)==0:
      k//=j+1
      cnt+=1
    lcm[j+1]=max(cnt,lcm[j+1])
  lcm[k]=max(1,lcm[k])
lcmn=1
for i in range(len(lcm)):
  if lcm[i]>0:
    lcmn*=i**lcm[i]%mod
lcmn%=mod
ans=0
for i in range(n):
  ans+=lcmn*inv[a[i]]%mod
print(ans%mod)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
import fractions
#import numpy as np

mod=int(10**9+7)


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

#main
N=int(input())
A=list(map(int,input().split()))
l=A[0]
for a in range(1,N):
    l=lcm(l,A[a])
l%=mod

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
MOD = 10**9 + 7
U = 10**6 + 10

is_prime = np.zeros(U,np.bool) #素数列挙(エラトステネス)
is_prime[2] = 1
is_prime[3::2] = 1
# print(is_prime)
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

# Mより大きい数は、ここに現れる
for x in set(A.tolist()):
    lcm *= x
    lcm %= MOD

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

Submission status: Accepted

Solution code:
def gcd(a,b):    #求最大公约数
    if b==0:
        return a
    else:
        return gcd(b,a%b)
n=int(input())
mod=1000000007
s=[int(j) for j in input().split()]
ans=1
for i in s:
    ans*=i//gcd(ans,i)
print(sum(ans//i for i in s)%mod)

Submission status: Accepted

Solution code:
from fractions import*
n=int(input())
mod=1000000007
s=[int(j) for j in input().split()]
ans=1
for i in s:
    ans*=i//gcd(ans,i)
print(sum(ans//i for i in s)%mod)

Submission status: Accepted

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

mod = 10**9 + 7

primes = [2,3,5,7]
for i in range(8,1001):
    check = True
    for j in primes:
        if(j > i**0.5):
            break
        if(i%j == 0):
            check = False
            break
    if(check):
        # print(i)
        primes.append(i)

p_fac = {}
for i in primes:
    p_fac[i] = 0

for i in range(n):
    temp = a[i]
    for j in primes:
        count = 0
        if( temp%j == 0):
            temp = temp // j
            count += 1
            while(True):
                if(temp%j == 0):
                    temp = temp // j
                    count += 1
                else:
                    p_fac[j] = max(p_fac[j],count)
                    break
    if(temp > 1):
        primes.append(temp)
        p_fac[temp] = 1

lcm = 1
for key, value in p_fac.items():
    for i in range(value):
        lcm = lcm*key % mod

# aの逆元を求める
max = max(a)
inv = [0]*(max+1)
inv[0] = 1
inv[1] = 1
for i in range(2,max+1):
    inv[i] = inv[mod % i] * (mod - mod//i ) % mod

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(j) for j in input().split()]
t=1
mod=10**9+7
from fractions import*
for i in a:
    t*=i//gcd(t,i)
print(sum(t//i for i in a)%mod)

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:
from functools import reduce
from fractions import gcd
import numpy as np

MOD = 10**9+7

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

def main():
    N = int(input())
    a = [int(i) for i in input().split()]
    A = np.array(a)  

    lcm = reduce(lcm_base, a, 1)
    B = lcm // A

    print(np.sum(B) % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

def lcm(n, m):
    return n * m // gcd(n, m)

L = A[0]
for a in A:
    L = lcm(L, a)

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

print(ans % MOD)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

MOD = 10**9+7

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

def main():
    N = int(input())
    a = [int(i) for i in input().split()]

    lcm = reduce(lcm_base, a, 1)
    
    ans = 0
    for i in a:
        ans += lcm // i

    print(ans % MOD)


if __name__ == "__main__":
    main()

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)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    D = lcm_list(A)
    ans = 0
    MOD = 10 ** 9 + 7
    D %= MOD
    for a in A:
        ans += D * pow(a, MOD - 2, MOD)
        ans %= MOD
    print(ans)


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

'''
lcm=1
for i in a:
 lcm=(lcm*i)//gcd(lcm,i)
'''

'''
ans=0
mod=10**9+7
for i in a:
 ans+=lcm//i
 ans%=mod
print(ans)

'''
'''
from functools import reduce
lcm=reduce(lambda x,y :(x*y)//gcd(x,y),a)
'''
from functools import reduce
lcm=reduce(lambda x,y :x*(y//gcd(x,y)),a)

'''
ans=0
mod=10**9+7
for i in a:
 ans+=lcm//i
 ans%=mod
'''
ans=sum(lcm//i for i in a)
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7
def gcd(x,y):
  if(x<y) :
    z=y
    y=x
    x=z
  if(y==0):
    return x
  return gcd(x%y,y)

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

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

ans=0
for x in a:
  ans += l//x
print(ans%MOD)

Submission status: Accepted

Solution code:
from fractions import gcd

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


lcm=1
for i in a:
 lcm=(lcm*i)//gcd(lcm,i)

'''
ans=0
mod=10**9+7
for i in a:
 ans+=lcm//i
 ans%=mod
print(ans)

'''
'''
from functools import reduce
lcm=reduce(lambda x,y :(x*y)//gcd(x,y),a)
'''

'''
ans=0
mod=10**9+7
for i in a:
 ans+=lcm//i
 ans%=mod
'''
ans=sum(lcm//i for i in a)
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

'''
lcm=1
for i in a:
 lcm=(lcm*i)//gcd(lcm,i)

ans=0
mod=10**9+7
for i in a:
 ans+=lcm//i
 ans%=mod
print(ans)
'''

from functools import reduce

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

'''
ans=0
mod=10**9+7
for i in a:
 ans+=lcm//i
 ans%=mod
'''
ans=sum(lcm//i for i in a)
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
import math
import fractions
from heapq import heappush, heappop


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7


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 lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
    # return (x * y) * modinv(fractions.gcd(x, y), MOD)


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

lm = 1
s = 0

for i in range(N):
    lm = lcm(A[i], lm)
    #s += lm // MOD
    #lm %= MOD

lm %= MOD
# print(lm)
ans = 0
for i in range(N):
    m = modinv(A[i], MOD)
    ans += lm * m
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

class LCM_mod:
    """
    最小公倍数の計算を行う
    オーバーフローが発生しないように素因数分解し,
    因数の積を逐次余りに置き換えて最小公倍数を導出する.
    """
    def __init__(self, max_num, p=10**9+7):
        self.max_num = max_num + 1
        self.p = p
        self.prime = [0 for _ in range(self.max_num)]
        self.max_map = defaultdict(int)
        self.sieve()

    def rep_sqr(self, base, k):
        # 繰り返し二乗法
        if k == 0:
            return 1
        elif k % 2 == 0:
            return (self.rep_sqr(base, k / 2) ** 2) % self.p
        else:
            return (self.rep_sqr(base, k - 1) * base) % self.p

    def sieve(self):
        """
        エラトステネスの篩　O(n)
        nまでに含まれる素数を導出
        """
        self.prime[0], self.prime[1] = 1, 1
        for i in range(2, self.max_num):
            if self.prime[i] == 0:
                for j in range(i * 2, self.max_num, i):
                    if self.prime[j] == 0:
                        self.prime[j] = i
                self.prime[i] = i

    def lcm_list_mod(self, arr):
        """
        listのそれぞれの要素について、素因数分解する
        それぞれの因数について最大であれば更新する
        """
        for i in range(len(arr)):
            num = arr[i]
            d = defaultdict(int)

            while num > 1:
                fact = self.prime[num]
                d[fact] += 1
                num //= fact

            for i in d.keys():
                self.max_map[i] = max(self.max_map[i], d[i])

        ans = 1
        for i in self.max_map.keys():
            ans = (ans * self.rep_sqr(i, self.max_map[i])) % self.p
        return ans


def rep_sqr(base, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 0:
        return (rep_sqr(base, k / 2, mod) ** 2) % mod
    else:
        return (rep_sqr(base, k - 1, mod) * base) % mod

# a^(-1) == a^(m-2)

def flt(a, mod):
    return rep_sqr(a, mod-2, mod)

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

lcm_mod = LCM_mod(max(a), MOD)
lcm_all = lcm_mod.lcm_list_mod(a)

b = list(map(lambda x: lcm_all * flt(x, MOD), a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

class LCM_mod:
    """
    最小公倍数の計算を行う
    オーバーフローが発生しないように素因数分解し,
    因数の積を逐次余りに置き換えて最小公倍数を導出する.
    """
    def __init__(self, max_num, p=10**9+7):
        self.max_num = max_num + 1
        self.p = p
        self.prime = [0 for _ in range(self.max_num)]
        self.max_map = defaultdict(int)
        self.sieve()

    def rep_sqr(self, base, k):
        # 繰り返し二乗法
        if k == 0:
            return 1
        elif k % 2 == 0:
            return (self.rep_sqr(base, k / 2) ** 2) % self.p
        else:
            return (self.rep_sqr(base, k - 1) * base) % self.p

    def sieve(self):
        """
        エラトステネスの篩　O(n)
        nまでに含まれる素数を導出
        """
        self.prime[0], self.prime[1] = 1, 1
        for i in range(2, self.max_num):
            if self.prime[i]:
                continue
            for j in range(i * 2, self.max_num, i):
                if self.prime[j]:
                    continue
                self.prime[j] = i
            self.prime[i] = i

    def lcm_list_mod(self, arr):
        """
        listのそれぞれの要素について、素因数分解する
        それぞれの因数について最大であれば更新する
        """
        for i in range(len(arr)):
            num = arr[i]
            d = defaultdict(int)

            while num > 1:
                fact = self.prime[num]
                d[fact] += 1
                num //= fact

            for i in d.keys():
                self.max_map[i] = max(self.max_map[i], d[i])

        ans = 1
        for i in self.max_map.keys():
            ans = (ans * self.rep_sqr(i, self.max_map[i])) % self.p
        return ans


def rep_sqr(base, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 0:
        return (rep_sqr(base, k / 2, mod) ** 2) % mod
    else:
        return (rep_sqr(base, k - 1, mod) * base) % mod

# a^(-1) == a^(m-2)

def flt(a, mod):
    return rep_sqr(a, mod-2, mod)

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

lcm_mod = LCM_mod(max(a), MOD)

lcm_all = lcm_mod.lcm_list_mod(a)

b = list(map(lambda x: lcm_all * flt(x, MOD), a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)

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])
 
total=0  
for i in range(0,N):
    total+= ans//a[i]

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

Submission status: Accepted

Solution code:
from collections import defaultdict

class LCM_mod:
    """
    最小公倍数の計算を行う
    オーバーフローが発生しないように素因数分解し,
    因数の積を逐次余りに置き換えて最小公倍数を導出する.
    """
    def __init__(self, max_num, p=10**9+7):
        self.max_num = max_num + 1
        self.p = p
        self.prime = [0 for _ in range(self.max_num)]
        self.max_map = defaultdict(int)
        self.sieve()

    def rep_sqr(self, base, k):
        # 繰り返し二乗法
        if k == 0:
            return 1
        elif k % 2 == 0:
            return (self.rep_sqr(base, k / 2) ** 2) % self.p
        else:
            return (self.rep_sqr(base, k - 1) * base) % self.p

    def sieve(self):
        """
        エラトステネスの篩　O(n)
        nまでに含まれる素数を導出
        """
        self.prime[0], self.prime[1] = 1, 1
        for i in range(2, self.max_num):
            if self.prime[i] == 0:
                for j in range(i * 2, self.max_num, i):
                    if self.prime[j] == 0:
                        self.prime[j] = i
                self.prime[i] = i

    def lcm_list_mod(self, arr):
        """
        listのそれぞれの要素について、素因数分解する
        それぞれの因数について最大であれば更新する
        """
        for i in range(len(arr)):
            num = arr[i]
            d = defaultdict(int)

            while num > 1:
                fact = self.prime[num]
                d[fact] += 1
                num //= fact

            for i in d.keys():
                self.max_map[i] = max(self.max_map[i], d[i])

        ans = 1
        for i in self.max_map.keys():
            ans = (ans * self.rep_sqr(i, self.max_map[i])) % self.p
        return ans


def rep_sqr(base, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 0:
        return (rep_sqr(base, k / 2, mod) ** 2) % mod
    else:
        return (rep_sqr(base, k - 1, mod) * base) % mod

# a^(-1) == a^(m-2)

def flt(a, mod):
    return rep_sqr(a, mod-2, mod)


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

lcm_mod = LCM_mod(max(a), MOD)

lcm_all = lcm_mod.lcm_list_mod(a)

b = list(map(lambda x: lcm_all * flt(x, MOD), a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

class LCM_mod:
    """
    最小公倍数の計算を行う
    オーバーフローが発生しないように素因数分解し,
    因数の積を逐次余りに置き換えて最小公倍数を導出する.
    """
    def __init__(self, max_num, p=10**9+7):
        self.max_num = max_num + 1
        self.p = p
        self.prime = [0 for _ in range(self.max_num)]
        self.max_map = defaultdict(int)
        self.sieve()

    def rep_sqr(self, base, k):
        # 繰り返し二乗法
        if k == 0:
            return 1
        elif k % 2 == 0:
            return (self.rep_sqr(base, k / 2) ** 2) % self.p
        else:
            return (self.rep_sqr(base, k - 1) * base) % self.p

    def sieve(self):
        """
        エラトステネスの篩　O(n)
        nまでに含まれる素数を導出
        """
        self.prime[0], self.prime[1] = 1, 1
        for i in range(2, self.max_num):
            if self.prime[i] == 0:
                for j in range(i * 2, self.max_num, i):
                    if self.prime[j] == 0:
                        self.prime[j] = i
                self.prime[i] = i

    def lcm_list_mod(self, arr):
        """
        listのそれぞれの要素について、素因数分解する
        それぞれの因数について最大であれば更新する
        """
        for i in range(len(arr)):
            num = arr[i]
            d = defaultdict(int)

            while num > 1:
                fact = self.prime[num]
                d[fact] += 1
                num //= fact

            for i in d.keys():
                self.max_map[i] = max(self.max_map[i], d[i])

        ans = 1
        for i in self.max_map.keys():
            ans = (ans * self.rep_sqr(i, self.max_map[i])) % self.p
        return ans


def rep_sqr(base, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 0:
        return (rep_sqr(base, k / 2, mod) ** 2) % mod
    else:
        return (rep_sqr(base, k - 1, mod) * base) % mod

# a^(-1) == a^(m-2)

def flt(a, mod):
    return rep_sqr(a, mod-2, mod)


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

lcm_mod = LCM_mod(10**6, MOD)

lcm_all = lcm_mod.lcm_list_mod(a)

b = list(map(lambda x: lcm_all * flt(x, MOD), a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)

Submission status: Accepted

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

from fractions import gcd

mod = int(1e9 + 7)

lcm = 1
for x in A:
    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:
from collections import defaultdict
import sys
input = sys.stdin.readline

#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def main():
    mod = 10**9+7
    n = int(input())
    a = tuple(map(int,input().split()))

    pr = primes(10**3+1)

    d = defaultdict(lambda : 0)

    for elt in a:
        for p in pr:
            if elt < p:
                break
            c = 0
            while not elt%p:
                c += 1
                elt //= p
            if c > d[p]:
                d[p] = c
        if elt > 1 and d[elt] == 0:
            d[elt] = 1

    lcm  = 1
    for elt in d:
        lcm = lcm*pow(elt,d[elt],mod)%mod

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


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

pr = primes(10**3+1)

d = defaultdict(lambda : 0)

for elt in a:
    for p in pr:
        if elt < p:
            break
        c = 0
        while not elt%p:
            c += 1
            elt //= p
        if c > d[p]:
            d[p] = c
    if elt > 1 and d[elt] == 0:
        d[elt] = 1



lcm  = 1
for elt in d:
    lcm = lcm*pow(elt,d[elt],mod)%mod

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

Submission status: Accepted

Solution code:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める
    計算量: O(log(min(a, b)))"""
    return (a * b) // gcd(a, b)


def multi_gcd(array: list) -> int:
    """arrayのGCDを求める
    計算量: O(Nlog)
    """
    n = len(array)
    ans = array[0]
    for i in range(1, n):
        ans = gcd(ans, array[i])
    return ans


def multi_lcm(array):
    """arrayのLCMを求める"""
    ans = array[0]
    for i in range(1, len(array)):
        ans = (ans * array[i]) // gcd(ans, array[i])
    return ans


n = int(input())
MOD = 10**9 + 7
a = list(map(int, input().split()))
lcm_ = multi_lcm(a) % 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:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める
    計算量: O(log(min(a, b)))"""
    return (a * b) // gcd(a, b)


def multi_gcd(array: list) -> int:
    """arrayのGCDを求める
    計算量: O(Nlog)
    """
    n = len(array)
    ans = array[0]
    for i in range(1, n):
        ans = gcd(ans, array[i])
    return ans


def multi_lcm(array):
    """arrayのLCMを求める"""
    ans = array[0]
    for i in range(1, len(array)):
        ans = (ans * array[i]) // gcd(ans, array[i])
    return ans


n = int(input())
MOD = 10**9 + 7
a = list(map(int, input().split()))
lcm_ = multi_lcm(a) % MOD
ans = 0
for i in range(n):
    ans += lcm_ * pow(a[i], MOD - 2, MOD)
print(ans % MOD)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
MOD = 10**9 + 7
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)

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

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

ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
import fractions
mod = 10**9+7

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

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

print(ans%mod)

Submission status: Accepted

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

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

t = 1
for a in A:
    t = a*t//gcd(a, t)

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

print(ans%mod)

Submission status: Accepted

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

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

n=max(A)+5

#is_prime[i]にはi-1画素数か否かを示すboolが入る，[0]に1の素数判定がある．
is_prime = [True]*(n+1)
is_prime[0] = False

for i in range(2, n+1):
    if is_prime[i-1]:
        j = 2 * i
        while j <= n:
            is_prime[j-1] = False
            j += i

table = [ i for i in range(1, n+1) if is_prime[i-1]]
#print(table)


for i in range(N):
    a=A[i]
    for j in table:
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for d in lcm.items():
    l*=pow(d[0],d[1])
    
ans=0
mod=10**9+7

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

Submission status: Accepted

Solution code:
def e_flatten(MOD=10**9 + 7):
    from fractions import gcd
    from functools import reduce
    N = int(input())
    A = [int(i) for i in input().split()]

    lcm = reduce(lambda x, y: y // gcd(x, y) * x, A) % MOD
    coefficient = sum(pow(a, MOD - 2, MOD) for a in A)
    return (lcm * coefficient) % MOD

print(e_flatten())

Submission status: Accepted

Solution code:
import fractions
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())
l = list(map(int, input().split(" ")))
 
p = lcm_list(l)
c = 0
for i in l:
  c += p // i
print(c % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

# from functools import reduce
# from math import gcd as gcd_base  # from fractions import gcd
# gcd = lambda *numbers: reduce(gcd_base, numbers)  # 3 数以上の最大公約数

# lcm_base = lambda x, y: (x * y) // gcd_base(x, y)
# lcm = lambda *numbers: reduce(lcm_base, numbers, 1)  # 3 数以上の最小公倍数
# 最小公倍数
# def gcd(a, b):
#     if a < b:
#         a, b = b, a
#     while a % b != 0:
#         a, b = b, a % b
#     return b



def many_lcm(l):
    tmp = l[0]
    for i in range(1, len(l)):
        tmp = tmp * l[i]//gcd(tmp, l[i])
    return tmp
N = INT()
A = LIST()

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

Submission status: Accepted

Solution code:
def e_flatten(MOD=10**9 + 7):
    from fractions import gcd
    from functools import reduce
    N = int(input())
    A = [int(i) for i in input().split()]

    lcm = reduce(lambda x, y: x * y // gcd(x, y), A) % MOD
    coefficient = sum(pow(a, MOD - 2, MOD) for a in A)
    return (lcm * coefficient) % MOD

print(e_flatten())

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
 
N = int(input())
A = list(map(int, input().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:
from fractions import gcd
from functools import reduce
lcm=lambda x,y:x//gcd(x,y)*y
MOD=10**9+7

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

c=sum(pow(a,MOD-2,MOD) for a in A)%MOD
l=reduce(lcm,A)%MOD

print(c*l%MOD)

Submission status: Accepted

Solution code:
from fractions import gcd


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


def extgcd(a, b):
    if b == 0:
        return [1, 0, a]
    x, y, g = extgcd(b, a % b)
    return [y, x - a//b * y, g]


def mod_inverse(a, m):
    x, y, _ = extgcd(a, m)
    return (m + x % m) % m


N = int(input())
A = list(map(int, input().split()))
_lcm = 1
for a in A:
    _lcm = lcm(_lcm, a)
ans = 0
big = 1000000007
_lcm %= big
for a in A:
    ans += _lcm * mod_inverse(a, big)
print(ans % big)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
lcm %= MOD

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

print(ans)

Submission status: Accepted

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


def sieve(n):
    result = [0] * (n+1)
    result[0] = result[1] = -1
    #primes = []
    for i in range(2, n+1):
        if(result[i]):
            continue
        # primes.append(i)
        result[i] = i
        for j in range(i*i, n+1, i):
            if not result[j]:
                result[j] = i
    return result


def is_prime(table, x):
    return table[x] == x


def factor(table, x):
    result = {}
    while(x != 1):
        p = str(table[x])
        if p not in result:
            result[p] = 1
        else:
            result[p] += 1
        x //= int(p)
    return result


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

    table = sieve(10**6)
    max_table = {}
    for i in range(n):
        f = factor(table, x[i])
        for j in f:
            if j not in max_table:
                max_table[j] = f[j]
            else:
                max_table[j] = max(max_table[j], f[j])

    lcm = 1
    for p in max_table:
        lcm *= int(p)**max_table[p] % MOD

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


main()

Submission status: Accepted

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

#a,bの最小公倍数
def lcm(a, b):
	return a * b // gcd (a, b)


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

l = a[0]
for e in a:
    l = lcm(l,e)

a_sum = 0
for e in a:
    a_sum = (a_sum + pow(e,mod-2,mod))%mod

print((l%mod)*a_sum%mod)

Submission status: Accepted

Solution code:
from fractions import gcd


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


def extgcd(a, b):
    if b == 0:
        return [1, 0, a]
    x, y, g = extgcd(b, a % b)
    return [y, x - a//b * y, g]


def mod_inverse(a, m):
    x, y, _ = extgcd(a, m)
    return (m + x % m) % m


N = int(input())
A = list(map(int, input().split()))
_lcm = 1
for a in A:
    _lcm = lcm(_lcm, a)
ans = 0
for a in A:
    ans += _lcm * mod_inverse(a, 1000000007)
print(ans % 1000000007)

Submission status: Accepted

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

def prime_factor(n):
    ret, p = [], 2
    while p*p <= n:
        if n % p != 0:
            p += 1
            continue
        exp_v = 0
        while n%p == 0:
            exp_v += 1
            n //= p
        ret.append( [p, exp_v] )
        p += 1
    if n != 1: ret.append( [n, 1] )
    return ret


def extgcd(a, b):
    if b == 0:
        return [1, 0, a]
    x, y, g = extgcd(b, a%b)
    return [y, x - a//b * y, g]


def mod_inverse(a, m):
    x, y, _ = extgcd(a, m)
    return (m+x%m) % m


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

MOD = 10**9 + 7

primes = {}
for aa in a:
    t = prime_factor(aa)
    for tt in t:
        v, e = tt
        primes[v] = max(e, primes.get(v, 0))

prod = 1
for k, v in primes.items():
    prod *= pow(k, v, MOD)
    prod %= MOD

ans = 0
for aa in a:
    ans += prod*mod_inverse(aa, MOD)
    ans %= MOD

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)