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

from collections import defaultdict

def prime_factors(d,N): 
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            c = 0
            while tmp%i == 0:
                tmp //= i
                c += 1
            if d[i] < c:
                d[i] = c
    if tmp != 1:
        if d[tmp] == 0:
            d[tmp] = 1

Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    d = defaultdict( int)
    for a in A:
        prime_factors(d, a)
    s = 1

    for key, value in d.items():
        s *= pow( key, value)
    ans = 0
    for a in A:
        ans += s*pow(a,Q-2,Q)
    print(ans%Q)
if __name__ == '__main__':
    main()

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

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

import fractions, functools
 
def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)
 
lcm = lcm_list(A)
 
answer = 0
for i in range(N):
    answer += lcm//A[i]
 
print(answer % (10**9 + 7))

Solution (Python):

from fractions import gcd

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

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

mod = 10**9+7

ans = 0
for i in A:
    ans += value // i

print(ans%mod)

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


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


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

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

ans = 0

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

print(ans%1000000007)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
import fractions
from functools import reduce

n=int(input())
c = list(map(int, input().split()))
mod=pow(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)

v=lcm(*c)%mod
ans=0

for i in range(n):
    ans += v * pow(c[i],mod-2,mod)
    ans%=mod

print(ans%mod)

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()))
a=lcm_list(l)
ans_l = []
for i in l:
    ans_l.append(a//i)
print(int(sum(ans_l)%(10**9+7)))

Solution (Python):
import sys
from collections import defaultdict

read = sys.stdin.read



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 - 1) // (2 * i) + 1)
    return sieve



def prime_factorize(n):
    a = defaultdict(int)
    while n != 1:
        b = table[n]
        a[b] += 1
        n //= b
    return a


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

table = min_factor(10 ** 6)
dic = defaultdict(int)

for i in A:
    for key, value in prime_factorize(i).items():
        dic[key] = max(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
from collections import Counter, defaultdict

read = sys.stdin.read



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 - 1) // (2 * i) + 1)
    return sieve



def prime_factorize(n):
    a = [1]
    while n != 1:
        b = table[n]
        a.append(b)
        n //= b
    return a


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

table = min_factor(10 ** 6)
dic = defaultdict(int)

for i in A:
    for key, value in Counter(prime_factorize(i)).items():
        dic[key] = max(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):
