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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
import math
from functools import reduce

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

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

x = reduce(lcm, a)

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

print(ans%1000000007)

Solution (Python):
from collections import Counter

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

lcm = Counter([])
for a in A:
    tmp = []
    d = 2
    while d*d <= a:
        while a%d == 0:
            tmp.append(d)
            a //= d
        d += 1
    if a != 1:
        tmp.append(a)
    tmp = Counter(tmp)
    for k,v in tmp.items():
        if k not in lcm or v > lcm[k]:
            lcm[k] = v

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

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

print(ans)

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

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


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

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

    a_lcm = reduce(lcm, a)
    print(sum([a_lcm * pow(aa, mod - 2, mod) % mod for aa in a]) % mod)


if __name__ == '__main__':
    main()

Solution (Python):
import math
from functools import reduce

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
N = int(input())
A = list(map(int,input().split()))
ans = 0

lcm = lcm_list(A)

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

print(ans%1000000007)

Solution (Python):
from collections import defaultdict

ps = []
for i in range(2, 1000):
    is_p = True
    for j in range(2, i):
        if i % j == 0:
            is_p = False
            break
    if is_p:
        ps.append(i)

def factorization(n):
    arr = defaultdict(int)
    temp = n
    for i in ps:
        if i > int(-(-n**0.5//1))+1:
            break
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt
    if temp!=1:
        arr[temp] = 1
    if arr==[]:
        arr[n] = 1
    return arr


aa = defaultdict(int)

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

fs = [[]] * 1000001
for i in a:
    if not fs[i]:
        fs[i] = factorization(i)

for i in a:
    for k, v in fs[i].items():
        aa[k] = max(aa[k], v)


mod = 10 ** 9 + 7
t = 1
for k, v in aa.items():
    t = (t * (k ** v)) % mod
ans = 0
for i in a:
    ans += t * pow(i, mod - 2, mod)
    ans %= mod
print(ans)

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

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

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

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

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

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

Solution (Python):
import math
N = int(input())
A = list(map(int,input().split()))
B = [0] * (N)
lcmall = A[0]
for i in range(1,N):
    gcdall = math.gcd(lcmall,A[i])
    lcmall = lcmall*A[i] // gcdall
sum = 0
for i in range(N):
    B[i] =int(lcmall // A[i])
    sum += B[i]
print(sum % (10 ** 9 + 7))

Solution (Python):
from collections import Counter

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

divide = []
for a in A:
    tmp = []
    d = 2
    while d*d <= a:
        while a % d == 0:
            a //= d
            tmp.append(d)
        d += 1
    if a != 1:
        tmp.append(a)
    divide.append(Counter(tmp))

count = Counter([])
for d in divide:
    for k,v in d.items():
        if k not in count:
            count[k] = v
        else:
            count[k] = max(count[k],v)

LCM = 1
for k,v in count.items():
    LCM *= pow(k,v,mod)
    LCM %= mod

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

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

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

def main():
    mod=10**9+7
    from collections import defaultdict
    
    def factorization(n):
        if n==1:
            return [[1,0]]
        arr = []
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr.append([i, cnt])

        if temp!=1:
            arr.append([temp, 1])

        if arr==[]:
            arr.append([n, 1])

        return arr
    
    lcm_dd = defaultdict(int)
    
    N=I()
    A=LI()
    for i in range(N):
        a=A[i]
        arr=factorization(a)
        for v in arr:
            p,cnt=v
            lcm_dd[p]=max(lcm_dd[p],cnt)
            
    lcm=1
    for k,v in lcm_dd.items():
        temp=pow(k,v,mod)
        lcm=(lcm*temp)%mod
        
    ans=0
    for i in range(N):
        temp=(lcm*pow(A[i],mod-2,mod))%mod
        ans=(ans+temp)%mod
        
    print(ans%mod)
        
    


main()

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int,input().split()))

divide = []
for i in range(N):
    a = A[i]
    tmp = []
    d = 2
    while d*d <= a:
        while a%d == 0:
            tmp.append(d)
            a //= d
        d += 1
    if a != 1:
        tmp.append(a)
    divide.append(Counter(tmp))

lcm = Counter([])
for count in divide:
    for k,v in count.items():
        if k not in lcm:
            lcm[k] = v
        else:
            lcm[k] = max(lcm[k],v)

mod = 10**9 +7
LCM = 1
for k,v in lcm.items():
    LCM *= pow(k,v,mod)
    LCM %= mod

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

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


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


def read_float():
    return float(readline())


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


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


def read_str_n():
    return readline().strip().split()


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


def mt(f):
    import time

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

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

    return wrap


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

@mt
def slv(N, A):
    c = Counter()
    for a in A:
        while a != 1:
            p = T[a]
            t = 0
            while a % p == 0:
                t += 1
                a //= p
            if t > 0:
                c[p] = max(c[p], t)
            if a == 1:
                break

    M = Mod(10**9+7)
    L = 1
    for k, v in c.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()

Solution (Python):

import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys


readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


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


def read_float():
    return float(readline())


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


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


def read_str_n():
    return readline().strip().split()


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


def mt(f):
    import time

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

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

    return wrap


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)


