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 fractions
from functools import reduce

MOD = 10**9 + 7


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


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


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


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

    AN_lcm = lcm_list(AN) % MOD

    ans = 0
    for A in AN:
        ans += AN_lcm * modinv(A, MOD)
        ans %= MOD

    print(ans)


main()

Submission status: Accepted

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr

#逆元テーブル
mod = 10 ** 9 + 7
N = 1000002
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

n = int(input())
a = list(map(int, input().split()))
d = [0 for i in range(1000001)]
for ai in a:
    arr = factorization(ai)
    for i, n in arr:
        d[i] = max(d[i], n)

base = 1
for i, n in enumerate(d):
    base = base * i ** n % mod
ans = 0
for ai in a:
    ans = (ans + base * inv_t[ai]) % mod
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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

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

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

LCM = lcm_list(A)
MOD = 10 ** 9 + 7
cnt = 0
for a in A:
  cnt += LCM // a

print(cnt % MOD)

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(1000000)
input = sys.stdin.readline
# from bisect import *
from collections import *
# from heapq import *
# INF = 500000
mod = 10**9+7

def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

N = int(input())
A = [int(x) for x in input().split()]
ps = primes(int(max(A)**0.5)+1)
dic = defaultdict(lambda : 0)
for a in A:
    for i in ps:
        if a < i:
            break
        if a % i == 0:
            c = 0
            while a % i == 0:
                c += 1
                a //= i
            if dic[i] < c:
                dic[i] = c
    if a > 1 and dic[a] == 0:
        dic[a] = 1
MAX = 1
for k in dic:
    MAX = MAX * pow(k, dic[k], mod) % mod
