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:
# 解説放送を見た

class Sieve:
    """区間[2,n]の値を素因数分解する"""

    def __init__(self, n=1):
        primes = []
        f = [0] * (n + 1)
        f[0] = f[1] = -1
        for i in range(2, n + 1):  # 素数を探す
            if f[i]: continue
            primes.append(i)
            f[i] = i  # 素数には自身を代入
            for j in range(i * i, n + 1, i):  # 合成数に素因数を書き込む
                if not f[j]:
                    f[j] = i  # 最小の素因数を代入
        self.primes = primes
        self.f = f

    def is_prime(self, x) -> bool:  # 素数判定
        return self.f[x] == x

    def factor_list(self, x) -> list:  # 素因数分解の昇順リスト, [2,2,3,5,...]
        res = []
        while x != 1:
            res.append(self.f[x])
            x //= self.f[x]
        return res

    def factor(self, x) -> list:  # 素因数分解の頻度リスト, [[2,x],[3,y],[5,z],...]
        fl = self.factor_list(x)
        if not fl: return []
        res = [[fl[0], 0]]
        for p in fl:
            if res[-1][0] == p:
                res[-1][1] += 1
            else:
                res.append([p, 1])
        return res


def main():
    from collections import defaultdict

    mod = 10 ** 9 + 7

    _ = int(input())  # n
    *a, = map(int, input().split())

    sieve = Sieve(n=10 ** 6 + 5)

    mp = defaultdict(int)
    for x in a:
        f = sieve.factor(x=x)  # [[prime,cnt],...]
        for prime, cnt in f:
            mp[prime] = max(mp[prime], cnt)

    lcm = 1
    for prime, cnt in mp.items():
        for _ in range(cnt):
            lcm = (lcm * prime) % mod

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd  # python<=3.4

MOD=1000000007

def ADD(x, y):
  return (x + y) % MOD

def SUB(x, y):
  return (x - y + MOD) % MOD

def MUL(x, y):
  return x * y % MOD

def POW(x, e):
  v = 1
  while e:
    if e & 1:
      v = MUL(v, x)
    x = MUL(x, x)
    e >>= 1
  return v

def INV(x):
  return POW(x, MOD-2)

def DIV(x, y):
  return MUL(x, INV(y))


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

el = 1
for ai in a:
  g = gcd(el,ai)
  el = el // g * ai

el %= MOD

sum = 0
for ai in a:
  sum += DIV(el, ai)