@mt
def slv(N, A):
    M = Mod(10**9 + 7)
    def lcm(a, b):
        return a // math.gcd(a, b) * b
    b = reduce(lcm, A)
    ans = 0
    for a in A:
        ans = M.add(ans, M.div(b, a))
    return ans


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


if __name__ == '__main__':
    main()

Solution (Python):
import math
import sys
input = sys.stdin.readline

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

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

mod = 10**9 + 7

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


b_sum = 0
for i in range(N):
    b_sum += a_lcm // A[i]

print(b_sum % mod)

Solution (Python):
from collections import Counter
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
prime = [0] * (10**6+1)
for i in range(N):
    c = Counter(prime_factorize(A[i]))
    for j in c.items():
        prime[j[0]] = max(j[1],prime[j[0]])
lcm = 1
for i in range(10**6):
    if prime[i] > 0:
        lcm *= pow(i,prime[i])
        lcm %= MOD

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

Solution (Python):
import math
import sys
input = sys.stdin.readline

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

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

mod = 10**9 + 7

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


b_sum = 0
for i in range(N):
    b_sum += a_lcm // A[i]

print(b_sum % mod)

Solution (Python):
from collections import Counter
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
prime = [0] * (10**6+5)
for i in range(N):
    c = Counter(prime_factorize(A[i]))
    for j in c.items():
        prime[j[0]] = max(j[1],prime[j[0]])
lcm = 1
for i in range(10**6+2):
    if prime[i] > 0:
        lcm *= pow(i,prime[i])
        lcm %= MOD

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

Solution (Python):
from collections import Counter
MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))


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


prime = [0] * (10**6+1)
for i in range(N):
    c = Counter(prime_factorize(A[i]))
    for j in c.items():
        prime[j[0]] = max(j[1], prime[j[0]])
lcm = 1
for i in range(10**6):
    if prime[i] > 0:
        lcm *= pow(i, prime[i],MOD)

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

Solution (Python):
import math
import sys
input = sys.stdin.readline

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

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

mod = 10**9 + 7

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


b_sum = 0
for i in range(N):
    b_sum += a_lcm // A[i]

print(b_sum % mod)

Solution (Python):
import math
from typing import List, Counter, Tuple
from collections import Counter
from itertools import permutations, zip_longest, groupby


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))

modulo = 10**9+7


def merge(A, start, end, divisors):
    if start == end:
        return Counter(divisors[A[start]])
    mid = start+(end-start)//2
    left = merge(A, start, mid, divisors)
    right = merge(A, mid+1, end, divisors)
    for r in right:
        left[r] = max(left[r], right[r])
    return left

def solve() -> int:
    N = read_int()
    A = read_ints()
    M = 10**6+1
    divisors: List[List[int]] = [[] for _ in range(M)]
    for i in range(2, M):
        if len(divisors[i]) == 0:
            for j in range(i, M, i):
                temp = j
                while temp%i == 0:
                    divisors[j].append(i)
                    temp //= i
    lcd_counter = merge(A, 0, N-1, divisors)
    lcd = 1
    for k in lcd_counter:
        lcd = (lcd*pow(k, lcd_counter[k], modulo))%modulo
    answer = 0
    for a in A:
        answer = (answer+(lcd*pow(a, modulo-2, modulo))%modulo)%modulo
    return answer


