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:
import sys

MOD = 10 ** 9 + 7

from math import floor, sqrt
from bisect import bisect_right as bi_r
from collections import defaultdict

def prime_nums(n=10**6):
    sieve = set(range(2, n + 1))
    non_prime = set(range(2 * 2, n + 1, 2))
    sieve -= non_prime
    for i in range(3, floor(sqrt(n)) + 1, 2):
        if i in sieve:
            non_prime = set(range(i * 2, n + 1, i))
            sieve -= non_prime
    return sieve

p_nums = sorted(prime_nums())

def make_inv_table(n=10**6, p=MOD):
    fac = [None] * (n + 1)
    fac[0] = 1
    for i in range(n):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (n + 1)
    ifac[n] = pow(fac[n], p-2, p)
    for i in range(n, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    inv = [None] * (n + 1)
    for i in range(1, n+1):
        inv[i] = ifac[i] * fac[i-1] % p
    return inv

inv = make_inv_table()

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

def main():
    facs = defaultdict(int)
    for a in A:
        if a == 1:
            continue
        for p in p_nums[:bi_r(p_nums, sqrt(a))]:
            cnt = 0
            while not a % p:
                cnt += 1
                a //= p
            facs[p] = max(facs[p], cnt)
            if a == 1:
                break
        else:
            facs[a] = max(facs[a], 1)
    
    lcm = 1
    for f, c in facs.items():
        lcm *= pow(f, c, MOD)
        lcm %= MOD
    
    ans = 0
    for a in A:
        ans += lcm * inv[a] % MOD
        ans %= MOD
    return ans

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

#------------最小公倍数---------------------
lcm = a[0]
for i in range(1, N):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i])
#------------------------------------------
ans=0
for j in a:
    ans += lcm // j
print(ans % 1000000007)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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

L = reduce(lcm, A) % mod
print(L * sum(pow(a, mod - 2, mod) for a in A) % mod)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

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()))
calc=(lcm(a))  # 実行結果: 12


ans=0
for index,item in enumerate(a):
    ans+=(calc)//item

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

Submission status: Accepted

Solution code:
import functools
import fractions

MOD = 10**9 + 7
N = int(input())
A = [int(i) for i in input().split()]