ans = 0
for a in A:
    ans += MAX * pow(a, mod-2, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
#from math import gcd
from fractions import gcd
def ExtGCD(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = ExtGCD(b, a % b)
        x -= (a // b) * y
        return d, y, x
def ModInv(a, mod):
    return ExtGCD(a, mod)[1] % mod
def lcm(a,b):
    return a*b//gcd(a,b)
def main():
    n=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    lcm=A[0]
    for i in range(1,n):
        lcm = lcm * A[i] //gcd(lcm, A[i])
    ans=0
    for a in A:
        ans += lcm*ModInv(a,mod)%mod
    print(ans%mod)
main()

Submission status: Accepted

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

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

def modpow(x, n, mod):
    res = 1
    while n > 0:
        if n%2 == 1:
            res = res*x%mod
        x = x*x%mod
        n >>= 1
    return res

mod = 10**9+7

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

g = 0
for x in a:
    g = gcd(g, x)

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

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from fractions import gcd
    from collections import defaultdict
    input = sys.stdin.buffer.readline

    def p(n):
        ret = defaultdict(int)
        d = 2
        m = int(n**0.5)
        while n > 1:
            if n % d == 0:
                ret[d] += 1
                n //= d
            else:
                d += 1
                if d > m:
                    ret[n] += 1
                    break
        return ret

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

    prime = defaultdict(int)
    p_list = []
    for a in A:
        pp = p(a)
        p_list.append(pp)
        for pr in pp.keys():
            ppr = prime[pr]
            pppr = pp[pr]
            if ppr < pppr:
                prime[pr] = pppr

    M = 1
    for pr in prime.keys():
        M = (M * pow(pr, prime[pr], mod))%mod

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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

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

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

    ans = 0
    mod = 10**9 + 7
    for i in a:
        ans += lcm // i
    ans %= mod
    print(ans)

main()

Submission status: Accepted

Solution code:
mod = 10**9+7
def fctr(n): 
    res=[]
    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:
            res.append([i,c])
            c=0
    if n!=1:
        res.append([n,1])
    return res
N = int(input())
A = list(map(int, input().split()))
A_inv = [pow(a, mod-2, mod) for a in A]
primes = [0]*(10**6+1)
for a in A:
    res = fctr(a)
    for i, c in res:
        primes[i] = max(primes[i], c)
m = 1
for i in range(1, 10**6+1):
    c = primes[i]
    m*=pow(i, c, mod)
    m%=mod
ans = 0
for a in A_inv:
    ans+=m*a
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
import fractions

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
gcda = a[0]
ans = 0
for i in range(1, n):
    gcda = gcda * a[i] // fractions.gcd(gcda, a[i])
for j in a:
  ans += gcda//j
ans %= (10**9)+7
print(ans)

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)

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

l_cm = lcm_list(l)

for i in range(0,n):
    c = c + l_cm//l[i]
print(c%(10**9 + 7))

Submission status: Accepted

Solution code:
import fractions
mod = 10**9+7
def LCM(a,b):
    return a*b//fractions.gcd(a,b)

N=int(input())
A = [int(i) for i in input().split()]
curLCM = A[0]
for i in range(1,N):
    curLCM = LCM(curLCM,A[i])
ans = 0
for a in A:
    ans += curLCM//a 
print(ans%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())
A = list(map(int,input().split()))
mod = 10**9+7

LCM = lcm_list(A)
ans = 0

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

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

MOD = 10 ** 9 + 7


def lcm(*nums):
    return reduce(lambda x, y: (x * y) // gcd(x, y), nums, 1)


# print(lcm(*[2, 3, 4])) -> 12

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

l = lcm(*a)
ans = 0

for ai in a:
    ans += l // ai

print(ans % MOD)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
n=int(input())
l=list(map(int,input().split()))


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


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

k=lcm_list(l)

m=0
for i in range(n):
    m+=k//l[i]
print(m%(10**9+7))

Submission status: Accepted

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr

#factorization(24) 

## [[2, 3], [3, 1]]
z=[0]*(10**6+1)
for i in l:
    if i>=2:
        re=factorization(i)
        for p in re:
            z[p[0]]=max(z[p[0]],p[1])
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
w=1
mod=10**9+7
for i in range(10**6+1):
    w*=pow(i,z[i],mod)
    w%=mod
kai=0
for i in l:
    kai+=w*mod_inv(i,mod)
    kai%=mod
print(kai)

Submission status: Accepted

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

MOD = 10**9 + 7
def inv(a):
	b = MOD
	u = 1
	v = 0
	while b > 0:
		t = a // b
		a -= t*b
		a,b = b,a
		u -= t*v
		u,v = v,u
	u %= MOD
	return u

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

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

L = lcm % MOD
ans = 0
for a in A:
	ans = (ans + L * inv(a)) % MOD
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

n=int((input()))
a=list(map(int,input().split()))
mod=10**9+7
b=0
for i in a:
    b+=(pow(i,mod-2,mod))
    
tmp=b%mod

def gcd(x,y):
    while y!=0:
        x,y=y,x%y
    return x
    
def lcm(x,y):
    G=gcd(x,y)
    return (x)*(y)//G
    
L=a[0]
for i in a:
    L=lcm(L,i)
    


print(L*tmp%mod)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
con = 10 ** 9 + 7

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#素因数分解
L = [1 for i in range(1001)]
L[0] = 0
L[1] = 0
plist = []
for i in range(1001):
	if L[i] == 1:
		plist.append(i)
		c = 2
		while True:
			if i * c <= 1000:
				L[i * c] = 0
				c += 1
			else:
				break

#処理内容
def main():
	N = int(input())
	A = getlist()
	D = defaultdict(int)
	for k in range(N):
		K = A[k]
		Dpre = defaultdict(int)
		for i in plist:
			while True:
				if K % i == 0:
					Dpre[i] += 1
					K = int(K // i)
				if K % i != 0:
					break
		if K != 1:
			Dpre[K] += 1
		# print(Dpre)
		for i in Dpre:
			D[i] = max(D[i], Dpre[i])
	# print(D)
	lcm = 1
	for i in D:
		for j in range(D[i]):
			lcm = (lcm * i) % con
	# print(lcm)

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

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def e_flatten(MOD=10**9 + 7):
    from fractions import gcd
    from functools import reduce
    N = int(input())
    A = [int(i) for i in input().split()]

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

    def inv(n, mod=MOD):
        return pow(n, mod - 2, mod)

    l = reduce(lcm, A) % MOD
    ans = [(l * inv(a)) % MOD for a in A]
    return sum(ans) % MOD

print(e_flatten())

Submission status: Accepted

Solution code:
import fractions
mod = 10**9+7

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


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


ans = 0
for i in range(n):
    ans += inv(a[i], mod)
    ans %= mod


lcm = a[0]

for i in range(1, n):
    lcm = lcm*a[i] // fractions.gcd(lcm,a[i])

lcm %= mod

ans *= lcm
ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

def main():
    n = input()
    aa = list(map(int, raw_input().split()))
    g = 1
    for a in aa:
        g *= a // gcd(a, g)
    ans = 0
    MOD = 10 ** 9 + 7
    g %= MOD
    for a in aa:
        ans = (ans + g * pow(a, MOD - 2, MOD)) % MOD
    print(ans)


main()

Submission status: Accepted

Solution code:
from fractions import gcd
import sys

input = sys.stdin.readline

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

MOD = 10 ** 9 + 7


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


l = A[0]
for a in A:
    l = lcm(l, a)

res = 0
for a in A:
    res = (res + (l * pow(a, MOD - 2, MOD)) % MOD) % MOD
    # res = (res + l // a) % MOD

print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

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

l = a[0]
for i in a[1:]:
    l = lcm(l, i)
b = []
for i in a:
    b.append(l//i)
ans = sum(b) % (10 ** 9 + 7)
print(ans)

Submission status: Accepted

Solution code:
import fractions
n = int(input())
li = list(map(int, input().split()))

g = li[0]
for i in range(1, n):
    g = g * li[i] // fractions.gcd(g, li[i])

ans = 0
for i in range(n):
    ans += g // li[i]

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

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
res = 0
for x in a:
  l = x * l // gcd(x, l)
l %= mod
for x in a:
  res += l * pow(x, mod - 2, mod)
  res %= mod
print(res)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

# 最小公倍数を求める
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

BASE = 10**9 + 7

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

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

print(ans%BASE)

Submission status: Accepted

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

primes = {}

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

    if val != 1:
        if val not in primes:
            primes[val] = 1


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

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

ans = 0
for val in a:
    ans += lcm * inv(val) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

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

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

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

ans = 0
for i in range(N):
    ans += a * pow(A[i], mod-2, mod)

print(ans % mod)

Submission status: Accepted

Solution code:
N = int(input())

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

count = 0
for i in range(N):
    count += ans // a[i]

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

Submission status: Accepted

Solution code:

from fractions import gcd
import random
n = int(input())
a = list(map(int, input().split( )))
random.shuffle(a)
#最小公倍数でよいか？
#全てのjについてAiBiはAjで割り切れる
#計算時間は？

mod =10**9+7
def lcd(x,y):
    g = gcd(x,y)
    return x*y//g

ag1 = 1
for i in range(n//2):
    ag1 = lcd(ag1,a[i])
ag2 = 1
for i in range(n//2,n):
    ag2 = lcd(ag2,a[i])

ag3 = lcd(ag1,ag2)

ans = 0

for i in range(n//2):
    ans += ag1//a[i]
ans*=ag3//ag1
ans %=mod
ans2 = 0
for i in range(n//2,n):
    ans2 += ag2//a[i]
ans2*= ag3//ag2
ans2%=mod 
ans += ans2
ans %=mod
print(ans)

Submission status: Accepted

Solution code:
LARGE = 10 ** 9 + 7


def solve(n, a_list):

    # inverse
    res = 0
    for i in range(n):
        res += pow(a_list[i], LARGE - 2, LARGE)
        res %= LARGE

    # primes
    p_candidate_list = [1] * 10 ** 3
    p_candidate_list[0] = 0
    p_candidate_list[1] = 0
    for p in range(2, 10 ** 3):
        if p_candidate_list[p]:
            for q in range(p * p, 10 ** 3, p):
                p_candidate_list[q] = 0
    primes_1000 = [p for p in range(1000) if p_candidate_list[p]]

    lcm = 1
    for p in primes_1000:
        r_max = 0
        for i in range(n):
            r = 0
            while a_list[i] % p == 0:
                r += 1
                a_list[i] = a_list[i] // p
            r_max = max(r_max, r)
        lcm *= pow(int(p), r_max, LARGE)
        lcm %= LARGE

    for q in set(a_list):
        lcm *= q
        lcm %= LARGE

    return res * lcm % LARGE


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(3, [2, 3, 4]) == 13
    assert solve(5, [12, 12, 12, 12, 12]) == 5
    assert solve(3, [1000000, 999999, 999998]) == 996989508


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
import fractions

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

ans = a_list[0]
for i in range(1, n):
    ans = ans * a_list[i] // fractions.gcd(ans, a_list[i])

num = 0
for a in a_list:
    num += ans//a

print(num%1000000007)

Submission status: Accepted

Solution code:
from fractions import gcd
MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
ans = 0
p = 1
for a in A:
    b = gcd(a,p)
    ans = (ans * (a//b) % MOD + (p//b))%MOD
    p = a*p//b
print(ans)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

MOD = 10**9 + 7

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

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

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

    l = lcm_list(A)
    ans = 0

    for x in A:
        ans += l // x
        
    print(ans % MOD)

    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions
N = int(input())
a = list(map(int, input().split()))

ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])

kai = 0
for i in range(N):
  kai += ans // a[i]

print(kai % (pow(10,9) + 7))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
mod = 1000000007
A = [int(i) for i in input().split()]
import fractions
from fractions import gcd
def lcm(x,y) :
    return(x*y) // fractions.gcd(x,y)
k =  A[0]
for i in range(1,N) :
    k = lcm(k,A[i])
sum = 0
for i in range(N) :
    B = k // A[i]
    sum += B
sum = sum % mod
print(sum)

Submission status: Accepted

Solution code:
N = int(input())
listA = list(map(int, input().split(' ')))

from fractions import gcd

tmp_lcm = 1
sumB = 0
for i in listA:
  tmp_gcd = gcd(tmp_lcm, i)
  next_lcm = (tmp_lcm * i) // tmp_gcd
  sumB = sumB * (next_lcm // tmp_lcm) + (next_lcm // i)
  tmp_lcm = next_lcm

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

Submission status: Accepted

Solution code:
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b,a%b)
def lcm(a,b):
	p = a*b
	g = gcd(a,b);
	return p//g
MOD = int(10**9+7)
n = int(input())
a = list(map(int,input().split()))
lc = a[0];
for i in range(1,n):
	lc = lcm(a[i],lc)
ans = 0
for i in range(n):
	ans += (lc//a[i])
print(ans%MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import fractions
from functools import reduce
N=int(input())
A=list(map(int,input().split()))

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
l=lcm_list(A)
ans=0

for i in range(N):
    ans+=(l//A[i])
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
def factorize(a):
    factors = {}
    v = a
    if v%2==0: factors[2]=0
    while v%2==0:
        v//=2
        factors[2]+=1
    
    p = 3
    while p*p<=a:
        if v%p==0: factors[p] = 0
        while v%p==0:
            v//=p
            factors[p]+=1
        p+=2
    if v>1: factors[v] = 1
    return factors

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

# calc lcm
lcm = {}
for a in A:
    factors_a = factorize(a)
    for k, v in factors_a.items():
        if k not in lcm or lcm[k]<v: lcm[k] = v

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

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

from functools import reduce
def lcm_multi(num_list):
    return reduce(lcm, num_list, 1)
k=lcm_multi(a)
answer=0
for i in range(n):
    answer+=k//a[i]
print(answer%(10**9+7))

Submission status: Accepted

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

def lcm(a,b):
	p = a*b
	g = gcd(a,b);
	return p//g
MOD = int(10**9+7)
n = int(input())
a = list(map(int,input().split()))
lc = a[0];
for i in range(1,n):
	lc = lcm(a[i],lc)
ans = 0
for i in range(n):
	ans += (lc//a[i])
print(ans%MOD)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
n=int(input())
num=list(map(int,input().split()))
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
z=lcm(*num)
ans=0
for i in range(n):
  ans+=z//num[i]
print(ans%1000000007)

Submission status: Accepted

Solution code:
import functools
import fractions


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


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

n = int(input())
l = list(map(int, input().split()))
ans = 0
lcm_l = lcm_list(l)
for i in range(n):
    ans += (lcm_l // l[i])
print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
from random import randint
from collections import defaultdict
from itertools import accumulate
from fractions import gcd
from collections import defaultdict
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7

def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i]:
            P.append(i)
            for j in range(2*i, N+1, i):
                sieve[j] = 0
    return P

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


P = primes(10**3)

size = 10**6 + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size
 
g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 

N = int(input())
A = inpl()

#N = 10**4
#A = [randint(0, 10**6) for _ in range(10**4)]
D = defaultdict(int)
for a in A:
    for p in P:
        tmp = 0
        while a%p == 0:
            tmp += 1
            a //= p
        if tmp:
            D[p] = max(D[p], tmp)
        if a == 1:
            break
    if a != 1:
        D[a] = 1

lmc = 1
for k, v in D.items():
    lmc = lmc * pow(k, v, MOD)%MOD

ans = 0
for a in A:
    ans = (ans + lmc*inverse[a])%MOD
print(ans)

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)

MOD = 1000000000 + 7

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

L = 1
for a in A:
  L = lcm(L, a)
ans = 0
for a in A:
  ans += L // a
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

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)
    
def gcd_list(numbers):
    return reduce(gcd, numbers)

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

div = 10 ** 9 + 7

LCM =  lcm_list(A)

total = 0

for i in range(N):
  total += LCM // A[i]
  
print(total % div)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def gcd(a,b):
    while b:a,b=b,a%b
    return a

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

def main():
    md=10**9+7
    n=II()
    aa=LI()
    l=1
    for a in aa:
        l=lcm(l,a)
    bb=[]
    for a in aa:
        bb.append(l//a)
    print(sum(bb)%md)

main()

Submission status: Accepted

Solution code:
import math
from collections import Counter
MOD = 10 ** 9 + 7

# 雑な方法
primes = []
for i in range(2, 1001):
    for j in range(2, math.floor(math.sqrt(i))+1):
        if i % j == 0:
            break
    else:
        primes.append(i)

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

cts = Counter()
for a in As:
    x = a
    ct = Counter()
    for p in primes:
        if p > x:
            break
        while x % p == 0:
            x //= p
            ct[p] += 1
    if x > 1:
        ct[x] += 1
    for k, v in ct.items():
        ctsk = cts[k]
        cts[k] = ctsk if ctsk >= v else v

ans = 1
for k, v in cts.items():
    ans *= pow(k, v, MOD)
    ans %= MOD

total = 0
for a in As:
    total += ans * pow(a, MOD-2, MOD)
    total %= MOD
print(total)

Submission status: Accepted

Solution code:
import math
mod = 10**9+7

# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m=mod):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

import sys
input = sys.stdin.readline


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

dic = {}
for a in A:
    pr = prime(a)
    for num, count in pr.items():
        if not num in dic.keys():
            dic[num] = count
        else:
            if dic[num] < count:
                dic[num] = count

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

ans = 0
for a in A:
    ans += mod_inv(a)*lcm
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

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

# a//b (MOD p)
def div_mod(a, b, p):
    return (a * pow(b, p-2, p)) % p

ans = 0
target = reduce(lcm, A)
for i in range(N):
    ans += div_mod(target, A[i], MOD)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7

lcm = a[0]
for i in range(1,n):
    lcm = lcm*a[i]//gcd(lcm,a[i])

lcm %= mod

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

Submission status: Accepted

Solution code:
from functools import reduce
import fractions

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

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
N=int(input())
A=[int(x) for x in input().split()]
lcm=lcm_list(A)
ans=0
for a in A:
  ans+=lcm//a
print(ans%1000000007)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
c=[1]*(10**3+1)
p={}
q=[]
m=10**9+7
for i in range(2,10**3+1):
    if c[i]:
        p[i]=0
        q.append(i)
        for j in range(i*2,10**3+1,i):
            c[j]=0
for j in a:
    i=0
    while j!=1:
        if j%q[i]==0:
            d=0
            while j%q[i]==0:
                j//=q[i]
                d+=1
            p[q[i]]=max(p[q[i]],d)
        i+=1
        if i==168:
            break
    p[j]=1
e=1
for i in p.keys():
    e=(e*pow(i,p[i],m))%m
c=0
for i in a:
    c=(c+e*pow(i,m-2,m))%m
print(c)

Submission status: Accepted

Solution code:
import fractions

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

aset = set(a)

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

if n == 1:
    print(1)

elif 1 < n:
    g = lcm(a[0], a[1])

    if n != 2:
        for val in aset:
            g = lcm(g, val)

    ans = 0
    for val in a:
        ans += g//val

    print(ans % mod)

Submission status: Accepted

Solution code:
N = int(input())
A = 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)

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)