Problem:


Score : 500 points

Problem Statement

Given are N positive integers A_1,...,A_N.

Consider positive integers B_1, ..., B_N that satisfy the following condition.

Condition: For any i, j such that 1 \leq i < j \leq N, A_i B_i = A_j B_j holds.

Find the minimum possible value of B_1 + ... + B_N for such B_1,...,B_N.

Since the answer can be enormous, print the sum modulo (10^9 +7).

Constraints

1 \leq N \leq 10^4

1 \leq A_i \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the minimum possible value of B_1 + ... + B_N for B_1,...,B_N that satisfy the condition, modulo (10^9 +7).

Sample Input 1

3
2 3 4

Sample Output 1

13

Let B_1=6, B_2=4, and B_3=3, and the condition will be satisfied.

Sample Input 2

5
12 12 12 12 12

Sample Output 2

5

We can let all B_i be 1.

Sample Input 3

3
1000000 999999 999998

Sample Output 3

996989508

Print the sum modulo (10^9+7).



Sample input:
3
2 3 4


Sample output:
13

Submission status: Accepted

Solution code:
MOD=10**9+7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
N=int(input())
A=list(map(int,input().split()))
ans=ModInt(0)
Divisor=dict([(i,0) for i in range(1000000)])
def frac(n,div):
    ret = 0
    while not (n % div) :
        n //= div
        ret += 1
    return ret,n
for i in A:
    divided=i
    for j in range(2,int(divided**(0.5)+2)):
        chk,divided = frac(divided,j)
        if chk > Divisor[j]:Divisor[j] = chk
    Divisor[divided] = max(1,Divisor[divided])
LCM=ModInt(1)
for i in range(2,1000000):
    LCM*=i**ModInt(Divisor[i])