L = functools.reduce(lambda a, b: a // fractions.gcd(a, b) * b, A) % MOD
ans = 0

for a in A:
    ans += L * pow(a, MOD - 2, MOD)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
lcm = list(map(int, input().split()))
ans = [1] * n
while len(lcm) < (1 << 14):
  lcm.append(1)
  ans.append(0)
for i in range(13, -1, -1):
  bit = 1 << i
  for j in range(bit):
    new = lcm[j] // gcd(lcm[j], lcm[j | bit]) * lcm[j | bit]
    ans[j] = new // lcm[j] * ans[j] + new // lcm[j | bit] * ans[j | bit]
    lcm[j] = new
print(ans[0] % 1000000007)

Submission status: Accepted

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
MOD = 1000000007
lcm = 1
for a in A:
    lcm = a // gcd(lcm, a) * lcm
ans = 0
for a in A:
    ans += lcm // a
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
lcm = list(map(int, input().split()))
ans = [1] * n
while len(lcm) < (1 << 14):
  lcm.append(1)
  ans.append(0)
for i in range(13, -1, -1):
  bit = 1 << i
  for j in range(bit):
    new = lcm[j] // gcd(lcm[j], lcm[j | bit]) * lcm[j | bit]
    ans[j] = new // lcm[j] * ans[j] + new // lcm[j | bit] * ans[j | bit]
    ans[j] %= 1000000007
    lcm[j] = new
print(ans[0])

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
lcm = list(map(int, input().split()))
ans = [1] * n
while len(lcm) < (1 << 14):
  lcm.append(1)
  ans.append(0)
for i in range(13, -1, -1):
  bit = 1 << i
  for j in range(bit):
    new = lcm[j] // gcd(lcm[j], lcm[j | bit]) * lcm[j | bit]
    ans[j] = new // lcm[j] * ans[j] + new // lcm[j | bit] * ans[j | bit]
    ans[j] %= 1000000007
    lcm[j] = new
print(ans[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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

L = reduce(lcm, A) % mod
print(sum(L * pow(a, mod - 2, mod) for a in A) % mod)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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

L = reduce(lcm, A) % mod
print(sum(L * pow(a, mod - 2, mod) % mod for a in A) % mod)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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

L = reduce(lcm, A)
print(sum(L // a for a in A) % mod)

Submission status: Accepted

Solution code:
from fractions import gcd

mod = 10 ** 9 + 7

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

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

L %= mod

print(sum(L * pow(a, mod - 2, mod) for a in A) % mod)

Submission status: Accepted

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 


def flatten():
    MOD = 10**9+7
    N = wczytaj_liste()[0]
    A = wczytaj_liste()
    najwieksza = max(A)
    najmniejszy_dzielnik = [None] * (najwieksza + 1)
    for i in reversed(range(2, najwieksza + 1)):
        for j in range(0, najwieksza + 1, i):
            najmniejszy_dzielnik[j] = i
    najwieksze_wykladniki = [0] * (najwieksza + 1)
    for liczba in A:
        dzielnik = 1
        wykladnik = 0
        while liczba != 1:
            d = najmniejszy_dzielnik[liczba]
            if d == dzielnik:
                wykladnik += 1
            else:
                if najwieksze_wykladniki[dzielnik] < wykladnik:
                    najwieksze_wykladniki[dzielnik] = wykladnik
                dzielnik = d
                wykladnik = 1
                
            liczba //= d
            
        if najwieksze_wykladniki[dzielnik] < wykladnik:
            najwieksze_wykladniki[dzielnik] = wykladnik
    
    nww = 1
    for dzielnik, wykladnik in enumerate(najwieksze_wykladniki):
        nww = nww * pow(dzielnik, wykladnik, MOD) % MOD
    
    suma = 0
    for liczba in A:
        suma += nww * pow(liczba, MOD - 2, MOD)
        suma %= MOD
    print(suma)
        

flatten()

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline

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

from fractions import gcd
from functools import reduce

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

ans = 0

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

print(ans % mod)

Submission status: Accepted

Solution code:

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

from fractions import gcd

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

ans = 0

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

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()
nas = lambda: stdin.readline().split()

n = ni()
a = na()

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

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

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

ans %= 1000000007
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

lcm = A[0]

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

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)

lcm = A[0]

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

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

print(ans)

Submission status: Accepted

Solution code:

def Sieve(n): #n以下の素数全列挙(O(nloglogn)) retは素数が入ってる。divlisはその数字の素因数が一つ入ってる

    ret = []
    divlis = [-1] * (n+1) #何で割ったかのリスト(初期値は-1)
    
    flag = [True] * (n+1)
    flag[0] = False
    flag[1] = False

    ind = 2
    while ind <= n:

        if flag[ind]:
            ret.append(ind)

            ind2 = ind ** 2

            while ind2 <= n:
                flag[ind2] = False
                divlis[ind2] = ind
                ind2 += ind

        ind += 1

    return ret,divlis
        

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

nums,divs = Sieve(max(A)+1)

dic = {}

for i in range(N):

    na = A[i]
    ss = {}

    while True:

        if divs[na] > 0:
            if divs[na] not in ss:
                ss[divs[na]] = 0

            ss[divs[na]] += 1
            na = na // divs[na]

        else:
            if na not in ss:
                ss[na] = 0
            
            ss[na] += 1
            break

    for j in ss:
        if j not in dic:
            dic[j] = ss[j]
        else:
            dic[j] = max(dic[j],ss[j])

lcm = 1
#print (dic)

for i in dic:
    lcm *= pow(i,dic[i],mod)

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

Submission status: Accepted

Solution code:
def primeFactor(N):
    i = 2
    ret = {}
    n = N
    while i*i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i%2
        if i == 101 and n >= 2**20:
            def findFactorRho(N):
                def gcd(a, b):
                    while b: a, b = b, a % b
                    return a
                def f(x, c):
                    return (x * x + c) % N
                for c in range(1, 99):
                    X, d, j = [2], 1, 0
                    while d == 1:
                        j += 1
                        X.append(f(X[-1], c))
                        X.append(f(X[-1], c))
                        d = gcd(abs(X[2*j]-X[j]), N)
                    if d != N:
                        if isPrimeMR(d):
                            return d
                        elif isPrimeMR(N//d): return N//d
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    return ret

def isPrimeMR(n):
    if n == 2:
        return True
    if n == 1 or n & 1 == 0:
        return False
    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    
    L = [2, 7, 61] if n < 1<<32 else [2, 13, 23, 1662803] if n < 1<<40 else [2, 3, 5, 7, 11, 13, 17] if n < 1<<48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    for a in L:
        t = d
        y = pow(a, t, n)
        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False
    return True


P = 10**9+7
D = {}
N = int(input())
A = [int(a) for a in input().split()]
t = 0
for a in A:
    t += pow(a, P-2, P)
    pf = primeFactor(a)
    for p in pf:
        if p in D:
            D[p] = max(D[p], pf[p])
        else:
            D[p] = pf[p]
s = 1
for f in D:
    s = (s * pow(f, D[f], P)) % P
print(s * t % P)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
from fractions import gcd
mod=10**9+7
g=A[0]
for a in A:
  g=g*a//gcd(g,a)

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

Submission status: Accepted

Solution code:
def primeFactor(N):
    i, n, ret, d, sq = 2, N, {}, 2, 99
    while i <= sq:
        k = 0
        while n % i == 0: n, k, ret[i] = n//i, k+1, k+1
        if k > 0 or i == 97: sq = int(n**(1/2)+0.5)
        if i < 4: i = i * 2 - 1
        else: i, d = i+d, d^6
    if n > 1: ret[n] = 1
    return ret

P = 10**9+7
D = {}
N = int(input())
A = [int(a) for a in input().split()]
t = 0
for a in A:
    t += pow(a, P-2, P)
    pf = primeFactor(a)
    for p in pf:
        if p in D:
            D[p] = max(D[p], pf[p])
        else:
            D[p] = pf[p]
s = 1
for f in D:
    s = (s * pow(f, D[f], P)) % P
print(s * t % P)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


def eratosthenes(n):
    p = []
    t = [-1] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i] == -1:
            p.append(i)
            t[i] = i
            for j in range(2*i, n, i):
                if t[j] == -1:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == -1:
            p.append(j)
            t[j] = j

    return p, t

P, T = eratosthenes(10**6+1)

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

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

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

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

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

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

def factor(a):
    ps = Counter()
    while a != 1:
        f = T[a]
        while a % f == 0:
            ps[f] += 1
            a //= f
    return ps

@mt
def slv(N, A):
    lcm = Counter()
    for a in A:
        ps = factor(a)
        for k in ps.keys():
            lcm[k] = max(lcm[k], ps[k])

    M = Mod(10**9+7)
    l = 1
    for k, v in lcm.items():
        l = M.mul(l, M.pow(k, v))

    ans = 0
    for a in A:
        ans = M.add(ans, M.div(l, a))
    return ans


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


def eratosthenes(n):
    p = []
    t = [-1] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i] == -1:
            p.append(i)
            t[i] = i
            for j in range(2*i, n, i):
                if t[j] == -1:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == -1:
            p.append(j)
            t[j] = j

    return p, t

P, T = eratosthenes(10**6+1)

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

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

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

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

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

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

def factor(a):
    ps = Counter()
    while a != 1:
        f = T[a]
        while a % f == 0:
            ps[f] += 1
            a //= f
    return ps

@mt
def slv(N, A):
    lcm = Counter()
    for a in A:
        ps = factor(a)
        for k in ps.keys():
            lcm[k] = max(lcm[k], ps[k])

    M = Mod(10**9+7)
    l = 1
    for k, v in lcm.items():
        l = M.mul(l, M.pow(k, v))

    ans = 0
    for a in A:
        ans = M.add(ans, M.div(l, a))
    return ans


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    l = reduce(lambda x, y: x * y // gcd(x, y), A) % MOD
    b = [(l * pow(a, MOD - 2, MOD)) % MOD for a in A]
    return sum(b) % MOD

print(e_flatten())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


def eratosthenes(n):
    p = []
    t = [-1] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i] == -1:
            p.append(i)
            t[i] = i
            for j in range(2*i, n, i):
                if t[j] == -1:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == -1:
            p.append(j)
            t[j] = j

    return p, t

P, T = eratosthenes(10**6+1)

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

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

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

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

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

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

def factor(a):
    ps = Counter()
    k = set()
    while a != 1:
        f = T[a]
        if a % f == 0:
            k.add(f)
        while a % f == 0:
            ps[f] += 1
            a //= f
    return ps, k

@mt
def slv(N, A):
    lcm = Counter()
    for a in A:
        ps, fs = factor(a)
        for k in fs:
            lcm[k] = max(lcm[k], ps[k])

    M = Mod(10**9+7)
    l = 1
    for k, v in lcm.items():
        l = M.mul(l, M.pow(k, v))

    ans = 0
    for a in A:
        ans = M.add(ans, M.div(l, a))
    return ans


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import 周り
from fractions import gcd

# 定数関係
mod = 10 ** 9 + 7

# 補助関数
def inv(a):
    b, u, v = mod, 1, 0
    while b != 0:
        t = a // b
        a, b = b, a - t * b
        u, v = v, u - t * v
    return u

if __name__ == '__main__':
    #入力関係
    n = int(input())
    A = list(map(int, input().split()))

    U, V = 0, 1
    for ele in A:
      V *= ele // gcd(V, ele)# LCMを計算
      U += inv(ele)
    V %= mod
    print(U * V % mod)

Submission status: Accepted

Solution code:
# import 周り
from fractions import gcd

# 定数関係
mod = 10 ** 9 + 7

# 補助関数
def inv(a):
    b, u, v = mod, 1, 0
    while b != 0:
        t = a // b
        a, b = b, a - t * b
        u, v = v, u - t * v
    return u

if __name__ == '__main__':
    #入力関係
    n = int(input())
    A = list(map(int, input().split()))

    U, V = 0, 1
    for ele in A:
      V = V * ele // gcd(V, ele) # LCMを計算
      U += inv(ele)
    V %= mod
    print(U * V % mod)

Submission status: Accepted

Solution code:
# import 周り
from fractions import gcd

# 定数関係
mod = 10 ** 9 + 7

# 補助関数
def inv(a):
    b, u, v = mod, 1, 0
    while b != 0:
        t = a // b
        a, b = b, a - t * b
        u, v = v, u - t * v
        if u < 0: u += mod
    return u

if __name__ == '__main__':
    #入力関係
    n = int(input())
    A = list(map(int, input().split()))

    V = 1
    U = 0
    for ele in A:
      V = V * ele // gcd(V, ele) # LCMを計算
      U += inv(ele)
    V %= mod
    print(U * V % mod)

Submission status: Accepted

Solution code:
#最初のを試したところ、python のほうが早かった
#メモリが問題になるせいか？
#こちらでは？

from fractions import gcd
import random
n = int(input())
a = list(map(int, input().split( )))
random.shuffle(a)
#最小公倍数でよいか？
#全てのjについてAiBiはAjで割り切れる
#計算時間は？

mod =10**9+7


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

ag3 = ag1*ag2//gcd(ag1,ag2)

ans = 0

for i in range(n//2):
    ans += ag1//a[i]
ans*=ag3//ag1
ans %=mod
ans2 = 0
for i in range(n//2,n):
    ans2 += ag2//a[i]
ans2*= ag3//ag2
ans2%=mod 
ans += ans2
ans %=mod
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

MOD = 1000000000 + 7

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

def fact(a, n):
    r = 1
    while (n > 0):
        if (n & 1):
            r = (r * a) % MOD
        a = (a * a) % MOD
        n //= 2
    return r

def modinv(a):
    return fact(a, MOD-2)

l = 1
ans = 0
for a in A:
    l = l * a // gcd(a, l)
l %= MOD
ans = 0
for a in A:
    ans += (l * modinv(a)) % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
import fractions

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


mod = 10**9+7


N = int(input())

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

B = 0
for i in A:
    B += pow(i,mod-2,mod)
    B %= mod

g = 1

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

print (g * B % mod)

Submission status: Accepted

Solution code:
import fractions

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


mod = 10**9+7


N = int(input())

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

B = 0
for i in A:
    B += pow(i,mod-2,mod)
    B %= mod

g = 1

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

print (g * B % mod)

Submission status: Accepted

Solution code:
from functools import reduce
def gcd(a, b):
    while b: a, b = b, a % b
    return a
def lcm(a, b):
    return b//gcd(a, b)*a

P = 10**9+7
N = int(input())
A = [int(a) for a in input().split()]
print(reduce(lcm, A) % P * sum([pow(a, P-2, P) for a in A]) % P)

Submission status: Accepted

Solution code:
from collections import Counter

def resolve():
    # 方針
    # LCMを求めたい
    #  Aを素因数分解して、素因数ごとに肩のmaxを取りに行く
    #  max同士を掛け合わせる
    # B = X / A : 逆元
    #  B = A^(p-2) , p: 素数 prime

    # たくさんの数の素因数分解
    #     (1こだけの場合。Xに対し、sqrt(X)まで順に見て割り切れなければ素数として判定)
    #  (1) 素数列挙
    #    エラトステネスの篩
    #     素数と決まった数の倍数を消していく(最初は2)
    #     次の数にいく。消されてなければ素数。その数の倍数を消していく。(2乗となる倍数から開始すれば良い)　-> O(NloglogN)
    #     
    #  (2) 素因数分解
    #     上記の操作の時、何で割られたかメモしていく。すでに書かれているものは上書きしない。
    #     例:36. 36 ->2-> 18 ->2-> 9 ->3-> 3(prime) = 2x2x3x3 (sorted)
    #    => 素因数分解の完了
    # 
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split()))

    # 素数列挙 & 割った数の計算
    MX = int(10**6)
    L = [0] * (MX + 1)
    L[0] = -1
    L[1] = -1
    primes = []

    for i in range(2, MX+1):
        if L[i]:
            continue
        primes.append(i)
        L[i] = i
        for j in range(i*i, MX+1, i):
            if L[j] == 0:
                L[j] = i

    def factor(x: int):
        res = []
        while x != 1:
            prime = L[x] if L[x] != 0 else x
            res.append(prime)
            x /= prime
            x = int(x)
        return res

    max_e = {}
    for a in A:
        a = Counter(factor(a))
        for key, v in a.items():
            if not key in max_e:
                max_e[key] = v
            else:
                if v > max_e[key]:
                    max_e[key] = v
    # print(max_e)

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

    lcm = 1
    for key, v in max_e.items():
        lcm *= key ** v

    # print(max_e)
    # print(lcm)
    lcm %= MOD
    # print(lcm)

    ans = 0
    for i in range(N):
        b = lcm * modinv(A[i]) 
        ans += b

    print(int(ans % MOD))


def resolve_ref():
    from fractions import gcd
    
    mod = 10 ** 9 + 7
    
    N = int(input())
    A = list(map(int, input().split()))
    
    L = 1
    for a in A:
        L *= a // gcd(L, a)
    
    print(L)
    L %= mod
    print(L)
    
    print(sum(L * pow(a, mod - 2, mod) for a in A) % mod)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

P = 10**9+7
N = int(input())
A = [int(a) for a in input().split()]
L = 1
s = 0
for a in A:
    L = a // gcd(L, a) * L
    s += pow(a, P-2, P)
print(s * L % P)

Submission status: Accepted

Solution code:
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]]
def mod_inv(a,m):
  x=extgcd(a,m)[0]
  return (m+x%m)%m

def fact(n):
  fct=[]
  b,e=2,0
  while b*b<=n:
    while n%b==0:
      n=n//b
      e=e+1
    if e>0:
      fct.append((b,e))
    b,e=b+1,0
  if n>1:
    fct.append((n,1))
  return fct

n=int(input())
a=list(map(int,input().split()))
l=[0]*10**6
mod=10**9+7
for i in range(n):
  x=fact(a[i])
  for j in range(len(x)):
    l[x[j][0]]=max(l[x[j][0]],x[j][1])
lcm=1
for i in range(2,10**6):
  lcm*=(i**l[i])
  lcm%=mod
ans=0
for i in range(n):
  ans+=lcm*mod_inv(a[i],mod)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
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]]
def mod_inv(a,m):
  x=extgcd(a,m)[0]
  return (m+x%m)%m

def fact(n):
  fct=[]
  b,e=2,0
  while b*b<= n:
    while n%b==0:
      n=n//b
      e=e + 1
    if e>0:
      fct.append((b, e))
    b,e=b+1,0
  if n>1:
    fct.append((n, 1))
  return fct

n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(10**6)]
mod=10**9+7
for i in range(n):
  x=fact(a[i])
  for j in range(len(x)):
    l[x[j][0]]=max(l[x[j][0]],x[j][1])
lcm=1
for i in range(2,10**6):
  lcm*=(i**l[i])
  lcm%=mod
ans=0
for i in range(n):
  ans+=lcm*mod_inv(a[i],mod)
  ans%=mod
print(ans)

Submission status: Accepted

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

def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in a:
        x = (x * i) // gcd(x, i)
    return x

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

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