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):
from collections import defaultdict

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

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

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

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

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

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

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


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



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


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

lcm_mod = LCM_mod(max(a), MOD)

lcm_all = lcm_mod.lcm_list_mod(a)

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

Solution (Python):
from collections import defaultdict

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

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

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

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

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

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

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


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



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


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

lcm_mod = LCM_mod(max(a), MOD)

lcm_all = lcm_mod.lcm_list_mod(a)

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

Solution (Python):
from collections import defaultdict

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

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

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

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

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

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

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


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



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


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

lcm_mod = LCM_mod(10**6, MOD)

lcm_all = lcm_mod.lcm_list_mod(a)

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

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

from fractions import gcd

mod = int(1e9 + 7)

lcm = 1
for x in A:
    lcm = lcm * x // gcd(lcm, x)
lcm %= mod

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

print(ans)

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

from fractions import gcd

mod = int(1e9 + 7)

lcm = 1
for x in A:
    lcm = lcm * x // gcd(lcm, x)
lcm %= mod

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

print(ans)

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


def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

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

    pr = primes(10**3+1)

    d = defaultdict(lambda : 0)

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

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

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

if __name__ == '__main__':
    main()

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


def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


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

pr = primes(10**3+1)

d = defaultdict(lambda : 0)

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



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

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

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


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


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


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


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

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


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


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


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


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

Solution (Python):
import fractions
from functools import reduce
MOD = 10**9 + 7
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

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

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

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

ans %= MOD
print(ans)

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

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

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

print(ans%mod)

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

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

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

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

print(ans%mod)

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

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

n=max(A)+5


is_prime = [True]*(n+1)
is_prime[0] = False

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

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



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

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

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

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

print(e_flatten())

Solution (Python):
import fractions
from functools import reduce
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

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

N = int(input())
l = list(map(int, input().split(" ")))
 
p = lcm_list(l)
c = 0
for i in l:
  c += p // i
print(c % (10 ** 9 + 7))

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

















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

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

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

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

print(e_flatten())

Solution (Python):
from fractions import gcd
from functools import reduce
 
N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
 