if __name__ == '__main__':
    print(solve())

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

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

a_lcm = 1
for ai in a:
    a_lcm = lcm(a_lcm, ai)

b_sum = 0
for i in range(n):
    b_sum += a_lcm // a[i]

print(b_sum%mod)

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

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

a_lcm = 1
for ai in a:
    a_lcm = lcm(a_lcm, ai)

b_sum = 0
for ai in a:
    b_sum += a_lcm // ai

print(b_sum%mod)

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

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

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

b_sum = 0
for ai in a:
    b_sum += a_lcm // ai

print(b_sum%mod)

Solution (Python):
from collections import Counter
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
prime = [0] * (10**6+5)
for i in range(N):
    c = Counter(prime_factorize(A[i]))
    for j in c.items():
        prime[j[0]] = max(j[1],prime[j[0]])
lcm = 1
for i in range(10**6+2):
    if prime[i] > 0:
        lcm *= pow(i,prime[i])
        lcm %= MOD

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

Solution (Python):
from collections import Counter
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
def prime_factorize(n):
    N = n
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= N:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
prime = [0] * (10**6+5)
for i in range(N):
    c = Counter(prime_factorize(A[i]))
    for j in c.items():
        prime[j[0]] = max(j[1],prime[j[0]])
lcm = 1
for i in range(10**6+2):
    if prime[i] > 0:
        lcm *= pow(i,prime[i])
        lcm %= MOD

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

Solution (Python):
from functools import reduce

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

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

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

LCM = reduce(lcm,A)%mod

print(sum([LCM*pow(A[i],-1,mod)%mod for i in range(N)])%mod)

Solution (Python):
import sys
sys.setrecursionlimit(4100000)
import math




N = int(input())