sum %= MOD
print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd;from functools import reduce;n,*a=map(int,open(0).read().split());l=reduce(lambda a,b:a*b//gcd(a,b),a);print(sum(l//i for i in a)%1000000007)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)


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


mod = int(1e9 + 7)
n = int(input())
a = [int(i) for i in input().split()]
kek = 1
for i in range(n):
    kek = (kek * a[i]) // gcd(kek, a[i])
s = 0
for i in range(n):
    s += kek // a[i]
print(int(s % mod))

Submission status: Accepted

Solution code:
import math

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

def gcd(x,y):
    return x if y == 0 else gcd(y,x%y)

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

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

ans = 0
for e in a:
    ans += now_lcm//e

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

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict

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

max_A = max(A)
f = list(range(max_A + 1))
for i in range(2, int(max_A ** 0.5) + 1):
    if f[i] == i:
        f[i::i] = [i] * (max_A // i)


def factors(x):
    factor = defaultdict(int)
    while x != 1:
        factor[f[x]] += 1
        x //= f[x]
    return factor


L = defaultdict(int)
for i in range(N):
    Ai = factors(A[i])
    for p, index in Ai.items():
        L[p] = max(L[p], index)
lcm = 1
for p, index in L.items():
    if index == 0:
        continue
    lcm *= pow(p, index, MOD)
    lcm %= MOD

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

Submission status: Accepted

Solution code:
import fractions
import sys
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())
alist=list(map(int,input().split()))

if N==1:
  print(1)
else:
  lcm_alist=lcm_list(alist)
  #print(lcm_alist)
  
  allsum=0
  for i in range(N):
    allsum+=lcm_alist//alist[i]
    
  #print(blist)
  print(allsum%(10**9+7))

Submission status: Accepted

Solution code:
from fractions import gcd

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

lm = A[0]
for a in A[1:]:
    lm = lm*a//gcd(lm,a)

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

print(ans)

Submission status: Accepted

Solution code:
def factoring(M,n=2):
    if M==1: return {}
    for i in range(n,int(M**0.5)+1):
        if M%i==0:
            ret = factoring(M//i,i)
            ret[i] = ret.get(i,0)+1
            return ret
    return {M:1}

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

mod = 10**9+7

fac = {}

for a in A:
    tmp = factoring(a)
    for b,n in tmp.items():
        fac[b] = max(fac.get(b,1),n)
lcm = 1
for b,n in fac.items():
    lcm *= pow(b,n,mod)
    lcm %= mod
        
ans = 0
for a in A:
    ans += (lcm*pow(a,mod-2,mod))%mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
##########################
#  
##########################
from functools import reduce
from fractions import gcd

MOD = 10**9+7

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

def main():
    N = int(input())
    a = [int(i) for i in input().split()]

    lcm = reduce(lcm_base, a, 1)
    lcm %= MOD
    
    b = sum(pow(i, MOD - 2, MOD) for i in a)
    b %= MOD
    ans = lcm * b

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

input = sys.stdin.readline
MOD = 10 ** 9 + 7


def inverse(n, mod=10 ** 9 + 7):
    return pow(n, mod - 2, mod)


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

    L = reduce(lambda o1, o2: o1 // gcd(o1, o2) * o2, A)
    sigma_A_inv = sum([inverse(a) for a in A])

    print(L * sigma_A_inv % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

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

print(sum(lcm//a for a in A)%MOD)

Submission status: Accepted

Solution code:
import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
res = 0
MOD = 10**9+7
for elem in a:
    tmp = g*elem//fractions.gcd(g,elem)
    res *= tmp//g
    g = tmp
    res += g//elem
print(res%MOD)

Submission status: Accepted

Solution code:
from functools import reduce
# python > pypy
MOD = 10**9 + 7
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def gcd_list(numbers):
    return reduce(gcd, numbers)

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

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

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

Submission status: Accepted

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

def inverse(a): #aに対し、a**(mod-2)、つまり逆元を返す
    T=[a]
    while 2**(len(T))<mod: #a**1,a**2.a**4,a**8,...を計算しておく
        T.append(T[-1]**2%mod)
    b=bin(mod-2) #mod-2を2進数表記にする
    ans=1
    for i in range(len(b)-2):
        if int(b[-i-1])==1:
            ans=ans*T[i]%mod
    return ans

def make_eratosthenes(n): #エラストテネスの篩(最大の素因数を格納した配列)
    A=[0]*n
    A[0],A[1]=-1,-1
    for i in range(2,n):
        if A[i]==0:
            j=i
            while j<n:
                A[j]=i
                j+=i
    return A

E=make_eratosthenes(10**6+5)

l={}
for a in A:
    now=a
    f=[] #素因数格納配列
    while now>1:
        f.append(E[now])
        now//=E[now]
    chk=0 
    for p in f:
        if chk==p: #同じ素因数が複数あるときに飛ばす
            continue
        chk=p
        if p in l.keys(): #辞書に素因数がある場合、個数の多いほう
            l[p]=max(l[p],f.count(p))
        else: #辞書にない場合新規追加
            l[p]=f.count(p)

lcm=1
for k in l:
    for i in range(l[k]):
        lcm=lcm*k%mod
s=0
for i in range(n):
    s+=lcm*inverse(A[i])%mod
    s%=mod
print(s)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
import collections
import math

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


def eratosthenes(n):  #エラトステネスの篩
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


def factorize(n, primes):        # 素数の値をカウントする
    if n < 2:
        return dict()
    counter = collections.Counter()
    for p in primes:
        while n % p == 0:
            counter[p] += 1
            n //= p
        if n == 1:
            break
    if n > 1:
        counter[n] += 1
    return counter


if n == 1:
    print(1)
    exit()

sieve = eratosthenes(10 ** 3)
primes = [x for x, b in enumerate(sieve) if b]

lcm = collections.Counter()
for x in a:
    counter = factorize(x, primes)
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)
lcm_val = 1
for p, k in lcm.items():  # 各素因数と個数
    lcm_val *= pow(p, k, MOD)
    #lcm_val %= MOD       # 最小公倍数


res = 0
for x in a:
    res += lcm_val * pow(x, MOD - 2, MOD)  # 最小公倍数lcm_val / 各値x の余り 逆元をとる
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
import fractions
#import numpy as np

mod=int(10**9+7)

def lcm(a,b):
    return

def ac(N,A):
    l=A[0]
    for a in range(1,N):
        l=(l*A[a])//fractions.gcd(l,A[a])
    l%=mod
    ans=0
    for a in A:
        ans+=l*pow(a,mod-2,mod)
        ans%=mod
    return ans

def solve():
    return

#main
N=int(input())
A=list(map(int,input().split()))
print(ac(N,A))

Submission status: Accepted

Solution code:
import functools

MOD = 10**9 + 7


def lcm(a, b) -> int:
    c, d = a, b
    while d != 0:
        c, d = d, c % d
    return a // c * b


def inv_mod(x):
    return pow(x, MOD - 2)


def pow(x: int, n: int) -> int:
    res = 1
    while n > 0:
        if n & 1 == 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1

    return res


def main():
    N = int(input())
    an = list(map(int, input().split()))

    lcm_an = functools.reduce(lcm, an)
    lcm_an %= MOD

    ans = 0
    for a in an:
        ans = (ans + lcm_an * inv_mod(a)) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

def list_lcm(*numbers):
    return reduce(lcm,numbers)

n=int(input())
a=list(map(int,input().split()))
l,ans,mod=list_lcm(*a),0,1000000007
print(sum(l//i for i in a)%mod)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

def list_lcm(*numbers):
    return reduce(lcm,numbers)

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

l=list_lcm(*a)
ans,mod=0,1000000007
for i in a:
    ans+=l//i

print(ans%mod)

Submission status: Accepted

Solution code:
import fractions as m
n=int(input())
a=input().split()
b=1
for i in a:
    i=int(i)
    b*=i//m.gcd(b,i)
    
print(sum(b//int(i) for i in a)%(10**9+7))

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y > 0:
        tmp = x % y
        x = y
        y = tmp
    return x

def lcm(x, y):
    if x == 0 or y == 0:
        return 0
    else:
        return x // gcd(x, y) * y

def main():
    mod = int(1e9 + 7)
    n = int(input())
    a = list(map(int, input().split()))
    l = 1
    for i in range(n):
        l = lcm(l, a[i])

    ans = 0

    print(int(sum(l // i for i in a) % mod))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
import functools

MOD = int(1e9) + 7


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


class Inv:

    @classmethod
    def pow(cls, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % MOD
            x = x * x % MOD
            n >>= 1
        return ret

    @classmethod
    def inv(cls, x: int) -> int:
        return cls.pow(x, MOD - 2)


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

v = functools.reduce(lcm, A)
v %= MOD
ans = 0
for a in A:
    ans = (ans + v * Inv.inv(a)) % MOD
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a,b):
    return a//gcd(a,b)*b

n=int(input())
a=[int(i) for i in input().split()]
L=a[0]
for i in a:
    L=lcm(L,i)
ans=0
for i in a:
    ans+=L//i
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
N=10**6+1
mod=10**9+7

inv_l=[0,1]
for i in range(2,N):
    inv_l+=[inv_l[mod%i]*(mod-int(mod/i))%mod]

prime_list=[]
min_prime=[1]*(N+1)
is_prime=[0,0]+[1]*(N-1)
for i in range(2,N+1):
    if is_prime[i]==1:
        prime_list.append(i)
        j=i
        while j<=N:
            is_prime[j]=0
            if min_prime[j]==1:
                min_prime[j]=i
            j+=i

def lcm(l,mod):
    max_count=[0]*(N+1)
    for a in l:
        a_min_prime=min_prime[a]
        a_count=0
        while a>1:
            if min_prime[a]==a_min_prime:
                a_count+=1
                a//=a_min_prime
            else:
                max_count[a_min_prime]=max(max_count[a_min_prime],a_count)
                a_min_prime=min_prime[a]
                a//=a_min_prime
                a_count=1
            if a==1:
                max_count[a_min_prime]=max(max_count[a_min_prime],a_count)
    ret=1
    for i in range(1,N+1):
        if max_count[i]!=0:
            ret=(ret*i**max_count[i])%mod
    return ret

n=int(input())
A=list(map(int,input().split()))
L=lcm(A,mod)
ans=0
for i in range(n):
    ans=(ans+L*inv_l[A[i]])%mod
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

def gcd(x, y):
    y, x = sorted([x, y])
    while True:
        r = x % y
        if r == 0:
            # print(x, y, r)
            return y
        else:
            # print(x, y, r)
            x, y = y, r

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

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

N = int(input())
l = list(map(int, input().split(" ")))

p = lcm_list(l)
c = 0
z = 10 ** 9 + 7
for i in l:
  c += p // i
print(c % z)

Submission status: Accepted

Solution code:
from fractions import gcd
import sys
input = sys.stdin.readline
def lcm(a,b):
    return a*b // gcd(a,b)

def main():
    N = int(input())
    A = list(map(int,input().split()))
    M = 10**9+7
    l = 1
    for a in A:
        l = lcm(l,a)
    ans = 0
    for a in A:
        ans += l//a
    print(ans%M)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd
    import sys
    input = sys.stdin.readline
    def lcm(a,b):
        return a*b // gcd(a,b)
    N = int(input())
    A = list(map(int,input().split()))
    M = 10**9+7
    l = 1
    for a in A:
        l = lcm(l,a)
    ans = 0
    for a in A:
        ans += l//a
    print(ans%M)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y > 0:
        tmp = x % y
        x = y
        y = tmp
    return x

def lcm(x, y):
    if x == 0 or y == 0:
        return 0
    else:
        return x // gcd(x, y) * y

def main():
    mod = int(1e9 + 7)
    n = int(input())
    a = list(map(int, input().split()))
    l = 1
    for i in range(n):
        l = lcm(l, a[i])

    ans = 0

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

    ans %= mod

    print(int(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
import functools

MOD = int(1e9) + 7


class Inv:

    @classmethod
    def pow(cls, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % MOD
            x = x * x % MOD
            n >>= 1
        return ret

    @classmethod
    def inv(cls, x: int) -> int:
        return cls.pow(x % MOD, MOD - 2)


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

MAX_A = 1000010

facts = [0] * MAX_A
p = [False] * MAX_A

def prime():

    for i in range(2, MAX_A):
        p[0] = p[1] = True
        if not p[i]:
            j = 2 * i
            while j < MAX_A:
                p[j] = True
                j += i

prime()

for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            ii = a // i
            c1 = 0
            while a % i == 0:
                c1 += 1
                a //= i
            c2 = 0
            while not p[ii] and a % ii == 0:
                c2 += 1
                a //= ii
            facts[i] = max(facts[i], c1)
            facts[ii] = max(facts[ii], c2)
        i += 1
    if not p[a]:
        facts[a] = max(facts[a], 1)

tar = 1
for idx, c in enumerate(facts):
    if c == 0:
        continue
    tar *= Inv.pow(idx, c)
    tar %= MOD

ans = 0
for a in A:
    ans += tar * Inv.inv(a) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import time, math
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

def f(a):
    M=10**9+7
    ans, z = 0, 1
    for x in a:
        z = (z * x) // gcd(z, x)
    #print(z)
    z %= M
    for x in a:
        ans += z * pow(x, M-2, M)
        ans %= M
    return ans

n = input()
a = list(map(int, input().split()))
#a = []
#for i in range(1000):
#    a.append(1000000-i)
print(f(a))

Submission status: Accepted

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

def gcd(a, b):
    while b:
        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()))
MOD = 10**9+7

L = 1

for Ai in A:
    L = lcm(L, Ai)

L %= MOD
ans = 0

for Ai in A:
    ans += L*pow(Ai, MOD-2, MOD)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def factorize(n):
    factors = []
    
    for i in range(2, int(n**0.5)+1):
        cnt = 0
        
        while n%i==0:
            n //= i
            cnt += 1
            
        if cnt>0:
            factors.append((i, cnt))
    
    if n!=1:
        factors.append((n, 1))
    
    return factors
    
def inv(x):
    return pow(x, MOD-2, MOD)
    
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7
M = defaultdict(int)

for Ai in A:
    factors = factorize(Ai)
    
    for v, c in factors:
        M[v] = max(M[v], c)
    
L = 1

for v, c in M.items():
    L *= pow(v, c, MOD)
    L %= MOD

ans = 0

for Ai in A:
    ans += L*inv(Ai)
    ans %= MOD

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


def factorize(n, primes):
    import collections
    if n < 2:
        return dict()
    counter = collections.Counter()
    for p in primes:
        while n % p == 0:
            counter[p] += 1
            n //= p
        if n == 1:
            break
    if n > 1:
        counter[n] += 1
    return counter


MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

sieve = eratosthenes(10**3)
primes = [x for x, b in enumerate(sieve) if b]

lcm_counter = collections.Counter()
for x in ls:
    counter = factorize(x, primes)
    for p, k in counter.items():
        lcm_counter[p] = max(lcm_counter[p], k)
lcm = 1
for p, k in lcm_counter.items():
    lcm *= pow(p, k, MOD)
    lcm %= MOD

res = 0
for x in ls:
    res += lcm * pow(x, MOD - 2, MOD)
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
 
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)
 
x = lcm_list(l)
ans = 0
for i in range(n):
  ans += x//l[i]
ans %= 10**9+7
  
print(ans)

Submission status: Accepted

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


def factorize(n, primes):
    import collections
    if n < 2:
        return dict()
    counter = collections.Counter()
    for p in primes:
        while n % p == 0:
            counter[p] += 1
            n //= p
        if n == 1:
            break
    if n > 1:
        counter[n] += 1
    return counter


MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

sieve = eratosthenes(10**3)
primes = [x for x, b in enumerate(sieve) if b]

lcm = collections.Counter()
for x in ls:
    counter = factorize(x, primes)
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)
lcm_val = 1
for p, k in lcm.items():
    lcm_val *= pow(p, k, MOD)
    lcm_val %= MOD

res = 0
for x in ls:
    res += lcm_val * pow(x, MOD - 2, MOD)
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def factorize_all(n):
    factorizations = [None] * (n + 1)
    factorizations[0] = dict()
    factorizations[1] = dict()
    for p in range(2, n + 1):
        if factorizations[p] is None:
            for k in range(1, n // p + 1):
                if factorizations[k] is None:
                    continue
                fs = factorizations[k].copy()
                if p in fs:
                    fs[p] += 1
                else:
                    fs[p] = 1
                factorizations[k * p] = fs
    return factorizations


MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

factorizations = factorize_all(max(ls))

lcm = collections.Counter()
for x in ls:
    counter = factorizations[x]
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)
lcm_val = 1
for p, k in lcm.items():
    lcm_val *= pow(p, k, MOD)
    lcm_val %= MOD

res = 0
for x in ls:
    res += lcm_val * pow(x, MOD - 2, MOD)
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def factorize_all(n):
    factorizations = [None] * (n + 1)
    factorizations[0] = dict()
    factorizations[1] = dict()
    for p in range(2, n + 1):
        if factorizations[p] is None:
            for k in range(1, n // p + 1):
                if factorizations[k] is None:
                    continue
                fs = factorizations[k].copy()
                if p in fs:
                    fs[p] += 1
                else:
                    fs[p] = 1
                factorizations[k * p] = fs
    return factorizations


MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

factorizations = factorize_all(max(ls))

lcm = collections.Counter()
for x in ls:
    counter = factorizations[x]
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)
lcm_val = 1
for p, k in lcm.items():
    lcm_val *= pow(p, k, MOD)
    lcm_val %= MOD

pinvs = {p: pow(p, MOD - 2, MOD) for p in lcm}
res = 0
for x in ls:
    counter = factorizations[x]
    s = 1
    for p, k in counter.items():
        s *= pow(pinvs[p], k, MOD)
    res += lcm_val * s % MOD
    res %= MOD
print(res)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
mod = 10**9 + 7
def gcd(a,b):
  while b: a,b = b,a%b
  return a
lcm = lambda a,b: a*b//gcd(a,b)
t = 1
for x in l: t = lcm(t,x)
print(sum(t//x for x in l)%mod)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
t = 1; mod = 10**9 + 7
def gcd(a,b):
  while b: a,b = b,a%b
  return a
lcm = lambda a,b: a*b//gcd(a,b)
for x in l: t = lcm(t,x)
print(sum(t//x for x in l)%mod)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

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

N = int(input())
l = list(map(int, input().split(" ")))

p = lcm_list(l)
c = 0
z = 10 ** 9 + 7
for i in l:
  c += p // i
print(c % z)

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

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]
    if i % 100 == 0:
        answer %= MOD

print(answer%MOD)

Submission status: Accepted

Solution code:
import fractions

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

for i in range(n):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i]) if i > 0 else a[i]
    ainv_sum += pow(a[i], m-2, m)
    ainv_sum %= m

print((ainv_sum * lcm) % m)

Submission status: Accepted

Solution code:
def mpow(x, n):
    result = 1
    while n != 0:
        if n & 1 == 1:
            result *= x
            result %= 1000000007
        x *= x
        x %= 1000000007
        n >>= 1
    return result


max_A = 1000000

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

sieve = [0] * (max_A + 1)
sieve[0] = -1
sieve[1] = -1
for i in range(2, max_A + 1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    for j in range(i * i, max_A + 1, i):
        if sieve[j] == 0:
            sieve[j] = i

lcm_factors = {}
for i in range(N):
    t = []
    a = A[i]
    while a != 1:
        if len(t) != 0 and t[-1][0] == sieve[a]:
            t[-1][1] += 1
        else:
            t.append([sieve[a], 1])
        a //= sieve[a]
    for k, v in t:
        if k not in lcm_factors or lcm_factors[k] < v:
            lcm_factors[k] = v

lcm = 1
for k in lcm_factors:
    for i in range(lcm_factors[k]):
        lcm *= k
        lcm %= 1000000007

result = 0
for i in range(N):
    result += lcm * mpow(A[i], 1000000007-2)
    result %= 1000000007
print(result)

Submission status: Accepted

Solution code:
import fractions
N = int(input())
T = list(map(int, input().split()))
lcm = T[0]
ans = 0
MOD = 1000000007
for i in range(1, N):
  lcm = lcm * T[i] // fractions.gcd(lcm, T[i])
for x in T:
  ans += lcm // x
print(ans % MOD)

Submission status: Accepted

Solution code:
from fractions import gcd
MOD = 10 ** 9 + 7

def main():
    _ = int(input())
    l = list(map(int,input().split()))

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

    ans = 0
    for i in l:
        ans += lcm // i
    ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x*a[i])//gcd(x, a[i])
    return x


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

A = lcm(a);
ans = 0

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

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

Submission status: Accepted

Solution code:
import sys

def compute_gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
def compute_lcm(x, y):
   lcm = (x*y)//compute_gcd(x,y)
   return lcm

def lcm(a):
	x = a[0]
	for i in range(1, len(a)):
		x = compute_lcm(x, a[i])
	return x

n = int(input())

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

MOD = 10 ** 9 + 7

ans = lcm(a)
cur = 0

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

print(cur % MOD)