answer = sum(lcm//x for x in A)
answer %= MOD
print(answer)

Solution (Python):
from fractions import gcd
from functools import reduce
lcm=lambda x,y:x//gcd(x,y)*y
MOD=10**9+7

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

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

print(c*l%MOD)

Solution (Python):
from fractions import gcd


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


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


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


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

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

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

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

print(ans)

Solution (Python):
import functools
import fractions
MOD = 10**9+7


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


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


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


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

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

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

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


main()

Solution (Python):

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


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


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

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

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

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

Solution (Python):
from fractions import gcd


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


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


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


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

Solution (Python):


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


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


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


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

MOD = 10**9 + 7

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

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

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

print(ans%MOD)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

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

MOD = 10 ** 9 + 7

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

answer = sum(lcm//x for x in A)
answer %= MOD
print(answer)

Solution (Python):
from functools import reduce

MOD = 10 ** 9 + 7

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

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

def lcmArr(a):
    return reduce(getLcm, a)

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

lcm = lcmArr(a)
lcm %= MOD
ret = 0
for val in a:
    ret += lcm * pow(val, MOD - 2, MOD)
    ret %= MOD
print(ret)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
lcm = a[0]

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

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

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

MOD = 10 ** 9 + 7

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

answer = sum(lcm//x for x in A)
answer %= MOD
print(answer)

Solution (Python):


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


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


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


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

MOD = 10**9 + 7

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

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

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

print(ans%MOD)

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

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

MOD = 10 ** 9 + 7

lcm = reduce(lambda x,y: y//gcd(x,y)*x, A)
lcm %= MOD

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

print(answer)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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


def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)

class InverseTable:
    __slots__ = ['In', 'fac', 'Ifac']

    def __init__(self, mod, maxnum):
        self.In = [0, 1]; self.fac = [1, 1]; self.Ifac = [1, 1]
        for i in range( 2, maxnum + 1 ):
            self.fac.append( ( self.fac[-1] * i ) % mod )
            self.In.append( ( -self.In[mod % i] * (mod//i) ) % mod )
            self.Ifac.append( (self.Ifac[-1] * self.In[-1]) % mod )
        
    def cmb(self, n, r):
        if ( r<0 or r>n ): return 0
        r = min(r, n-r)
        return self.fac[n] * self.Ifac[r] * self.Ifac[n-r] % mod

it = InverseTable(mod, 10**6)

for ai in A:
    pro=lcm(pro,ai)
for ai in A:
    ans+=it.In[ai]
    ans%=mod
print((pro*ans)%mod)

Solution (Python):
from fractions import gcd
N = int(input())
A = [int(i) for i in 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
cur_prime = {}
for i in range(N):
    S = factorization(A[i])
    for j in range(len(S)):
        if S[j][0] not in cur_prime:
            cur_prime[S[j][0]] = S[j][1]
        else:
            cur_prime[S[j][0]] = max(S[j][1],cur_prime[S[j][0]])
A_lcm = 1
key = list(cur_prime.keys())
value = list(cur_prime.values())
for i in range(len(key)):
    for j in range(value[i]):
        A_lcm *= key[i]
        A_lcm %= mod
ans = 0
for i in range(N):
    ans += A_lcm*pow(A[i],mod-2,mod)
    ans %= mod
print(ans)

Solution (Python):
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%p
    else:
        return (x*(pow(x,(m-1)//2)**2)%p)%p
P = [1 for _ in range(10**6+1)]
P[0]=0
P[1]=0
for i in range(2,10**3+1):
    for j in range(i*i,10**6+1,i):
        P[j] = 0
Q = {}
for i in range(2,10**6+1):
    if P[i]==1:
        Q[i] = 0
Q1 = sorted(list(Q.keys()))
p = 10**9+7
N = int(input())
A = list(map(int,input().split()))
for i in range(N):
    a = A[i]
    for b in Q1:
        if a%b==0:
            cnt = 0
            while a%b==0:
                a = a//b
                cnt += 1
            Q[b] = max(Q[b],cnt)
            if a==1:break
        elif b>1000 and a>1:
            Q[a] = max(Q[a],1)
            break
        else:continue
lcmA = 1
for b in Q:
    cnt = 1
    for i in range(Q[b]):
        cnt = (cnt*b)%p
    lcmA = (lcmA*cnt)%p
tot = 0
for i in range(N):
    tot = (tot+lcmA*pow(A[i],p-2))%p
print(tot)

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

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

def lcm(x, y):
    return x/gcd(x, y)*y
 
l = A[0]
for a in A:
    l = lcm(l, a)
 
res = 0
for a in A:
    res = (res + (l * pow(a, MOD - 2, MOD)) % MOD) % MOD
 
print(res)

Solution (Python):
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N = int(input())
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
for i in A:
  a = lcm(a,i)
ans = 0
for i in A:
  ans += (a//i)
print(ans%MOD)

Solution (Python):
import fractions
n = int(input())
a = list(map(int,input().split()))

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

val = a[0]
for i in range(1,n):
    val = lcm(val,a[i])

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

Solution (Python):
from functools import reduce

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

def gcd(a, b):
    
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend

    
    while dividend % divider != 0:
        
        r = dividend % divider
        dividend = divider
        divider = r

    
    return divider


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

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

L = reduce(lcm, a)

for i in range(n):
    
    ans += L * modinv(a[i])

print(ans % mod)

Solution (Python):
from functools import reduce

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

def gcd(a, b):
    
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend

    
    while dividend % divider != 0:
        
        r = dividend % divider
        dividend = divider
        divider = r

    
    return divider


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

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

b = list(set(a))



L = reduce(lcm, b)



for i in range(n):
    
    ans += L * modinv(a[i])

print(ans % mod)

Solution (Python):
import sys
read = sys.stdin.buffer.read

from fractions import gcd

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

lcm = 1
answer = 0
for x in A:
  n = x//gcd(lcm,x)
  lcm *= n
  answer *= n
  answer += lcm//x
  
answer %= (10**9 + 7)
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

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

MOD = 10 ** 9 + 7

lcm = 1
answer = 0
for x in A:
  n = x//gcd(lcm,x)
  lcm *= n
  answer *= n
  answer += lcm//x
  
answer %= MOD
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

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

MOD = 10 ** 9 + 7

lcm = 1
answer = 0
for x in A:
  n = x//gcd(lcm,x)
  lcm *= n
  answer *= n 
  answer %= MOD
  answer += lcm//x % MOD
  
answer %= MOD
print(answer)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

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

MOD = 10 ** 9 + 7

lcm = 1
answer = 0
for x in A:
  n = x//gcd(lcm,x)
  lcm *= n
  answer *= n
  answer += lcm//x
  
answer %= MOD
print(answer)

Solution (Python):
import fractions 

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

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

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

ret = 0
for a in A:
    ret += (_lcm // a)

print(ret%MODE)

Solution (Python):
import fractions

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    prev_lc = 1
    ans = 0
    for i in A:
        lc = lcm(prev_lc, i)
        ans = ans * (lc // prev_lc) + lc // i
        prev_lc = lc
    print(ans % 1000000007)

if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
if n == 1:
	print(1)
else:
	lcm = a[0] * a[1] // gcd(a[0], a[1])
	for x in a[2:]:
		lcm = lcm * x // gcd(lcm, x)
	lcm %= MOD
	ans = 0
	for x in a:
		ans += lcm * pow(x, MOD-2, MOD)
		ans %= MOD
	print(ans)

Solution (Python):
import fractions
def lcm(a, b):
  return a*b // fractions.gcd(a, b)

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

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

print(ans % 1000000007)

Solution (Python):
from functools import reduce

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

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

def lcm_list(A): return reduce(lcm, A)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
L = lcm_list(A)
ans = 0
for a in A:
    ans += L // a
print(ans % MOD)

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

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

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

hcm = arr[0]
for i in range(1,n):
    hcm = lcm(hcm,arr[i])

res = 0
for num in arr:
    res += (hcm//num)
    

print(res%N)

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

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

def lcm_list(A):
    l = A[0]
    for a in A[1:]:
        l = lcm(l, a)
    return l

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
L = lcm_list(A)
ans = 0
for a in A:
    ans += L // a
print(ans % MOD)