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

Submission status: Accepted

Solution code:
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()));
#N=10000;A=[1000000 for i in range(N)];
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#グローバル変数
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 # 素数が見つかったら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
#sqr_max_a = int(1.0 * 10**6)
pn = 3
while pn < sqr_max_a:
    pn = next_pn(pn)

# a を素因数分解する
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))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
import math
MOD = 1000000007  # type: int


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])
    # print(lcm)

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

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

Submission status: Accepted

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

MOD = 10**9+7


def main():
    # N = int(input())
    # A = list(map(int, input().split()))
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


#read = sys.stdin.read
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)


# N以下の素数を列挙
# make primes
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


# nの素数判定
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


# nの約数列挙
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  # sortされていない


# nの素因数分解(O(n**0.5)
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


# n以下の素数列挙(O(n log(n))
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


# a以上b未満の素数列挙
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]
#B[i] = lcm_A//A[i]

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

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(tmp, cur)
        #print(divs)
        #print(ret)
        #print('-------')
    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))  # 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(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()

Submission status: Accepted

Solution code:
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) # それまでのLCM
    ans *= tmp//g
    g = tmp
    ans += g//i

print(ans%MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

d = int(input())
nums = list(map(int, input().split(' ')))

lcm_num = 1
for n in nums:
  lcm_num = lcm_base(lcm_num, n)

ans = 0
mod = 10**9 + 7
for n in nums:
  ans += lcm_num//n
print(ans % mod)

Submission status: Accepted

Solution code:
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 range(N):
    lcm_A = lcm(lcm_A, A[i])
    
ans = 0
for i in range(N):
    ans += lcm_A // A[i]

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

print(ans%MOD)

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:
from fractions import gcd
from functools import reduce
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9+7

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

def inv(x):
    return pow(x,R-2,R)

n = inn()
a = inl()
#l = a[0]
#for i in range(1,n):
#    l = l*a[i]//gcd(l,a[i])
l = reduce(lcm_base,a,1)
sm = 0
for i in range(n):
    sm = (sm + inv(a[i]))%R
print((sm*l)%R)

Submission status: Accepted

Solution code:
# エラトステネスを素因数分解とlcm


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

def inverse(a): #aに対し、a**(mod-2)、つまり逆元を返す
  return pow(a, mod-2, mod)

def 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 = 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])
    s %= mod
print(s)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, int(math.sqrt(m)) + 1):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False
        self.ds_memo = {}
        self.ds_memo[1] = set([1])

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d


def M(n): return ModInt(n)
def MI(): return M(I())

class ModInt():
    def __init__(self, n):
        self.n = n

    def __add__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n+x) % mod)

    def __sub__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n-x) % mod)

    def __mul__(self, x):
        x = ModInt.xn(x)
        return ModInt((self.n*x) % mod)

    def __truediv__(self, x):
        x = ModInt.xn(x)
        return ModInt(self.n * pow(x, mod-2, mod) % mod)

    @classmethod
    def xn(cls, x):
        if isinstance(x, ModInt):
            return x.n
        return x

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

def main():
    n = I()
    a = LI()
    pr = Prime(10**12)
    ad = collections.defaultdict(int)
    da = []
    for c in a:
        d = pr.division(c)
        for k,v in d.items():
            if ad[k] < v:
                ad[k] = v
        da.append(d)
    ai = M(1)
    for k,v in ad.items():
        ai *= pow(k, v, mod)

    r = M(0)
    for c in a:
        r += ai / c

    return r


print(main())

Submission status: Accepted

Solution code:
# エラトステネスを素因数分解とlcm


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


def prime_decomposition(n):
    table = defaultdict(int)

    i = 2
    while n % i == 0:
        n //= i
        table[i] += 1

    i = 3
    while i * i <= n:
        while n % i == 0:
            n //= i
            table[i] += 1
        i += 2

    if n > 1:
        table[n] += 1

    return table


def main():
    mod = 10 ** 9 + 7

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

    lcm_d = defaultdict(int)
    for x in a:
        pd = prime_decomposition(x)
        for prime, power in pd.items():
            lcm_d[prime] = max(lcm_d[prime], power)

    lcm_ = 1
    for prime, power in lcm_d.items():
        lcm_ = (lcm_ * pow(prime, power, mod)) % mod

    ret = 0
    for x in a:
        ret = (ret + pow(x, mod - 2, mod)) % mod
    ret = (ret * lcm_) % mod

    print(ret)


if __name__ == '__main__':
    main()