for i in A:
    ans+=LCM/ModInt(i)
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
from math import *
input = sys.stdin.readline

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

    prime_factors = defaultdict(int)
    
    #各素因数の最大値を保持
    for i in range(n):
        pf = factorization(As[i])
        for j in pf:
            prime_factors[j] = max(pf[j], prime_factors[j])
    
    lcm = 1
    for key in prime_factors:
        lcm *= pow(key, prime_factors[key])    
    
    ans = 0
    ans = sum([lcm // As[i] for i in range(n)]) % mod

    print(ans)
    return

#参考: https://qiita.com/ophhdn/items/e6451ec5983939ecbc5b
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

def factorization(n):
    dic = defaultdict(int)
    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
            dic[i] = cnt
            
    if temp!=1:
        dic[temp] = 1
    if not dic:
        dic[n] = 1

    return dic

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
L = list(map(int,input().split()))
m = 10**9+7
ans = 0
def gcd(x,y):
  while y != 0:
    cur = x
    x = y
    y = cur%y
  return x
if n != 1:
  lcm = L[0]*L[1]//gcd(L[0],L[1])
  for i in range(2,n):
    p = gcd(L[i],lcm)
    lcm = L[i]*lcm//p
  for i in range(n):
    k = (lcm%m)*pow(L[i],10**9+5,m)
    ans = (ans+k)%m
else:
  ans = 1
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    import fractions
    n=int(input())
    a=[int(i) for i in input().split()]
    g=1
    dx=fractions.gcd
    for i in a:
        g*=i//dx(g,i)
    suml=0
    mod=10**9+7
    for i in a:
        suml+=g*pow(i,mod-2,mod)
        suml%=mod
    print(suml)
resolve()

Submission status: Accepted

Solution code:
import fractions
n=int(input())
a=[int(i) for i in input().split()]
g=1
dx=fractions.gcd
for i in a:
  g*=i//dx(g,i)
suml=0
mod=10**9+7
for i in a:
  suml+=g*pow(i,mod-2,mod)
  suml%=mod
print(suml)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

MOD = 10**9+7
def pow(a, b):
    res = 1
    while b:
        if b & 1: res = res * a % MOD
        a = a**2 % MOD
        b >>= 1
    return res

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = set(A)
    
    m = max(B)+1    
    prime = {i:i for i in range(m)}
    is_prime = [False] * m
    
    for i in range(2, int(m**0.5)+1):
        if is_prime[i]: continue
        is_prime[i] = True
        
        for j in range(2*i, m, i):
            if not is_prime[j]: prime[j] = i
            is_prime[j] = True
            
    from collections import Counter
    
    count = Counter()
            
    for a in A:
        c = Counter()
        while a > 1:
            n = prime[a]
            c[n] += 1
            a //= n
        for k, v in c.items(): count[k] = max(count[k], v)
            
    x = 1
    for k, v in count.items(): x = x * k**v % MOD
    
    ans = 0
    for a in A: ans += x * pow(a, MOD-2) % MOD
    
    print(ans%MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from fractions import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = lr()
MOD = 10 ** 9 + 7
lcm = 1
for a in A:
    lcm *= a // gcd(lcm, a)

A = np.array(A)
B = lcm // A
answer = np.sum(B) % MOD
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
lcm = 1
for i in range(n):
  big,sml = lcm,a[i]
  while sml != 0:
    big,sml = sml,big%sml
  lcm *= a[i] // big
mod = 10 ** 9 + 7
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    x -= mod % x
    y %= mod
  return y
ans = 0
for i in range(n):
  ans += inv(a[i])
  ans %= mod
lcm %= mod
ans *= lcm
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

MOD = 10**9+7


def gcd(a, b):
    """
    return gcd of a,b
    ユークリッド
    """
    while b:
        a, b = b, a % b
    return a


def list_gcd(l):
    """
    l: list
    l のgcd を返す
    """
    return reduce(gcd, l)


def lcm(a, b):
    """
    a,bの最小公倍数
    """
    return a*b//gcd(a, b)


def list_lcm(l):
    """
    l:list
    lのlcmを返す
    """
    return reduce(lcm, l)


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

LCM = list_lcm(L)
print(sum([LCM//v for v in L]) % MOD)

Submission status: Accepted

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

b = [0]*N

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

Submission status: Accepted

Solution code:
#import math
#g = math.gcd
import fractions
g = fractions.gcd
n = int(input())
a = [int(_) for _ in input().split()]
mod = 10**9 + 7
lcm = 1
for x in a:
    lcm *= x // g(lcm, x)
ans = 0
for x in a:
    ans += lcm * pow(x, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Accepted

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

def make_inv(n, mod=10**9+7):
    inv = [0, 1] + [0] * (n-2)
    for i in range(2, n):
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
    return inv

def get_primes(lim):
    table = [True] * (lim+1)
    table[0:2] = False, False
    for i in range(2, int(lim**0.5)+1):
        if not table[i]: continue
        for j in range(i*2, lim+1, i):
            table[j] = False
    return [i for i in range(lim+1) if table[i]]

def factorize(x, primes):
    res = []
    for p in primes:
        if p ** 2 > x: break
        cnt = 0
        while not x % p:
            x //= p
            cnt += 1
        if cnt: res.append((p, cnt))
    if x > 1: res.append((x, 1))
    return res

inv = make_inv(10**6+1)
table = [0] * (10**6+1)
primes = get_primes(10**4)

for x in a:
    for i, num in factorize(x, primes):
        table[i] = max(table[i], num)

lcm = 1
for x, num in enumerate(table):
    if not num: continue 
    lcm *= pow(x, num, MOD)
    lcm %= MOD

ans = 0
for x in a:
    ans += lcm * inv[x]
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
# from random import randint

MOD = 10**9+7

N = int(input())
A = list(map(int, input().split()))
# N = 10000
# A = [randint(1, 10**6) for _ in range(N)]

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

# a = 12345678900000
# b = 100000
# a %= MOD
# print(a * modinv(b) % MOD)

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

a_lcm = A[0]
for a_i in A[1:]:
    a_lcm = lcm(a_lcm, a_i)
a_lcm %= MOD

sum_num = 0
for a_i in A:
    sum_num = (sum_num + (a_lcm * modinv(a_i))) % MOD

print(sum_num)

Submission status: Accepted

Solution code:
from sys import stdin
from fractions import gcd
from functools import reduce

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

lcm = reduce(lambda a, b: a * b // gcd(a, b), A)
print(sum(lcm // a for a in A) % 1000000007)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

lcm = reduce(lambda a, b: a * b // gcd(a, b), A)
print(sum(lcm // a for a in A) % 1000000007)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))

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

def calc_gcd_list(l):
    gcd = l[0]
    for i in range(1, N):
        gcd = gcd(gcd, l[i])
    return gcd

def calc_lcm_list(l):
    lcm = 1
    for i in l:
        lcm = lcm * i // gcd(lcm, i)
    return lcm


N = input_one_number()
lstA = input_multiple_number_as_list()
lcm = calc_lcm_list(lstA)
pow = 10**9 +7
print(sum(lcm//a for a in lstA)%pow)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    A = lmis()
    l = 1
    for a in A:
        l = lcm(l, a)
    print(sum(l//a for a in A) % N1097)


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    A = lmis()
    l = 1
    for a in A:
        l = lcm(l, a)
    print(sum(l//a for a in A) % N1097)


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter

MOD = 1000000007  # type: int

def sieve(n):
    is_prime = [True for _ in range(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:0 for i in range(1, n+1) if is_prime[i-1]}
    # return is_prime, table
    return table

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

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

    for i in range(N):
        decom = Counter(prime_decomposition(A[i]))

        for d,number in decom.items():
            if table.get(d) == None:
                table[d] = number
                continue

            if table[d] < number:
                table[d] = number
    LCM = 1
    for key,value in table.items():
        LCM *= pow(key,value,MOD)

    print(sum([LCM*pow(a,MOD-2,MOD) for a in A])%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))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter

MOD = 1000000007  # type: int

def sieve(n):
    is_prime = [True for _ in range(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:0 for i in range(1, n+1) if is_prime[i-1]}
    # return is_prime, table
    return table

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

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

    for i in range(N):
        decom = Counter(prime_decomposition(A[i]))

        for d,number in decom.items():
            if table.get(d) == None:
                table[d] = number
                continue

            if table[d] < number:
                table[d] = number
    LCM = 1
    for key,value in table.items():
        LCM *= key**value
        LCM %= MOD

    print(sum([LCM*pow(a,MOD-2,MOD) for a in A])%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))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import fractions
from functools import reduce
import random

MOD = 1000000007  # type: int

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

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

    LCM = reduce(lcm,A)
    answer = 0
    for i in range(N):
        answer += LCM//A[i]
    print(answer%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))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd


def main():
        
    N = int(input())
    A = list(map(int, input().split())) 
    MOD = 10**9 + 7


    l = 1

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


    ans = 0
    for a in A:
        ans += (l // a)
    ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

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

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

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

Submission status: Accepted

Solution code:
import fractions

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

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

def solve():
    memo = A[0]
    for i in range(1, N):
        memo = lcm(memo, A[i])

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

    return ans % (10 ** 9 + 7)

print(solve())

Submission status: Accepted

Solution code:
import fractions

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

mod = 10**9+7

R = 1 # 最小公倍数
# 最小公倍数を求める
for A in A_list:
    R *= A // fractions.gcd(R, A)

# Bの合計を求める
ans = 0
for A in A_list:
    ans = ans + R // A # 計算は小数として出してはダメだから//を使う

ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import math

mod=1000000007

count=[0 for i in range(1000005)]

def factorize(x):
	lim= int(math.sqrt(x))
	for i in range(2,lim+1):
		if x%i == 0:
			c=0
			while x%i==0:
				x/=i
				c+=1
			x=int(x)

			if count[i]<c: count[i]=c
	if x>1:	
		if count[x]<1: count[x]=1

def minus(ans,x):
	lim= int(math.sqrt(x))
	for i in range(2,lim+1):
		if x%i == 0:
			c=0
			while x%i==0:
				x/=i
				c+=1
			x=int(x)

			ans*= pow(pow(i,c),mod-2,mod)
			ans%=mod

	ans*= pow(pow(x,1),mod-2,mod)
	ans%=mod

	return int(ans)

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

ans=0
for x in l:
	factorize(x)

ans=1
for i in range(1,1000005):
	ans*= pow(i,count[i],mod)
	ans%=mod

lc=ans
res=0
for x in l:
	res+=minus(lc,x)
	res%=mod

print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def pow_mod(x, n, mod):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return K*x

#main関数
def main():
    """"ここに今までのコード"""

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

    plist = [0]*1000
    lcm = 1
    nokori=set()
    for a in A:
        for j in range(2, 1001):
            count_j=0
            while a % j == 0:
                count_j += 1
                a //= j
            plist[j-1]=max(plist[j-1],count_j)
        nokori |= {a}
    for x in nokori:
        lcm *= x
        lcm %= mod

    for i in range(1000):
        lcm *= pow_mod(i+1, plist[i], mod)
        lcm %= mod
    
    ans = 0

    for a in A:
        ans += lcm * pow_mod(a, mod-2, mod)
        ans %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

plist = [0]*1000
lcm = 1
nokori=set()
for a in A:
    for j in range(2, 1001):
        count_j=0
        while a % j == 0:
            count_j += 1
            a //= j
        plist[j-1]=max(plist[j-1],count_j)
    nokori |= {a}
for x in nokori:
    lcm *= x
    lcm %= mod


for i in range(1000):
    lcm *= pow(i+1, plist[i], mod)
    lcm %= mod

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


#main関数
def main():
    """"ここに今までのコード"""

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

    plist = [0]*1000
    lcm = 1
    nokori=set()
    for a in A:
        for j in range(2, 1001):
            count_j=0
            while a % j == 0:
                count_j += 1
                a //= j
            plist[j-1]=max(plist[j-1],count_j)
        nokori |= {a}
    for x in nokori:
        lcm *= x
        lcm %= mod

    #print(plist)
    #print(lcm)
    for i in range(1000):
        lcm *= pow(i+1, plist[i], mod)
        lcm %= mod
    
    #print(lcm)
    ans = 0

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from copy import deepcopy
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

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 prime_decomposition(n):
    table = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            table += [i]
            n //= i
        if n == 1:
            break
    if n != 1:
        table += [a]
    return table

pr = primes(10 ** 3 + 1)
n = I()
A = LI()
D = defaultdict(int)
for a in A:
    for p in pr:
        if a < p:
            break
        cnt = 0
        while a % p == 0:
            cnt += 1
            a //= p
        if cnt > D[p]:
            D[p] = cnt
    if a > 1 and D[a] == 0:
        D[a] = 1

lcm = 1
for v in D:
    lcm = lcm * pow(v, D[v], mod) % mod

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



print(ans)

Submission status: Accepted

Solution code:
from fractions import *

n,*a=map(int,open(0).read().split())
lcm = 1
for i in a:
    lcm *= i // gcd(lcm,i)
b = 0
mod = 10**9+7
for i in a:
    b = b + lcm // i
b %= mod
print(b)

Submission status: Accepted

Solution code:

from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in a:
    ans = ans * i // gcd(ans, i)
mod = 10**9+7
print(sum(map(lambda x: ans // x, a)) % mod)

Submission status: Accepted

Solution code:
# from math import gcd
from fractions import gcd

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in a:
    ans = ans * i // gcd(ans, i)
mod = 10**9+7
print(sum(map(lambda x: ans // x, a)) % mod)

Submission status: Accepted

Solution code:
import math
import fractions
MOD=1000000007
n=int(input())
a=list(map(int,input().split()))
x=1
ans=0
for i in a:
  x=x*i//fractions.gcd(x,i)
for i in a:
  ans=ans+x//i
print(ans%MOD,'\n')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from fractions import gcd
from functools import reduce


MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    common_multi = reduce(lambda x, y: x * y // gcd(x, y), A)
    print(sum(map(lambda x: common_multi // x, A)) % MOD)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

n  = int(input())
xs = [int(x) for x in input().split()]
y  = 1
r  = 0
m  = 10 ** 9 + 7

for x in xs:
  y = lcm(y, x)

for x in xs:
  r += y // x

print(r % m)

Submission status: Accepted

Solution code:
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(x, y):
    return (x * y) // gcd(x, y)

MOD = int(1e9 + 7)

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

LCM = 1

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc152/submissions/9693323

import sys
read = sys.stdin.read

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


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


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


table = min_factor(max(A))

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
#リストの最小公倍数
def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

def main():
    N = ir()
    A = lr()
    A.sort()
    if N == 1:
        print(1)
        exit()
    MOD = 10 ** 9 + 7
    l = []
    first = A[0]
    l = [x//gcd(x, first) for x in A[1:]]
    x = lcm(l) #B[0]
    answer = x%MOD

    for i in range(1, N):
        answer += first * x // A[i]

    print(answer%MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


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


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


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


# N個の最大公約数
def eucledean(A, N):
    # A = sorted(A)
    ans = A[0]
    for i in range(1, N):
        ans = gcd(A[i], ans)
    return ans


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


# N個最小公倍数
def lcm_n(A, N):
    # A = sorted(A)
    ans = A[0]
    # for i in range(1, N):
    #     ans = fractions.gcd(A[i], ans)
    for i in range(1, N):
        ans = lcm(ans, A[i])
    return ans


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


def main():
    N = I()
    A = LI()
    ans = 0

    a = lcm_n(A, N)
    a %= MOD
    for i in range(N):
        ans += a * modinv(A[i])
        ans %= MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


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


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


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


# N個の最大公約数
def eucledean(A, N):
    # A = sorted(A)
    ans = A[0]
    for i in range(1, N):
        ans = gcd(A[i], ans)
    return ans


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


# N個最小公倍数
def lcm_n(A, N):
    # A = sorted(A)
    ans = A[0]
    # for i in range(1, N):
    #     ans = fractions.gcd(A[i], ans)
    for i in range(1, N):
        ans = lcm(ans, A[i])
    return ans


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


def main():
    N = I()
    A = LI()
    ans = 0

    # N = 10 ** 4
    # A = [10**6] * N
    # for i in range(N):
    #     A[i] -= i
    # # A[0] = 10**6 - 1
    # # A[1] = 10**6 - 2
    a = lcm_n(A, N)
    a %= MOD
    for i in range(N):
        ans += a * modinv(A[i])
    print(ans % MOD)


if __name__ == '__main__':
    main()