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:
#! /usr/bin/env python3
N = int(input())
A = [int(i) for i in input().split()]

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

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

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

ans = 0
MOD = int(1e9 + 7)
for a in A:
    ans += int(l // a)
    # ans %= MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


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

#solve
def solve():
    n = II()
    a = LI()
    lcm_ = lcm(a)
    ans = 0
    lcm_ %= mod
    for i in a:
        ans += lcm_ * pow(i, mod-2, mod)
        ans %= mod
    print(ans)
    return


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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

def lcm_list(l):
    return reduce(lcm, l, 1)


ans = 0

dev = 10 ** 9 + 7

n = int(input())

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

z = lcm_list(a)



for i in a:
    ans += z // i
    #ans = ans % dev

print(ans%dev)

Submission status: Accepted

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

AA = 1
for i in range(N):
    AA = lcm(AA,A[i])
AA %= mod

ans = 0
for i in range(N):
    ans += AA*pow(A[i],mod-2,mod)
    
print(ans%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


MOD = 10**9 + 7

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

# https://note.nkmk.me/python-gcd-lcm/

import math
from functools import reduce
import fractions


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 = lcm_list(a)
dprint(lcm)

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

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

N = I()
A = III()

#互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
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
    return [w[0],w[1]]


#aの逆元(mod M)を求める（aとMは互いに素）
def mod_inv(a,M=mod):
    if a==0:
        return 0
    x = extgcd(a,M)[0]
    return (M+x%M)%M

inv_list = [mod_inv(a) for a in range(max(A)+1)]

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)

x = lcm_list(A) % mod
y = [x*inv_list[a] for a in A]

ans = 0
for i in range(N):
    ans += y[i]
    ans %= mod

print(ans)

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



tmp = [0] * (10**6+1)
for i in range(n):
    t = factorization(a[i])
    for j in range(len(t)):
        tmp[t[j][0]] = max(tmp[t[j][0]], t[j][1])

#print(tmp[:20])

lcm = 1
for i in range(1, 10**6+1):
    x = i 
    y = tmp[i] 
    for j in range(y):
        lcm *= x
        lcm %= mod

#print(lcm)

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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce


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

def MinB_list(numbers):
    return reduce(MinB, numbers, 1)

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

tmp = MinB_list(AList)
result = 0
for i in range(0, N):
    result += tmp // AList[i]
    
print(result % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
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 main():
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    l = A[0]
    for i in A[1:]:
        g = fractions.gcd(g, i)
        l = l * i // fractions.gcd(l, i)
    r = 0
    mod = 10 ** 9 + 7
    n = (l // g) % mod
    for i in A:
        r += n * modinv(i//g, mod)
    print(r % mod)
main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7
lcm = a[0]
for i in range(1,n):
  big,sml = lcm,a[i]
  while sml != 0:
    big,sml = sml,big%sml
  lcm *= a[i] // big
ans = 0
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
#print(inv(5))
for i in range(n):
  ans += inv(a[i])
  ans %= mod
#print(ans)
ans *= lcm
ans %= mod
print(ans)
#print(lcm)
#print(1000000*999999*999998%mod)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
m = 0
sum = 0

n = int(input())
List = list(map(int, input().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)

m = lcm_list(List)

for i in List:
  sum += m // i
print(sum % (10**9 + 7))

Submission status: Accepted

Solution code:
def gcd(x, y): 

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

n = int(input())
a = list(map(int, input().split(' ')))
nok = a[0]
mod = int(1e9 + 7)
for i in range(1, n):
    nok = nok * a[i] // gcd(nok, a[i])
ans = 0
for i in range(0, n):
    ans += nok // a[i]
print (ans % mod)

Submission status: Accepted

Solution code:
import math
import os
import sys
from collections import Counter, defaultdict

from fractions import gcd
from functools import reduce

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


def get_factors(n):
    """
    素因数分解
    :param int n:
    :rtype: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


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

# 最小公倍数
max_counts = defaultdict(int)
for a in A:
    counts = Counter(get_factors(a))
    for k, cnt in counts.items():
        max_counts[k] = max(max_counts[k], cnt)

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

invs = mod_invs(max(A), MOD)
ans = 0
for a in A:
    ans += lcm * invs[a]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
from fractions import gcd
MOD = 10**9 + 7

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


lcm = 1
for item in a:
    lcm = lcm * item // gcd(lcm, item)
lcm %= MOD

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

print(ans)

Submission status: Accepted

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

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

ans=0
for g in range(n):
    ans+=b//a[g]
print(ans%mod)

Submission status: Accepted

Solution code:
def main():
    from collections import Counter as ct
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9+7

    def soinsuu(a):
        yy, j = [], 2
        y = yy.append
        while(a > 1):
            for i in range(j, int(a**0.5)+1):
                if a % i == 0:
                    y(i)
                    a, j = a//i, i
                    break
            else:
                y(a)
                break
        return ct(yy)

    soinsuu_dict = dict()

    for i in a:
        j = soinsuu(i)
        # print(j)
        for x, y in j.items():
            if x not in soinsuu_dict.keys():
                soinsuu_dict[x] = y
            else:
                soinsuu_dict[x] = max(soinsuu_dict[x], y)
    # print(soinsuu_dict)
    l = 1
    for i, j in soinsuu_dict.items():
        l = l*pow(i, j, mod) % mod
    # print(l)
    ans = 0
    for i in a:
        ans = (ans+l*pow(i, mod-2, mod)) % mod
    print(ans)


main()

Submission status: Accepted

Solution code:
from sys import stdin
def gcd(x, y):
	while(y):x, y = y, x % y 
	return x
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
lcm = a[0]
for i in range(1,n):lcm = (lcm*a[i])//gcd(lcm,a[i])
b = [lcm // i for i in a]
print(sum(b)%1000000007)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7

# l = 10**6 + 3

# M = [1]  # i!のmod
# m = 1
# for i in range(1, l):
#     m = (m * i) % mod
#     M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

# print(inv(8,13))

# MI = [0] * (l-1) +[inv(M[l-1], mod)]  # i!の逆元
# for i in range(l-2, -1, -1):
#     MI[i] = MI[i+1] * (i+1) % mod

# def C(x, y):  # コンビネーション
#     if y < 0 or y > x:
#         return 0
#     ans = M[x]
#     ans = (ans * MI[y]) % mod
#     return (ans * MI[x-y]) % mod

from fractions import gcd


def lcm(x, y):
    return (x*y) // gcd(x,y)
    # return int((x * y) * inv(gcd(x, y), mod)) % mod


def lcm_list(A):
    ans = A[0] % mod
    for i in range(1, len(A)):
        ans = lcm(ans, A[i]) #% mod
    return ans % mod

lc = lcm_list(A)
# print(lc)
ans = 0
for i in range(n):
    ans = (ans + (lc * inv(A[i], mod))% mod) % mod
print(ans%mod)

Submission status: Accepted

Solution code:
import fractions

n = int(input())
a = list(map(int, input().split()))
tmp = a[0]
ans = 0

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
MOD = 1000000007
gid = 1
for i in a_list:
    gid_temp = gid
    i_temp = i
    while i_temp > 0:
        gid_temp, i_temp = i_temp, gid_temp % i_temp
    gid = gid * i // gid_temp

sum = 0
for i in a_list:
    sum += gid // i
print(sum % MOD)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

def lcm_ls(num):
    return reduce(lcm, num, 1)


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

m = lcm_ls(ls)

ans = 0

for i in range(n):
    ans += m // ls[i]

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

Submission status: Accepted

Solution code:
from collections import Counter as C
N = 10 ** 6
X = [-1] * (N+1)
L = [[] for _ in range(N+1)]
k = 2
while k <= N:
    X[k] = 1
    L[k].append(k)
    for i in range(k*2, N+1, k):
        X[i] = 0
        L[i].append(k)
    d = 2
    while k**d <= N:
        for i in range(k**d, N+1, k**d):
            L[i].append(k)
        d += 1
    while k <= N and X[k] >= 0:
        k += 1
P = [i for i in range(N+1) if X[i] == 1]
D = {p: 0 for p in P}

###
P = 10**9+7
N = int(input())
A = [int(a) for a in input().split()]
s = sum([pow(a, P-2, P) for a in A]) % P
for a in A:
    c = C(L[a])
    for f in c:
        D[f] = max(D[f], c[f])

l = 1
for f in D:
    l = l * pow(f, D[f], P) % P

print(s * l % P)

Submission status: Accepted

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

import numpy as np

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

MOD = 10 ** 9 + 7

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

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

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

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

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

Submission status: Accepted

Solution code:
#500
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

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

for i in range(N):
    if i == 0:
        LCM = A[0]
    else:
        LCM = lcm(LCM,A[i])

for j in range(N):
    S = S + (LCM // A[j])

S = S % (10**9 + 7)
print(S)

Submission status: Accepted

Solution code:
# Contest: AtCoder Beginner Contest 152 (https://atcoder.jp/contests/abc152)
# Problem: E: Flatten (https://atcoder.jp/contests/abc152/tasks/abc152_e)

def rint():
    return int(input())


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


from fractions import gcd
from functools import reduce
m = 10**9 + 7
def inv(a):
    return pow(a, m - 2, m)
def mod_lcm(a, b):
    return a * b // gcd(a, b)
n = rint()
a = rints()
l = reduce(mod_lcm, a) % m
print(sum(l * inv(ai) % m for ai in a) % m)

Submission status: Accepted

Solution code:
import functools

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

def multiple(a, b):
    return a*b // euclid(a, b)

def lcm(nums):
        return functools.reduce(multiple, nums)

N = int(input())
A = list(map(int, input().split()))
NumLCM = lcm(A)
ans = 0
for i in range(len(A)):
    ans += NumLCM // A[i]

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

Submission status: Accepted

Solution code:
def Eratosthenes(N): #N以下の素数のリストを返す
    #iが素数のときis_prime_list[i]=1，それ以外は0
    N+=1
    is_prime_list = [True]*N
#    is_prime_list[0], is_prime_list[1] = False, False #リストが必要なときはこの2行を有効化
#    for j in range(4,N,2): is_prime_list[j] = False
    m = int(N**0.5)+1
    for i in range(3,m,2):
        if is_prime_list[i]:
            is_prime_list[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,N,2) if is_prime_list[i]]
#    return is_prime_list


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

#m = 1000000
#a = list(range(m,m+2000))

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

ans = 0
M = m%MOD
for i in a:
    ans += M*pow(i,MOD-2,MOD)%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

Submission status: Accepted

Solution code:
def lcm(data):
    from fractions import gcd
    x = data[0]
    for i in range(1, len(data)):
        x = (x * data[i]) // gcd(x, data[i])
    return x


k = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
z = lcm(a)
answer = 0
for j in range(n):
    answer += z // a[j]
print(answer % k)

Submission status: Accepted

Solution code:
import fractions as math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
a = input()
b = list(map(int,input().split()))
c = lcm_list(b)
ans = 0
for d in b:
  ans += c//d
print(ans%1000000007)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))

# lcm & gcd not math
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

from functools import reduce
def lcm_multi(num_list):
    return reduce(lcm, num_list, 1)

div_num = 10 ** 9 + 7
lcm_num = lcm_multi(tuple(A_list))
ans = 0
for i in range(N):
    ans += (lcm_num // A_list[i])
print(ans % div_num)

Submission status: Accepted

Solution code:
def gcd(x,y):
    while y != 0:
        x, y = y, x%y
#        print(x,y)
    return(x)

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

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

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

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
p = 10 ** 9 + 7

def pr(x):
    a=[]
    i=2
    while True:
        if x % i == 0:
            j=0
            while x % i == 0:
                x //= i
                j += 1
            a.append((i, j))
        if i * i > x:
            break
        i += 1
    if x != 1:
        a.append((x,1))
    return a
c = {}
for i in a:
    d = pr(i)
    for j in d:
        if j[0] in c:
            c[j[0]] = max(c[j[0]], j[1])
        else:
            c[j[0]] = j[1]

b = 1
for i in c:
    b *= pow(i, c[i], p)
    b %= p
ans = 0
for i in a:
    ans += b * pow(i, p - 2, p)
    ans %= p
print(ans)

Submission status: Accepted

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

mod=10**9+7

from collections import Counter

F=Counter()

import math

for x in A:
    L=int(math.sqrt(x))

    FACT=dict()

    for i in range(2,L+2):
        while x%i==0:
            FACT[i]=FACT.get(i,0)+1
            x=x//i

    if x!=1:
        FACT[x]=FACT.get(x,0)+1

    for f in FACT:
        F[f]=max(F[f],FACT[f])

#print(F)

LCM=1
for f in F:
    LCM=LCM*pow(f,F[f],mod)%mod

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

print(ANS)

Submission status: Accepted

Solution code:
MAX = 10**6+3

mod = 1000000007

prime = [0 for i in range(MAX)]

max_map = dict() 

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 

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 

def lcmModuloM(arr, n): 

	for i in range(n): 
		num = arr[i] 

		temp = dict() 

		while num > 1: 

			factor = prime[num] 

			if factor in temp.keys(): 
				temp[factor] += 1
			else: 
				temp[factor] = 1

			num = num // factor

		for i in temp:
			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:
		ans = (ans * power(i, max_map[i])) % mod
	return ans

n = int(input())
a = list(map(int, input().split()))
sieve()
LCM = lcmModuloM(a, n)
ans = 0
for ai in a:
    ans += pow(ai, mod-2, mod)
ans *= LCM
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def GCD(a, b):
    return GCD(b, a % b) if b else a
    
def LCM(a, b):
    return a // GCD(a, b) * b

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

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

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

print(ans%1000000007)

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)
ans = 0
for i in range(n):
    ans += lcm_ * pow(a[i], MOD - 2, MOD)
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()

isp = [True] * 1001
isp[0] = isp[1] = False
for p in range(2, 1001):
    if isp[p]:
        for j in range(p*2, 1001, p):
            isp[j] = False

maxe = [0] * 1000001
for v in a:
    for p in range(2, 1001):
        e = 0
        while v % p == 0:
            v //= p
            e += 1
        maxe[p] = max(maxe[p], e)
    if v > 1:
        maxe[v] = max(maxe[v], 1)

def inv(a, mod):
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    return p+mod if p < 0 else p


ans = 1
mod = 1000000007
for i in range(2, 1000001):
    for j in range(maxe[i]):
        ans = ans * i % mod

xx = 0
for v in a:
    xx += inv(v, mod)

print(ans*xx%mod)

Submission status: Accepted

Solution code:
def PrimeFact(N):
    PF = dict()
    M = N
    k = 2
    while (k*k<=N):
        od = 0
        if M % k == 0:
            while (True):
                if M % k == 0:
                    od += 1
                    M = M // k
                else:
                    break
            PF[k]=od
        else:
            k += 1
        if M == 1:
            break
    if M>1:
        PF[M]=1
    return PF

N=int(input())
A=[int(i) for i in input().split()]
#import random
#N=10**4
#A=[random.randrange(1,10**6+1) for i in range(N)]
mod=10**9+7
def inv(x):
    return pow(x,mod-2,mod)
D=dict()
for i in range(N):
    T=PrimeFact(A[i])
    for p in T:
        if not(p in D):
            D[p]=0
        D[p]=max(D[p],T[p])
ans=1
for p in D:
    ans=ans*pow(p,D[p],mod)
    ans%=mod
tmp=0
for i in range(N):
    tmp+=inv(A[i])
    tmp%=mod
ans=ans*tmp
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


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

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


N = inp()
aa = inpl()
tmp = 1

for a in aa:
    tmp = lcm(a,tmp)

tmp %= mod
ans = 0
for a in aa:
    ans += tmp * pow(a,mod-2,mod)
    ans %= mod

print(ans)

Submission status: Accepted

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

n=int((input()))
a=input().split()
t=1
for x in a:
    t=(t*int(x))//(gcdlol(t,int(x)))
ans=0
for x in a:
    ans+=(t//int(x))
print(ans%1000000007)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

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

    n = I()
    a = LI()
    g = a[0]
    l = a[0]
    for i in a[1:]:
        g = gcd(l,i)
        l = l*i//g
    ans = 0
    for i in a:
        ans += pow(i,mod-2,mod)
        ans %= mod
    print(ans*l%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
mod=10**9+7
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)
l=a[0]
for i in range(1,n):
  l=lcm(l,a[i])
ans=0
l%=mod
for i in range(n):
  ans+=l*pow(a[i],mod-2,mod)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
def power(a,b):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power(a,b//2)
        return d*d%mod
    elif b % 2 == 1:
        return a*power(a,b-1)%mod
import fractions
l = A[0]
g = A[0]
for i in range(1,N):
    x = A[i]
    g = fractions.gcd(l,x)
    l = l*x//g
l = l % mod
ans = 0
for i in range(N):
    ans += l*power(A[i],mod-2) % mod
ans = ans%mod
print(ans)

Submission status: Runtime Error

Solution code:
    import math
    from functools import reduce
     
    def lcm_base(x, y):
        return (x * y) // math.gcd(x, y)
     
    def lcm_list(numbers):
        return reduce(lcm_base, numbers, 1)
      
    N = int(input())
    A = list(map(int,input().split()))
    ans = 0
     
    lcm = lcm_list(A)
     
    for i in range(N):
      ans += lcm//A[i]
     
    print(ans%1000000007)

Submission status: Runtime Error

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) 
      
    n = int(input())
    arr = input()   # takes the whole line of n numbers
    a = list(map(int,arr.split(' ')))
    l = a[0]
    ans = 0
    for i in range(n):
        l = lcm(l, a[i])
    for i in range(n):
        ans = ans + l//a[i]
    print(ans%1000000007)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
import numpy as np

def lcm_base(x, y):
    return (x * y) // math.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()))
mod = 10**9+7

lcm = lcm_list(a)
b = lcm / np.array(a)
ans = 0
for i in range(n):
  ans += b[i] % mod
print(int(ans) % mod)

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
import numpy as np

def lcm_base(x, y):
    return (x * y) // math.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()))
mod = 10**9+7

lcm = lcm_list(a)
b = lcm / np.array(a)
ans = int(sum(b)) % mod
print(ans)

Submission status: Runtime Error

Solution code:
def cin():  return list(map(int,input().split()))

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

def gcd(l):
    ans = 0
    for i in l:  ans = gcd_(ans, i)
    return ans

def lcm_(x,y):
    return (x * y) // gcd_(x, y)

def lcm(l):
    ans = l[0]
    for i in l:  ans = lcm_(ans, i)
    return ans

N = cin()[0]
v = cin()
lc = lcm(v)
ans = 0
INF = 10 ** 9 + 7
for i in range(N):
    ans += lc / v[i]
    ans %= INF
print(int(ans))

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    from collections import defaultdict
    #nの素因数分解，[[a1,b1],[a2,b2]...]   aがb個,
    def factorization(n):
        if n==1:
            return [0,1]
        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
    
    lcm_dd = defaultdict(int)
    
    N=I()
    A=LI()
    L=[]
    for i in range(N):
        a=A[i]
        arr=factorization(a)
        for v in arr:
            p,cnt=v
            lcm_dd[p]=max(lcm_dd[p],cnt)
            
    lcm=1
    for k,v in lcm_dd.items():
        temp=pow(k,v,mod)
        lcm=(lcm*temp)%mod
        
    ans=0
    for i in range(N):
        temp=(lcm*pow(A[i],mod-2,mod))%mod
        ans=ans+temp
        
    print(ans%mod)
        
    


main()