import fractions
a = list(map(int, input().split()))
koubai = a[0]
small = []
for i in range(0, N//2):
    small.append(a[2*i + 1] * a[2*i] // fractions.gcd(a[2*i + 1], a[2*i]))

small.append(a[-1])
for i in range(len(small)):
    koubai = koubai * small[i] // fractions.gcd(koubai, small[i])


ans = int(0)
for i in range(N):
    ans += koubai // a[i]
    
ans %= 1000000007

print(ans)

Solution (Python):
from copy import copy
def prime_table(n):
  n+=1
  table=[i if i%2 else 2 for i in range(n)]
  for i in range(3,n,2):
    if table[i]==i:
      for j in range(i*i,n,2*i):
        if table[j]==j:
          table[j]=i
  return table


def prime_fact(n,table):
  p=[]
  while n!=1:
    pp=table[n]
    p.append(pp)
    n//=pp
  r={}
  for i in p:
    if i in r:
      r[i]+=1
    else:
      r[i]=1
  return r



n=int(input())
t=prime_table(10**6)
a=list(map(lambda x:prime_fact(int(x),t),input().split()))

mx=copy(a[0])
for i in a[1:]:
  for j in i:
    if j in mx:
      mx[j]=max(mx[j],i[j])
    else:
      mx[j]=i[j]


sm=0
mod=10**9+7
for i in a:
  r=1
  for j in i:
    r=(r*pow(j,i[j],mod))%mod
  sm=(sm+pow(r,mod-2,mod))%mod

  
p=1
for i in mx:
  p=(p*pow(i,mx[i],mod))%mod

print((sm*p)%mod)

Solution (Python):

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

mod = 10**9+7

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

l = a[0]
for i in range(n):
    l = lcm(l, a[i])
l %= mod 

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

print(ans%mod)

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
memo = []
for i in range(N):
    tmp = []
    a = A[i]
    d = 2
    while d*d <= a:
        while a%d == 0:
            tmp.append(d)
            a //= d
        d += 1
    if a!=1:
        tmp.append(a)
    memo.append(Counter(tmp))

lcm = Counter([])

for count in memo:
    for k,v in count.items():
        if k not in lcm:
            lcm[k] = v
        else:
            lcm[k] = max(lcm[k],v)
mod = 10**9 +7
LCM = 1
for k,v in lcm.items():
    LCM = LCM*pow(k,v)%mod

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

Solution (Python):
import math
n = int(input())
a = list(map(int, input().split()))
s = a[0]
for i in a[1:]:
    s = (s*i)//math.gcd(s,i)
num = 0
for h in a:
    num += (s//h)
print(num%((10**9)+7))

Solution (Python):
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
"""
from math import gcd
def lcm(a,b):
    return a*b//gcd(a,b)
def main():
    mod = 10**9 +7
    N = int(input())
    A = list(map(int,input().split()))
    l = A[0]
    for i in range(1,N):
        l = lcm(l,A[i])

    ans = 0
    for a in A:
        ans += l//a
    print(ans%mod)
main()

Solution (Python):
from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

    print(ans % mod)
main()

Solution (Python):
import sys
from collections import Counter
from functools import reduce
from operator import mul, ior

from typing import Callable, ClassVar, Sequence, Type, TypeVar


T = TypeVar('T', bound='ModIntBase')


class ModIntBase:
    value: int
    mod: ClassVar[int]
    fac: ClassVar[Sequence[int]] = ()
    inv: ClassVar[Sequence[int]] = ()
    finv: ClassVar[Sequence[int]] = ()

    def __init__(self, value: int) -> None:
        self.value = value % self.mod

    def __hash__(self) -> int:
        return hash((self.value, self.mod))

    def __eq__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value == other.value
        else:
            return NotImplemented

    def __ne__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value != other.value
        else:
            return NotImplemented

    
    def __add__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value + other.value) % self.mod)
        else:
            return NotImplemented

    def __sub__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value - other.value) % self.mod)
        else:
            return NotImplemented

    def __mul__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__(self.value * other.value % self.mod)
        else:
            return NotImplemented

    def __truediv__(self, other):
        if isinstance(other, self.__class__):
            a = other.value
            b = self.mod
            u = 1
            v = 0
            while b:
                t = a // b
                a, b = b, a - t * b
                u, v = v, u - t * v
            return self.__class__(self.value * u % self.mod)
        else:
            return NotImplemented

    def __pow__(self, other):
        if isinstance(other, self.__class__):
            v = 1
            a = self.value
            b = other.value
            mod = self.mod
            while b > 0:
                if b & 1:
                    v = v * a % mod
                a = a * a % mod
                b >>= 1
            return self.__class__(v)
        else:
            return NotImplemented

    @classmethod
    def comb(cls, n: int, k: int):
        if n < k:
            return cls(0)
        if n < 0 or k < 0:
            return cls(0)

        if n < len(cls.fac):
            return cls(cls.fac[n] * (cls.finv[k] * cls.finv[n - k] % cls.mod) % cls.mod)
        else:
            k = min(k, n - k)
            a = reduce(mul, map(cls, range(n - k + 1, n + 1)), cls(1))
            b = reduce(mul, map(cls, range(1, k + 1)), cls(1))
            return a / b

    def __repr__(self) -> str:
        return f'{self.__class__.__name__}({self.value!r})'

    def __str__(self) -> str:
        return str(self.value)


class ModInt(ModIntBase):
    mod = 1000000007  


def prime_factor(a, temp):
    while a > 1:
        yield temp[a]
        a //= temp[a]


def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    max_a = max(A)
    temp = [0] * (max_a + 1)
    temp[1] = 1

    for i in range(2, max_a + 1):
        if temp[i]:
            continue

        for j in range(i, max_a + 1, i):
            temp[j] = i
    
    ap_list = (Counter(prime_factor(a, temp)) for a in A)
    lcm = reduce(ior, ap_list, Counter())
    lcm_i = ModInt(1)
    for v in lcm.elements():
        lcm_i *= ModInt(v)


    ans = ModInt(0)
    for a in A:
        ans += lcm_i / ModInt(a)

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import Counter
from functools import reduce
from operator import mul, ior

from typing import Callable, ClassVar, Sequence, Type, TypeVar


T = TypeVar('T', bound='ModIntBase')


class ModIntBase:
    value: int
    mod: ClassVar[int]
    fac: ClassVar[Sequence[int]] = ()
    inv: ClassVar[Sequence[int]] = ()
    finv: ClassVar[Sequence[int]] = ()

    def __init__(self, value: int) -> None:
        self.value = value % self.mod

    def __hash__(self) -> int:
        return hash((self.value, self.mod))

    def __eq__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value == other.value
        else:
            return NotImplemented

    def __ne__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value != other.value
        else:
            return NotImplemented

    
    def __add__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value + other.value) % self.mod)
        else:
            return NotImplemented

    def __sub__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value - other.value) % self.mod)
        else:
            return NotImplemented

    def __mul__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__(self.value * other.value % self.mod)
        else:
            return NotImplemented

    def __truediv__(self, other):
        if isinstance(other, self.__class__):
            a = other.value
            b = self.mod
            u = 1
            v = 0
            while b:
                t = a // b
                a, b = b, a - t * b
                u, v = v, u - t * v
            return self.__class__(self.value * u % self.mod)
        else:
            return NotImplemented

    def __pow__(self, other):
        if isinstance(other, self.__class__):
            v = 1
            a = self.value
            b = other.value
            mod = self.mod
            while b > 0:
                if b & 1:
                    v = v * a % mod
                a = a * a % mod
                b >>= 1
            return self.__class__(v)
        else:
            return NotImplemented

    @classmethod
    def comb(cls, n: int, k: int):
        if n < k:
            return cls(0)
        if n < 0 or k < 0:
            return cls(0)

        if n < len(cls.fac):
            return cls(cls.fac[n] * (cls.finv[k] * cls.finv[n - k] % cls.mod) % cls.mod)
        else:
            k = min(k, n - k)
            a = reduce(mul, map(cls, range(n - k + 1, n + 1)), cls(1))
            b = reduce(mul, map(cls, range(1, k + 1)), cls(1))
            return a / b

    def __repr__(self) -> str:
        return f'{self.__class__.__name__}({self.value!r})'

    def __str__(self) -> str:
        return str(self.value)


class ModInt(ModIntBase):
    mod = 1000000007  


def prime_factor(a, temp):
    while a > 1:
        yield temp[a]
        a //= temp[a]


def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    max_a = max(A)
    temp = [0] * (max_a + 1)
    temp[1] = 1

    for i in range(2, max_a + 1):
        if temp[i]:
            continue

        for j in range(i, max_a + 1, i):
            temp[j] = i
    
    ap_list = (Counter(prime_factor(a, temp)) for a in A)
    lcm = reduce(ior, ap_list, Counter())
    lcm_i = ModInt(1)
    for v in lcm.elements():
        lcm_i *= ModInt(v)


    ans = ModInt(0)
    for a in A:
        ans += lcm_i / ModInt(a)

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

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

def gcd(p,q):
    if q == 0:
        return p
    else:
        return gcd(q,min(p%q,q-p%q))

if N != 1:
    lcm = 1
    for i in range(N-1):
        if i == 0:
            lcm = A[0]*A[1]//gcd(A[0],A[1])
        else:
            lcm = lcm*A[i+1]//gcd(lcm,A[i+1])

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

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

else:
    print(1)

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline
m=10**9+7
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    i=2
    if temp%i==0:
        cnt=0
        while temp%i==0:
            cnt+=1
            temp //= i
        arr.append([i, cnt])
            
    for i in range(3, int(-(-n**0.5//1))+1,2):
        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

N=int(input())
A=list(map(int,input().split()))
d = collections.defaultdict(int)
for a in A:
    arr = factorization(a)
    for ar in arr:
        if d[ar[0]]<ar[1]:
            d[ar[0]]=ar[1]

lcm = 1
for key,val in d.items():
    lcm = lcm*pow(key,val)

ans = 0
for a in A:
    ans = ans+lcm//a
print(ans%m)

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline
m=10**9+7
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    i=2
    if temp%i==0:
        cnt=0
        while temp%i==0:
            cnt+=1
            temp //= i
        arr.append([i, cnt])
            
    for i in range(3, int(-(-n**0.5//1))+1,2):
        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

N=int(input())
A=list(map(int,input().split()))
d = collections.defaultdict(int)
for a in A:
    arr = factorization(a)
    for ar in arr:
        if d[ar[0]]<ar[1]:
            d[ar[0]]=ar[1]

gcd = 1
for key,val in d.items():
    gcd = gcd*pow(key,val)

ans = 0
for a in A:
    ans = ans+gcd//a
print(ans%m)