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) .

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

def gcd(a, b):
    while b: a, b = b, a % b
    return a
def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1
def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g): return g
            elif isPrimeMR(n // g): return n // g
            return findFactorRho(g)
def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k
 
    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret
  
lcd = dict()
for i in num:
  j = primeFactor(i)
  for x,y in j.items():
    if not x in lcd.keys():
      lcd[x] = y
    else:
      lcd[x] = max(lcd[x],y)

lc = 1
for i,j in lcd.items():
  lc *= pow(i,j,mod)
  
ans =0
for i in range(n):
  ans += lc*pow(num[i], mod-2, mod)
  ans %= mod
print(ans)

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

from collections import Counter
def factorization(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 Counter(yy)
      
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
  
lcd = dict()
for i in num:
  j = primeFactor(i)
  for x,y in j.items():
    if not x in lcd.keys():
      lcd[x] = y
    else:
      lcd[x] = max(lcd[x],y)

lc = 1
for i,j in lcd.items():
  lc *= pow(i,j,mod)
  
ans =0
for i in range(n):
  ans += lc*pow(num[i], mod-2, mod)
  ans %= mod
print(ans)

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

from collections import Counter
def factorization(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 Counter(yy)
      
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
  
lcd = dict()
for i in num:
  j = factorization(i)
  for x,y in j.items():
    if not x in lcd.keys():
      lcd[x] = y
    else:
      lcd[x] = max(lcd[x],y)

lc = 1
for i,j in lcd.items():
  lc *= pow(i,j,mod)
  
ans =0
for i in range(n):
  ans += lc*pow(num[i], mod-2, mod)
  ans %= mod
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N = getN()
A = getList()
prime_list = defaultdict(int)

def prime_factorize(n):
    divisors = []
    
    temp = n
    for i in range(2, int(math.sqrt(n)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                
                temp //= i
            divisors.append([i, cnt])
    if temp != 1:
        divisors.append([temp, 1])
    if divisors == []:
        divisors.append([n, 1])

    return divisors

for i in range(N):
    prime = prime_factorize(A[i])
    for j in prime:
        prime_list[j[0]] = max(prime_list[j[0]], j[1])

num = 1
for key, value in prime_list.items():
    num *= key ** value
    num %= mod


lim = 10 ** 6 + 1
fact = [1, 1]
inv = [0, 1]

for i in range(2, lim + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)

ans = 0
for i in A:
    opt = (num * inv[i]) % mod
    ans += opt
    ans %= mod
print(ans % mod)

Solution (Python):





from collections import defaultdict
from math import gcd

MOD = 10 ** 9 + 7

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

lcm = A[0]
for a in A:
    lcm = (lcm * a) // gcd(lcm, a)
lcm %= MOD


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

Solution (Python):
from math import gcd
from functools import reduce

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

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

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

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

print(ans)

Solution (Python):
from math import gcd
from functools import reduce

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

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

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

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

print(ans)

Solution (Python):
import sys
from collections import defaultdict, Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    N_MAX = 10 ** 6

    min_factor = list(range(1, N_MAX + 1, 2))
    for i in range(1, int((N_MAX ** 0.5 - 1) / 2) + 1):
        f = 2 * i + 1
        if min_factor[i] != f:
            continue
        for j in range(2 * i * (i + 1), len(min_factor), f):
            if min_factor[j] > f:
                min_factor[j] = f

    def prime_factorize_fast(n):
        a = Counter()
        while not n & 1:
            a[2] += 1
            n //= 2
        while n != 1:
            a[min_factor[(n - 1) // 2]] += 1
            n //= min_factor[(n - 1) // 2]

        return a

    lcm_prime = Counter()
    for a in A:
        for p, n in prime_factorize_fast(a).items():
            if lcm_prime[p] < n:
                lcm_prime[p] = n

    l = 1
    for p, n in lcm_prime.items():
        l = l * pow(p, n, MOD) % MOD

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

    ans = ans * l % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict, Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    N_MAX = 10 ** 6

    min_factor = list(range(1, N_MAX + 1, 2))
    for i in range(1, int((N_MAX ** 0.5 - 1) / 2) + 1):
        if min_factor[i] != 2 * i + 1:
            continue
        for j in range(2 * i * (i + 1), len(min_factor), 2 * i + 1):
            if min_factor[j] > 2 * i + 1:
                min_factor[j] = 2 * i + 1

    def prime_factorize_fast(n):
        a = Counter()
        while not n & 1:
            a[2] += 1
            n //= 2
        while n != 1:
            a[min_factor[(n - 1) // 2]] += 1
            n //= min_factor[(n - 1) // 2]

        return a

    lcm_prime = Counter()
    for a in A:
        for p, n in prime_factorize_fast(a).items():
            if lcm_prime[p] < n:
                lcm_prime[p] = n

    l = 1
    for p, n in lcm_prime.items():
        l = l * pow(p, n, MOD) % MOD

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

    ans = ans * l % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict, Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    N_MAX = 10 ** 6

    min_factor = list(range(N_MAX + 1))
    min_factor[2::2] = [2] * (N_MAX // 2)
    for i in range(3, int(N_MAX ** 0.5) + 2, 2):
        if min_factor[i] != i:
            continue
        for j in range(i * i, N_MAX + 1, 2 * i):
            if min_factor[j] > i:
                min_factor[j] = i

    def prime_factorize_fast(n):
        a = Counter()
        while n != 1:
            a[min_factor[n]] += 1
            n //= min_factor[n]

        return a

    lcm_prime = Counter()
    for a in A:
        for p, n in prime_factorize_fast(a).items():
            if lcm_prime[p] < n:
                lcm_prime[p] = n

    l = 1
    for p, n in lcm_prime.items():
        l = l * pow(p, n, MOD) % MOD

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

    ans = ans * l % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict, Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    N_MAX = 10 ** 6

    min_factor = list(range(N_MAX + 1))
    min_factor[2::2] = [2] * (N_MAX // 2)
    for i in range(3, int(N_MAX ** 0.5) + 2, 2):
        if min_factor[i] != i:
            continue
        for j in range(i * i, N_MAX + 1, 2 * i):
            if min_factor[j] > i:
                min_factor[j] = i

    def prime_factorize_fast(n):
        a = Counter()
        while n != 1:
            f = min_factor[n]
            p = 0
            while min_factor[n] == f:
                p += 1
                n //= f
            a[f] = p

        return a

    lcm_prime = Counter()
    for a in A:
        for p, n in prime_factorize_fast(a).items():
            if lcm_prime[p] < n:
                lcm_prime[p] = n

    l = 1
    for p, n in lcm_prime.items():
        l = l * pow(p, n, MOD) % MOD

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

    ans = ans * l % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

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

def factor(n, m=None):
    
    arr = {}
    temp = n
    M = int(-(-n**0.5//1))+1
    if m is not None:
        M = min(m+1, M)
    for i in range(2, M):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr

ds = [factor(num) for num in a]
D = {}
for d in ds:
    for k,v in d.items():
        if k in D:
            D[k] = max(D[k], v)
        else:
            D[k] = v
l = 1
for k,v in D.items():
    l *= pow(k,v,M)
    l %= M
ans = 0
for num in a:
    ans += (l*pow(num, M-2, M))
    ans %= M
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


class Eratosthenes:
    def __init__(self, n):
        self.n = n
        self.min_factor = [-1] * (n + 1)
        self.min_factor[0], self.min_factor[1] = 0, 1

    def get_primes(self):
        primes = []
        is_prime = [True] * (self.n + 1)
        is_prime[0] = is_prime[1] = False
        for i in range(2, self.n + 1):
            if not is_prime[i]:
                continue
            primes.append(i)
            self.min_factor[i] = i
            for j in range(i * 2, self.n + 1, i):
                is_prime[j] = False
                if self.min_factor[j] == -1:
                    self.min_factor[j] = i
        return primes

    def prime_factorization(self, n):
        res = []
        while n != 1:
            prime = self.min_factor[n]
            exp = 0
            while self.min_factor[n] == prime:
                exp += 1
                n //= prime
            res.append([prime, exp])
        return res


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    MAX_A = max(A) + 1

    er = Eratosthenes(MAX_A)
    er.get_primes()
    num = [0] * MAX_A
    for i in range(n):
        pf = er.prime_factorization(A[i])
        for p, ex in pf:
            num[p] = max(num[p], ex)

    LCM = 1
    for v in range(2, MAX_A):
        LCM *= pow(v, num[v], mod)
        LCM %= mod

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


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
from math import gcd

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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


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

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

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


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append([i, ex])
    if n != 1:
        res.append([n, 1])
    return res


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

    prime = [0] * max(A)
    for a in A:
        primes = prime_factorization(a)
        for num, ex in primes:
            prime[num - 1] = max(prime[num - 1], ex)

    L = 1
    for i in range(len(prime)):
        if prime[i] == 0:
            continue
        L *= pow(i + 1, prime[i])

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


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
from collections import defaultdict, Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())

    N_MAX = 10 ** 6

    min_factor = list(range(N_MAX + 1))
    min_factor[2::2] = [2] * (N_MAX // 2)
    for i in range(3, int(N_MAX ** 0.5) + 2, 2):
        if min_factor[i] != i:
            continue
        for j in range(i * i, N_MAX + 1, i):
            if min_factor[j] > i:
                min_factor[j] = i

    def prime_factorize_fast(n):
        a = Counter()
        while n != 1:
            f = min_factor[n]
            p = 0
            while min_factor[n] == f:
                p += 1
                n //= f
            a[f] = p

        return a

    lcm_prime = Counter()
    for a in A:
        for p, n in prime_factorize_fast(a).items():
            if lcm_prime[p] < n:
                lcm_prime[p] = n

    l = 1
    for p, n in lcm_prime.items():
        l = l * pow(p, n, MOD) % MOD

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

    ans = ans * l % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict, Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
    N, *A = map(int, read().split())
    
    N_MAX = 10 ** 6

    min_factor = [0] * (N_MAX + 1)
    min_factor[1] = 1
    for i in range(2, N_MAX + 1):
        if min_factor[i]:
            continue
        for j in range(i, N_MAX + 1, i):
            if not min_factor[j]:
                min_factor[j] = i


    def prime_factorize_fast(n):
        a = Counter()
        while n != 1:
            f = min_factor[n]
            p = 0
            while min_factor[n] == f:
                p += 1
                n //= f
            a[f] = p

        return a

    lcm_prime = Counter()
    for a in A:
        for p, n in prime_factorize_fast(a).items():
            if lcm_prime[p] < n:
                lcm_prime[p] = n

    l = 1
    for p, n in lcm_prime.items():
        l = l * pow(p, n, MOD) % MOD

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

    ans = ans * l % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict, Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def prime_factorize(n):
    a = Counter()
    while n % 2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] += 1
    return a


def main():
    N, *A = map(int, read().split())

    lcm_prime = Counter()
    for a in A:
        for p, n in prime_factorize(a).items():
            if lcm_prime[p] < n:
                lcm_prime[p] = n

    l = 1
    for p, n in lcm_prime.items():
        l = l * pow(p, n, MOD) % MOD

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

    ans = ans * l % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import defaultdict, Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def prime_factorize(n):
    a = Counter()
    while n % 2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] += 1
    return a


def main():
    N, *A = map(int, read().split())

    lcm_prime = Counter()
    for i in range(N):
        for p, n in prime_factorize(A[i]).items():
            if lcm_prime[p] < n:
                lcm_prime[p] = n

    l = 1
    for p, n in lcm_prime.items():
        l = l * pow(p, n, MOD) % MOD

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

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from math import gcd
from functools import reduce

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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


def main():
    N, *A = map(int, read().split())

    ans = 0
    l = 1
    for a in A:
        l, l_prev = lcm(l, a), l
        ans = (ans * (l // l_prev) % MOD + l // a) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict


class PrimeFactor():

    def __init__(self, n):                  
        self.n = n
        self.table = list(range(n+1))
        self.table[2::2] = [2]*(n//2)
        for p in range(3, int(n**0.5) + 2, 2):
            if self.table[p] == p:
                for q in range(p * p, n + 1, 2 * p):
                    if self.table[q] == q:
                        self.table[q] = p

    def is_prime(self, x):  
        if x < 2:
            return False
        return self.table[x] == x

    def prime_factors(self, x):             
        res = []
        if x < 2:
            return res
        while self.table[x] != 1:
            res.append(self.table[x])
            x //= self.table[x]
        return res

    def prime_counter(self, x):             
        res = defaultdict(int)
        if x < 2:
            return res
        while self.table[x] != 1:
            res[self.table[x]] += 1
            x //= self.table[x]
        return res

    def prime_gcd(self, X):                 
        exponents = self.prime_counter(X[0])
        for x in X[1:]:
            Y = self.prime_counter(x)
            for prime, exp in exponents.items():
                if Y[prime] < exp:
                    exponents[prime] = Y[prime]
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp)
        return res

    def prime_lcm(self, X, mod=None):       
        exponents = defaultdict(int)
        for x in X:
            for prime, exp in self.prime_counter(x).items():
                if exp > exponents[prime]:
                    exponents[prime] = exp
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp, mod)
        if mod == None:
            return res
        else:
            return res % mod

mod = 10 ** 9 + 7

N = int(input())
A = list(map(int, input().split()))
A.sort()
table = PrimeFactor(10**6)
num = table.prime_lcm(A,mod)

res = 0
for a in A:
    res += num * pow(a, mod - 2, mod)

print(res % mod)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict


class PrimeFactor():

    def __init__(self, n):                  
        self.n = n
        self.table = list(range(n+1))
        self.table[2::2] = [2]*(n//2)
        for p in range(3, int(n**0.5) + 2, 2):
            if self.table[p] == p:
                self.table[p * p::2 * p] = [p] * ((n - p * p - 1) // (2 * p) + 1)

    def is_prime(self, x):  
        if x < 2:
            return False
        return self.table[x] == x

    def prime_factors(self, x):             
        res = []
        if x < 2:
            return res
        while self.table[x] != 1:
            res.append(self.table[x])
            x //= self.table[x]
        return res

    def prime_counter(self, x):             
        res = defaultdict(int)
        if x < 2:
            return res
        while self.table[x] != 1:
            res[self.table[x]] += 1
            x //= self.table[x]
        return res

    def prime_gcd(self, X):                 
        exponents = self.prime_counter(X[0])
        for x in X[1:]:
            Y = self.prime_counter(x)
            for prime, exp in exponents.items():
                if Y[prime] < exp:
                    exponents[prime] = Y[prime]
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp)
        return res

    def prime_lcm(self, X, mod=None):       
        exponents = defaultdict(int)
        for x in X:
            for prime, exp in self.prime_counter(x).items():
                if exp > exponents[prime]:
                    exponents[prime] = exp
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp, mod)
        if mod == None:
            return res
        else:
            return res % mod

mod = 10 ** 9 + 7

N = int(input())
A = list(map(int, input().split()))
B = set(A)
B = list(A)
table = PrimeFactor(10**6)
num = table.prime_lcm(B,mod)

res = 0
for a in A:
    res += num * pow(a, mod - 2, mod)

print(res % mod)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict


class PrimeFactor():

    def __init__(self, n):                  
        self.n = n
        self.table = list(range(n+1))
        self.table[2::2] = [2]*(n//2)
        for p in range(3, int(n**0.5) + 2, 2):
            if self.table[p] == p:
                self.table[p * p::2 * p] = [p] * ((n - p * p - 1) // (2 * p) + 1)

    def is_prime(self, x):  
        if x < 2:
            return False
        return self.table[x] == x

    def prime_factors(self, x):             
        res = []
        if x < 2:
            return res
        while self.table[x] != 1:
            res.append(self.table[x])
            x //= self.table[x]
        return res

    def prime_counter(self, x):             
        res = defaultdict(int)
        if x < 2:
            return res
        while self.table[x] != 1:
            res[self.table[x]] += 1
            x //= self.table[x]
        return res

    def prime_gcd(self, X):                 
        exponents = self.prime_counter(X[0])
        for x in X[1:]:
            Y = self.prime_counter(x)
            for prime, exp in exponents.items():
                if Y[prime] < exp:
                    exponents[prime] = Y[prime]
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp)
        return res

    def prime_lcm(self, X, mod=None):       
        exponents = defaultdict(int)
        for x in X:
            for prime, exp in self.prime_counter(x).items():
                if exp > exponents[prime]:
                    exponents[prime] = exp
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp, mod)
        if mod == None:
            return res
        else:
            return res % mod

mod = 10 ** 9 + 7

N = int(input())
A = list(map(int, input().split()))
A.sort()
table = PrimeFactor(10**6)
num = table.prime_lcm(A,mod)

res = 0
for a in A:
    res += num * pow(a, mod - 2, mod)

print(res % mod)

Solution (Python):


import sys
read = sys.stdin.read

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


def min_factor(n):
    sieve = list(range(n + 1))
    sieve[2::2] = [2] * (n // 2)
    for i in range(3, int(n ** 0.5) + 2, 2):
        if sieve[i] == i:
            sieve[i * i::2 * i] = [i] * ((n - i * i) // (2 * i) + 1)
    return sieve


def prime_factorize(n):
    a = {}
    while n != 1:
        b = table[n]
        if b in a:
            a[b] += 1
        else:
            a[b] = 1
        n //= b
    return a


table = min_factor(10**6)

dic = {}
for i in A:
    for key, value in prime_factorize(i).items():
        if key in dic:
            dic[key] = max(dic[key], value)
        else:
            dic[key] = value

lcm = 1
for i, j in dic.items():
    lcm *= pow(i, j, mod)
    lcm %= mod

answer = sum(lcm * pow(i, mod - 2, mod) for i in A) % mod
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict


class PrimeFactor():

    def __init__(self, n):                  
        self.n = n
        self.table = list(range(n+1))
        self.table[2::2] = [2]*(n//2)
        for p in range(3, int(n**0.5) + 2, 2):
            if self.table[p] == p:
                self.table[p * p::2 * p] = [p] * ((n - p * p - 1) // (2 * p) + 1)

    def is_prime(self, x):  
        if x < 2:
            return False
        return self.table[x] == x

    def prime_factors(self, x):             
        res = []
        if x < 2:
            return res
        while self.table[x] != 1:
            res.append(self.table[x])
            x //= self.table[x]
        return res

    def prime_counter(self, x):             
        res = defaultdict(int)
        if x < 2:
            return res
        while self.table[x] != 1:
            res[self.table[x]] += 1
            x //= self.table[x]
        return res

    def prime_gcd(self, X):                 
        exponents = self.prime_counter(X[0])
        for x in X[1:]:
            Y = self.prime_counter(x)
            for prime, exp in exponents.items():
                if Y[prime] < exp:
                    exponents[prime] = Y[prime]
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp)
        return res

    def prime_lcm(self, X, mod=None):       
        exponents = defaultdict(int)
        for x in X:
            for prime, exp in self.prime_counter(x).items():
                if exp > exponents[prime]:
                    exponents[prime] = exp
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp, mod)
        if mod == None:
            return res
        else:
            return res % mod

mod = 10 ** 9 + 7

N = int(input())
A = list(map(int, input().split()))
table = PrimeFactor(10**6)
num = table.prime_lcm(A,mod)

res = 0
for a in A:
    res += num * pow(a, mod - 2, mod)

print(res % mod)