P=1000000007
def power(x,p):
  if(p==0):
    return 1;
  if(p%2):
    return power(x,p-1)*x%P;
  a=power(x,p//2);
  return a*a%P;
def inv(x):
  return power(x,P-2);
N=int(input());A=list(map(int,input().split()));

L=[0 for i in range(max(A)+1)]
for a in A:
  t=a;i=2;
  while(i**2<=a):
    c=0;
    while(t%i==0):
      t//=i;c+=1;
    L[i]=max(L[i],c)
    i+=1;
  if(t!=1):
    L[t]=max(L[t],1)
    
l=1;
for i in range(2,len(L)):
  l=l*power(i,L[i])%P;
b=0;
for a in A:
  b=(b+inv(a))%P
print(l*b%P)

Solution (Python):


pn_list = [2,3]

def next_pn(pn):
    npn = pn + 2
    pn_flg = 0
    while pn_flg == 0:
        for i in pn_list:
            if npn % i == 0:
                break
            if (i ** 2) > npn:
                pn_flg = 1
                break
        if pn_flg == 1:
            break 
        else:
            npn += 2
    pn_list.append(npn)
    return npn


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


sqr_max_a = int((1.0 * 10**6) ** 0.5) + 1

pn = 3
while pn < sqr_max_a:
    pn = next_pn(pn)


lcm = int(1)
for i in pn_list:
    wareta = 1
    while wareta == 1:
        wareta = 0
        for j in range(n):
            if a[j] % i == 0:
                a[j] = a[j] // i
                wareta = 1
        if wareta == 1:
            lcm = lcm * i
pn_lcm = []
for i in a:
    if i > 1:
        if i not in pn_lcm:
            pn_lcm.append(i)
            lcm = lcm * i

min_bsum = int(0)
for i in aa:
    min_bsum = min_bsum + lcm // i

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

Solution (Python):


n=int(input())
a=[int(x) for x in input().split()]
mod=10**9+7
lcm=1
from fractions import gcd
for ai in a:
    lcm=ai*lcm//gcd(ai,lcm)
ans=0
for ai in a:
    ans+=lcm//ai
print(ans%mod)

Solution (Python):

import sys
from collections import Counter
import math
MOD = 1000000007  


def factorial(n):
    prime_count = Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def div(a, b):
    return (a * power(b, MOD-2)) % MOD


def solve(N: int, A: "List[int]"):

    lcm = Counter()
    for a in A:
        c = factorial(a)
        for k in c:
            lcm[k] = max(c[k], lcm[k])
    

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

    tot = 0
    for a in A:
        tot += div(LCM, a)
    print(tot % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)


if __name__ == '__main__':
    main()

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

mod = 10**9+7

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

lcm = 1
for a in lst_a:
    lcm = a*lcm//fractions.gcd(a,lcm)
lcm %= mod
ans = 0
for a in lst_a:
	ans += lcm*pow(a,mod-2,mod)
	ans %= mod

print(ans)

Solution (Python):
import fractions 

import functools

MOD = 10**9+7


def main():
    
    
    N, *A = map(int, open(0).read().split())
            
    x = 1
    for a in A:
        x *= a //  fractions.gcd(x, a)
        
    b = sum(x//a for a in A)
    print(b%MOD)
    
if __name__== "__main__":
    main()

Solution (Python):
from fractions import gcd

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

g=A[0]
l=A[0]
for i in range(N):
    g=gcd(l,A[i])
    l=l*A[i]//g
    
ans=0
mod=10**9+7

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

Solution (Python):
import math

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

for a in A:
    
    D = dict()
    ra = math.floor(math.sqrt(a))
    if ra>1:
        for i in range(2,ra+1):
            while a%i == 0:
                D[i] = D.get(i,0) + 1
                a //= i
            if a == 1:
                break
        
    if a > 1:
        D[a] = D.get(a,0) + 1

    for d in D:
        Ld[d] = max(Ld.get(d,0), D[d])

lcm = 1
for l in Ld:
    lcm *= pow(l,Ld[l],Mod)
    lcm %= Mod

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

print(ans)

Solution (Python):
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
import math
import fractions
from heapq import heappush, heappop



readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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




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



def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True



def divisor(n):
    ass = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    return ass  



def prime_factor(n):
    ass = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass



def fctr1(n):
    f = []
    c = 0
    r = int(n**0.5)
    for i in range(2, r+2):
        while n % i == 0:
            c += 1
            n = n//i
        if c != 0:
            f.append([i, c])
            c = 0
    if n != 1:
        f.append([n, 1])
    return f



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 segment_sieve(a, b):
    ass = []
    is_prime_small = [True] * (int(b**0.5)+1)
    is_prime = [True] * (b-a)
    for i in range(2, int(b**0.5)):
        if is_prime_small[i]:
            j = 2*i
            while j**2 < b:
                is_prime_small[j] = False
                j += i
            j = max(2*i, ((a+i-1)//i)*i)
            while j < b:
                is_prime[j-a] = False
                j += i
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(a+i)
    if ass[0] == 1:
        del ass[0]
    return ass



def lcm_fctr(n, l):
    a = fctr1(n)
    for p, i in a:
        l[p] = max(i, l[p])
    return l


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

l = defaultdict(int)
for a in A:
    lcm_fctr(a, l)

e = 1
for i in l.keys():
    e = (e * pow(i, l[i], MOD)) % MOD

ans = 0
for a in A:
    m = modinv(a, MOD)
    ans += (e * m) % MOD
    ans %= MOD

print(ans)

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)

n=int(input())
a=[int(i) for i in input().split()]
tmp=1
for i in a:
	tmp=lcm(i,tmp)
mod=1000000007
print(sum(tmp//i for i in a)%mod)

Solution (Python):
import fractions
import functools
import sys

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

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

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

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

lcm_A = lcm_list(A)

B = [None]*N
B = [lcm_A//a for a in A]
print(sum(B)%(10**9+7))

Solution (Python):
import fractions
import functools
import sys

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

def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)
"""
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
"""
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

lcm_A = functools.reduce(lcm_base, A, 1)
B = [None]*N
B = [lcm_A//a for a in A]


print(sum(B)%(10**9+7))

Solution (Python):
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
n=int(input())
mod=1000000007
s=[int(i) for i in input().split()]
ans=1
for i in s:
    ans*=i//gcd(ans,i)
print(sum(ans//i for i in s)%mod)

Solution (Python):
from fractions import gcd

P = 10**9 + 7
n = int(input())

def lcm(p,q):
    return p*q//gcd(p,q)

a = list(map(int, input().split()))
x = a[0]
for i in range(1,n):
    x = lcm(x,a[i])
ans = 0
for i in range(n):
    ans += x//a[i]
    if i%10==0:
        ans = ans%P
print(ans%P)

Solution (Python):
from fractions import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
k=reduce(lambda x,y:x*y//gcd(x,y),a)
ans=sum(list(map(lambda x:k//x,a)))
print(ans%(10**9+7))

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

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

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

lcm_a = 1

for i in A:
    lcm_a = lcm(lcm_a,i)

ans = 0
for i in A:
    ans +=lcm_a//i 
    
print(ans%int(1e9+7))

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

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

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

lcm_a = 1

for i in A:
    lcm_a = lcm(lcm_a,i)

ans = 0
for i in A:
    ans +=lcm_a//i 
    
mod = int(1e9+7)
print(ans%mod)

Solution (Python):
from fractions import gcd

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

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

lcm_a = 1

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

ans = 0
for i in range(N):
    ans +=lcm_a//A[i] 
    
mod = int(1e9+7)
print(ans%mod)

Solution (Python):
def main():
    import fractions
    n = int(input())
    array = list(map(int, input().split()))
    lcm = array[0]
    for i in range(1, n):
        lcm = lcm * array[i] // fractions.gcd(lcm, array[i])

    total = 0
    for i,num in enumerate(array):
        total += lcm // num
    print(int(total%(10**9+7)))

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
aa = inpl()
g = 1
for a in aa:
    g = a*g//fractions.gcd(a,g)
g %= mod
res = 0
for a in aa:
    res += g*pow(a,mod-2,mod)
    res %= mod
print(res)

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

from collections import defaultdict

MOD = 10**9 + 7

primes = defaultdict(int)

for a in A:
    p = 2
    while p * p <= a:
        if a % p == 0:
            cnt = 0
            while a % p == 0:
                cnt += 1
                a //= p
            primes[p] = max(primes[p], cnt)
        p += 1
    if a != 1:
        if a not in primes:
            primes[a] = 1

lcm = 1
for p in primes:
    lcm = lcm * pow(p, primes[p], MOD) % MOD

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

print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
aa = inpl()
g = 1
for a in aa:
    g = a*g//fractions.gcd(a,g)
g %= mod
res = 0
for a in aa:
    res += g*pow(a,mod-2,mod)
    res %= mod
print(res)

Solution (Python):
import collections

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

mod = 10**9+7

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

primes = sieve(10**3)

def primeFactorization(n):
    ans = []
    temp = n
    for p in primes:
        while temp%p == 0:
            ans.append(p)
            temp //= p
    if temp > 1:
        ans.append(temp)
    return collections.Counter(ans)

AFactorized = list(map(primeFactorization, A))

lcm = collections.Counter()
for a in AFactorized:
    for p, n in a.items():
        lcm[p] = max(lcm[p], n)

lcm_val = 1
for p, n in lcm.items():
    lcm_val *= pow(p, n, mod)

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

print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  

def solve(N: int, A: "List[int]"):
    def factorize(n):
        ret = {}
        d = 2
        mx = int(n ** 0.5) + 1
        while d < mx:
            if n % d == 0:
                ret[d] = 0
            while n % d == 0:
                ret[d] += 1
                n //= d
            d += 1
        if n > 1:
            if n not in ret:
                ret[n] = 1
            else:
                ret[n] += 1
        return ret
    divs = {}
    cur = 1
    ret = 0
    for val in A:
        facs = factorize(val)
        tmp = 1
        for k, cnt in facs.items():
            if not k in divs:
                divs[k] = 0
            if divs[k] < cnt:
                tmp *= k ** (cnt - divs[k])
                divs[k] = cnt
        cur *= tmp
        ret *= tmp
        ret += cur // val
        ret %= MOD
        
        
        
        
    print(ret)
    return ret

def solve_(N: int, A: "List[int]"):
    def gcd(a, b):
        return a if b == 0 else gcd(b, a % b)
    g = A[0]
    for v in A:
        tmp = gcd(g, v)
        g = g * v // tmp
    ret = 0
    for v in A:
        ret += g // v
        ret %= MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, A)

if __name__ == '__main__':
    main()

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

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

def dp():
    n=int(input())
    l=list(map(int,input().split()))
    lcm=l[0]
    for i in range(n):
        lcm=Lcm(lcm,l[i])
    ans=0
    mod=1000000007
    for i in range(n):
        ans+=lcm//l[i]
    print(ans%mod)

if __name__ == "__main__":
    dp()

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

N = int(input())
A = list(map(int, input().split()))
g = 1
MOD = 10**9+7
ans = 0

for i in A:
    tmp = g*i//fractions.gcd(g, i) 
    ans *= tmp//g
    g = tmp
    ans += g//i

print(ans%MOD)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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)

n = I()
a = LI()
l = 1
for i in range(n):
    l = lcm(l,a[i])

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

Solution (Python):
from fractions import *
n,*a=map(int,open(0).read().split())
b=1
for i in a:b*=i//gcd(b,i)
print(sum(b//i for i in a)%(10**9+7))

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

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

N = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // gcd(ans, a[i])

B = []
for i in range(N):
    B.append(ans//a[i])

print(sum(B) % (10**9 + 7))

Solution (Python):
from fractions import gcd


n = int(input())
A = list(map(int,input().split()))
num = 1
ans = 0
for i in A:
  num = i // gcd(i,num) * num

for i in A:
  ans += num//i
  
print(int(ans%1000000007))

Solution (Python):
import sys
import fractions
sys.setrecursionlimit(100000)
def lcm(x,y):
    return x//fractions.gcd(x,y)*y

n = int(input())
a = list(map(int,input().split()))
LCM=a[0]
for i in a:
  LCM = lcm(LCM,i)
ans=0
for i in a:
  ans += LCM//i
  
print(int(ans)%1000000007)

Solution (Python):
def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)
def lcm(a, b):
    return a // gcd(a, b) * b

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

l = 1
for i in a:
    l = lcm(l, i)

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

print(ans % 1000000007)

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


class FLT:
    def __init__(self, mod=10**9+7):
        self.mod = mod

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

    def inv(self, a):
        """ 逆元を取る """
        return self.rep_sqr(a, self.mod-2)

def main():
    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)
    flt = FLT(MOD)

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

main()

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


class FLT:
    def __init__(self, mod=10**9+7):
        self.mod = mod

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

    def inv(self, a):
        """ 逆元を取る """
        return self.rep_sqr(a, self.mod-2)

def main():
    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)
    flt = FLT(MOD)

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

main()

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


class FLT:
    def __init__(self, mod=10**9+7):
        self.mod = mod

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

    def inv(self, a):
        """ 逆元を取る """
        return self.rep_sqr(a, self.mod-2)

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)
flt = FLT(MOD)

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