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:
from collections import defaultdict
from functools import lru_cache
import math


def trial_division(n):
    factor = defaultdict(int)
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor[num] += 1
    factor[n] += 1
    return factor


@lru_cache(maxsize=None)
def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
numbers = defaultdict(int)
for a_i in a:
    for i, v in trial_division(a_i).items():
        numbers[i] = max(v, numbers[i])

l = 1
for i, v in numbers.items():
    l *= powmod(i, v, mod)
    l %= mod


ans = 0
for i in a:
    r = powmod(i, mod-2, mod)
    ans += l * r
    ans %= mod
print(int(ans))

Submission status: Accepted

Solution code:
from fractions import gcd
MOD=10**9+7
def lcm(x,y):return x*y//gcd(x,y)
def inv(x):return pow(x,MOD-2,MOD)
def main():
  n,*a=map(int,open(0).read().split())
  L=1
  for i in a:L=lcm(L,i)
  L=L%MOD
  ans=0
  for i in a:ans=(ans+L*inv(i))%MOD  
  print(ans)
main()

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def inv(x):return pow(x,MOD-2,MOD)
MOD=10**9+7
def main():
  n,*a=map(int,open(0).read().split())
  L=1
  for i in a:L=lcm(L,i)
  L=L%MOD
  ans=0
  for i in a:ans=(ans+L*inv(i))%MOD  
  print(ans)
main()

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
MOD=10**9+7
from fractions import gcd

def lcm(x,y):return x*y//gcd(x,y)
def inv(x):return pow(x,MOD-2,MOD)

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

Submission status: Accepted

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

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

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

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

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

L=L%MOD
ans=0
for i in a:
  ans=(ans+L*inv(i))%MOD
  

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
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()
a = inpl()
def lcm(a,b):
    return a*b//fractions.gcd(a,b)
r = 1

for i in a:
    r = lcm(i,r)
r %= mod
res = 0
for i in a:
    res += r*pow(i,mod-2,mod)
    res %= mod
print(res)

Submission status: Accepted

Solution code:
def g(a, b):
    m = a * b
    if a < b:
        a, b = b, a
    while True:
        a, b = b, (a % b)
        if b == 0:
            return m // a    
        
N = int(input())
A = list(map(int,input().split()))
MOD = 10 ** 9 + 7
ans = 0
c = 1
for i in range(N):
    c = g(c, A[i])
for i in range(N):
    ans += c // A[i]
print(ans % MOD)

Submission status: Accepted

Solution code:
from fractions import gcd
import math
n = int(input())
a = list(map(int, input().split()))
MOD=10**9+7
lcm=1
for i in range(n):
    lcm*=a[i]//gcd(lcm,a[i])
res=0
for i in range(n):
    res+=lcm//a[i]
print(res%MOD)

Submission status: Accepted

Solution code:
import math
import fractions
import functools
def main():
    n = int(input())
    a = [int(t)for t in input().split()]

    M = 10**9+7
    culcm = functools.reduce(lcm,a)

    b = [culcm//a_i for a_i in a]

    print(sum(b)%M)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
def sosuu(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


N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
M=1
dic={}
for a in A:
    arr=sosuu(a)
    for b,c in arr:#b,c:素数、指数
        if b in dic:
            if c>dic[b]:
                M=M*pow(b,c-dic[b],mod)%mod
                dic[b]=c
        else:
            dic.update({b:c})
            M=M*pow(b,c,mod)%mod
M%=mod
print(sum([M*pow(a,mod-2,mod)%mod for a in A])%mod)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
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

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

M=1

dic={}

for a in A:
    Z=1
    arr=factorization(a)
    for b,c in arr:
        if b in dic:
            if c>dic[b]:
                M=M*pow(b,c-dic[b],mod)%mod
                dic[b]=c
        else:
            dic.update({b:c})
            M=M*pow(b,c,mod)%mod
M%=mod

print(sum([M*pow(a,mod-2,mod)%mod for a in A])%mod)

Submission status: Accepted

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
M=1
for a in A:
    M=((M * a) // gcd(M, a))
M%=mod

count=0

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

Submission status: Accepted

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
M=1
for a in A:
    M=((M * a) // gcd(M, a))
M%=mod

print(sum([M*pow(a,mod-2,mod)%mod for a in A])%mod)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
M=1
for a in A:
    M=((M * a) // gcd(M, a))
M%=mod

print(sum([M*pow(a,mod-2,mod)%mod for a in A])%mod)

Submission status: Accepted

Solution code:
import fractions
MOD = 1000000007

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


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


x = A[0]
for a in A:
    x = get_lcm(a, x)


ret = 0
for a in A:
    ret += x // a

print(ret % MOD)

Submission status: Accepted

Solution code:
def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007

def prime(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > x**(1/2): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primes = prime(10**6)
pd = {}
for i in range(len(primes)):
	pd[primes[i]] = i
MOD = 10**9+7
N = int(input())
A = [int(i) for i in input().split()]
K = [0]*len(primes)
for i in range(N):
	a = A[i]
	for i in range(len(primes)):
		p = primes[i]
		if a == 1:
			break
		elif p > 1000:
			K[pd[a]] = 1
			break
		else:
			cou = 0
			while a%p==0:
				a = a//p
				cou += 1
			K[i] = max(cou, K[i])
kv = 1
for i in range(len(primes)):
	kv *= power(primes[i], K[i])
	kv %= MOD
ans = 0
for i in range(N):
	ans += divide(kv, A[i])
	ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy

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

"""
普通に最小公倍数を計算すると桁数が莫大になって
桁溢れor多倍長整数を使っても計算が一気に遅くなるのがこの問題のミソ

桁数の大きい数は素因数分解の形で保持すると高速にmod計算が可能なので、これを用いる。
まずは1000以下の素数テーブルを用意。
"""
prime = [i for i in range(2, 10**3)]
for p in prime:
    prime = [x for x in prime if (x == p or x % p != 0)]

def div(a, n):
    """
    自然数aがnで何回割れるかと、割り尽くした残りを返す
    """
    num = 0
    while a % n == 0:
        num += 1
        a = a // n
    return num, a

"""
素数pごとに、各A[i]がpで何回割れるかを求め、iでループを回した中での最大値をe_pとすると
A[0],...A[N-1]の最小公倍数はL = ¥Prod_p p^{e_p}になる。
これならmodで桁数削減が可能。

ただし素数テーブルは1000までしか用意してないので、それ以上の素数はリストAの中に吐き出させ、
あとでそれをLに組み込む。
"""
L = 1
for p in prime:
    e = 0
    for i in range(N):
        cand, A[i] = div(A[i], p)
        e = max(e, cand)
    L *= pow(p, e, mod)
    L %= mod
for a in set(A):
    L *= a
    L %= mod

"""
あとは答えを求めるのみ。
ただしLをmodで算出しているので、単純にL/A[i]を加算すると答えが狂う。
そこでA[i]^{-1}をmodで求めてLに乗算する。
"""
ans = 0
for i in range(N):
    inv = pow(B[i], mod - 2, mod)
    ans += L * inv
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
class PrimeOptimizer:
    def __init__(self, MAX_NUM=10**3):
        is_prime = [True] * MAX_NUM
        is_prime[0] = False
        is_prime[1] = False
        primes = []
        for i in range(MAX_NUM):
            if is_prime[i]:
                primes.append(i)
                for j in range(2*i, MAX_NUM, i):
                    is_prime[j] = False
        self.primes = primes

    def prime_factorization(self, x):
        res = {}
        for prime in self.primes:
            while x % prime == 0:
                if not prime in res:
                    res[prime] = 0
                res[prime] += 1
                x //= prime
        if x > 1:
            res[x] = 1
        return res

MOD = 10**9+7

def mod_pow(p, q):
    res = 1
    while q:
        if q & 1:
            res = (res * p) % MOD
        p = (p * p) % MOD
        q //= 2
    return res

def mod_inv(p):
    return mod_pow(p, MOD - 2)

def solve(n, a):
    primeOpt = PrimeOptimizer()
    D = {}
    for i in range(n):
        prime_num_mapping = primeOpt.prime_factorization(a[i])
        for prime, num in prime_num_mapping.items():
            if not prime in D:
                D[prime] = 0
            D[prime] = max(D[prime], num)
    L = 1
    for prime, num in D.items():
        L = (L * mod_pow(prime, num)) % MOD
    res = sum([L * mod_inv(x) % MOD for x in a])
    return res % MOD

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

Submission status: Accepted

Solution code:
import math
import fractions
def lcm(x, y):
  return (x * y) // fractions.gcd(x, y)
  
def main():
  mod = 10**9 +7
  n = int(input())
  ls = list(map(int,input().split()))
  
  t = ls[0]
  for a in ls:
    t = lcm(t,a)
  
  ans = 0
  for a in ls:
    ans += t//a
  print(ans%mod)
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import math
import fractions
def lcm(x, y):
  return (x * y) // fractions.gcd(x, y)

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

MODp = 1000000007
K = 1
for i in range(N):
  K = lcm(K,l[i])

Ans = 0
for i in range(N):
  Ans += ((K // l[i]))

Ans = Ans % MODp
print(Ans)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
# Python3 program to compute LCM of 
# array elements modulo M
MAX = 10**6+1
mod = 1000000007
prime = [0 for i in range(MAX)] 
max_map = dict() 
# function to return a^n 
def power(a, n):
	if n == 0: 
		return 1
	p = power(a, n // 2) % mod
	p = (p * p) % mod
	if n & 1: 
		p = (p * a) % mod
	return p 

# function to find the smallest prime
# factors of numbers upto MAX
def sieve(): 
	prime[0], prime[1] = 1, 1
	for i in range(2, MAX): 
		if prime[i] == 0: 
			for j in range(i * 2, MAX, i): 
				if prime[j] == 0: 
					prime[j] = i 
			prime[i] = i 

# function to return the LCM modulo M 
def lcmModuloM(arr, n): 
	for i in range(n): 
		num = arr[i] 
		temp = dict() 
		# temp stores mapping of prime factors 
		# to its power for the current element 
		while num > 1:
			# factor is the smallest prime
			# factor of num
			factor = prime[num]
			# Increase count of factor in temp
			if factor in temp.keys():
				temp[factor] += 1
			else:
				temp[factor] = 1
			# Reduce num by its prime factor
			num = num // factor
		for i in temp:
			# store the higest power of every prime
			# found till now in a new map max_map
			if i in max_map.keys():
				max_map[i] = max(max_map[i], temp[i])
			else: 
				max_map[i] = temp[i]
	ans = 1
	for i in max_map:
		ans = (ans * power(i, max_map[i])) % mod
	return ans
# Driver code
sieve()
X = int(input())
A = list(map(int,input().split()))
N = max(A)
value = lcmModuloM(A, X)
ans = 0
for i in range(X):
    ans += value*pow(A[i], mod-2, mod)%mod
print(ans%mod)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7
N=int(input())
A=list(map(int,input().split()))
pr=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 
71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 
313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 
787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
pl=[0]*168
l=[[] for i in range(N)]
for i in range(N):
    t=A[i]
    for j,p in enumerate(pr):
        c=0
        while 1:
            if t%p:
                break
            t//=p
            l[i].append(j)
            c+=1
        if c>pl[j]:
            pl[j]=c
    if t>1:
        pr.append(t)
        l[i].append(len(pl))
        pl.append(1)
lcm=1
for i,p in enumerate(pl):
    lcm=(lcm*pow(pr[i],p,mod))%mod
ipr=[]
for i in pr:
    ipr.append(pow(i,mod-2,mod))
a=0
for i in l:
    t=lcm
    for j in i:
        t=(t*ipr[j])%mod
    a=(a+t)%mod
print(a)

Submission status: Accepted

Solution code:
MOD = int(1e9+7)

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

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


N = int(input())
A = [int(i) for i in 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]

print(ans % MOD)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

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

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

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

ans = 0
MOD = int(1e9+7)
for i in range(N):
    ans += l // A[i]

print(ans % MOD)

Submission status: Accepted

Solution code:
import fractions
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1, n): l = l // fractions.gcd(l, a[i]) * a[i]
s = 0
for i in range(n): s += l // a[i]
print(s % 1000000007)

Submission status: Accepted

Solution code:
input();a=list(map(int,input().split()))
import fractions as f
l,r=a[0],1
for i in range(1,len(a)):
  g=f.gcd(l,a[i])
  s,t=l//g,a[i]//g
  l,r=s*t*g,(r*t+s)%(10**9+7)
print(r)

Submission status: Accepted

Solution code:
M=10**9+7
n=int(input())
a=list(map(int,input().split()))
import fractions as f
l,r=a[0],1
for i in range(1,n):
  g=f.gcd(l,a[i])
  s,t=l//g,a[i]//g
  l,r=s*t*g,(r*t+s)%M
print(r)

Submission status: Accepted

Solution code:
M=10**9+7
n=int(input())
a=list(map(int, input().split()))
import fractions as f
l,r=a[0],1
for i in range(1,n):
  g=f.gcd(l,a[i])
  s,t=l//g,a[i]//g
  l,r=s*t*g,(r*t+s)%M
print(r)

Submission status: Accepted

Solution code:
M=10**9+7
n=int(input())
a=list(map(int, input().split()))
def f(x, y):
  while y: x,y=y,x%y
  return x
l,r=a[0],1
for i in range(1,n):
  g=f(l,a[i])
  s,t=l//g,a[i]//g
  l,r=s*t*g,(r*t+s)%M
print(r)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
n=int(input())
A=list(map(int,input().split()))
lc=reduce(lambda a,b: a*b//gcd(a,b),A)
b=[lc//i for i in A]
print(sum(b)%(1000*1000000+7))

Submission status: Accepted

Solution code:
import fractions

def main():
    mod = 10**9+7
    N = int(input())
    A = list(map(int,input().split()))
    lcm = 1
    for Ai in A:
        lcm = lcm*Ai//fractions.gcd(lcm,Ai)
    lcm %= mod
    ans = 0
    for Ai in A:
        ans += lcm*pow(Ai,mod-2,mod)%mod
        ans %= mod
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class PrimeOptimizer:
    def __init__(self, MAX_NUM=10**3):
        is_prime = [True] * MAX_NUM
        is_prime[0] = False
        is_prime[1] = False
        primes = []
        for i in range(MAX_NUM):
            if is_prime[i]:
                primes.append(i)
                for j in range(2*i, MAX_NUM, i):
                    is_prime[j] = False
        self.primes = primes

    def prime_factorization(self, x):
        res = {}
        for prime in self.primes:
            while x % prime == 0:
                if not prime in res:
                    res[prime] = 0
                res[prime] += 1
                x //= prime
        if x > 1:
            res[x] = 1
        return res

MOD = 10**9+7

def mod_pow(p, q):
    res = 1
    while q:
        if q & 1:
            res = (res * p) % MOD
        p = (p * p) % MOD
        q //= 2
    return res

def mod_inv(p):
    return mod_pow(p, MOD - 2)

def solve(n, a):
    primeOpt = PrimeOptimizer()
    D = {}
    for i in range(n):
        prime_num_mapping = primeOpt.prime_factorization(a[i])
        for prime, num in prime_num_mapping.items():
            if not prime in D:
                D[prime] = 0
            D[prime] = max(D[prime], num)
    L = 1
    for prime, num in D.items():
        L = (L * mod_pow(prime, num)) % MOD
    res = sum([L * mod_inv(x) % MOD for x in a])
    return res % MOD

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

Submission status: Accepted

Solution code:
# エラトステネスの篩, フェルマーの小定理
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 * pow(A[i], 1000000007-2, 1000000007)
    result %= 1000000007
print(result)

Submission status: Accepted

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

#############
# Libraries #
#############

import math
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

#############
# Main Code #
#############

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

LCM = {}

for i in l:
  fact = factorization(i)
  for j in fact:
    if j[0] not in LCM:
      LCM[j[0]] = j[1]
    else:
      if LCM[j[0]] < j[1]:
         LCM[j[0]] = j[1]

lcm = 1
for i in LCM:
  lcm = lcm * pow(i,LCM[i],MOD) % MOD

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

print(ans)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
p=10**9+7
def lcm_base(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm(*numbers):
    return reduce(lcm_base,numbers,1)
num=lcm(*a)
l=0
for i in range(n):
  l+=num*pow(a[i],p-2,p)
print(l%p)

Submission status: Accepted

Solution code:
import sys
import math

sys.setrecursionlimit(1000000)
input = lambda: sys.stdin.readline().rstrip()


def inverse(x, mod):
    return pow(x, mod - 2, mod)


def factorize(x):
    count = {}
    i = 2
    while i * i <= x:
        while x % i == 0:
            x //= i
            count[i] = count.get(i, 0) + 1
        i += 1
    if x > 1:
        count[x] = count.get(x, 0) + 1
    return count


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

A = list(map(factorize, A))

lcm = {}
for i in A:
    for factor, count in i.items():
        lcm[factor] = max(lcm.get(factor, 0), count)

MOD = 1000000007

lcm_int = 1
for factor, count in lcm.items():
    lcm_int *= pow(factor, count, MOD)
    lcm_int %= MOD

ans = 0
for i in A:
    B = lcm_int
    for factor, count in i.items():
        B *= inverse(pow(factor, count, MOD), MOD)
        B % MOD
    ans = (ans + B) % MOD
print(ans)

Submission status: Accepted

Solution code:
def read_values():
    return map(int, input().split())
 
 
def read_list():
    return list(read_values())

def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
  
    u = {}
    for a in A:
      m = 2
      while m * m <= a:
        c = 0
        while a % m == 0:
          c += 1
          a //= m
        if c > 0:
          u[m] = max(u.get(m, 0), c)
        m += 1
      if a > 1:
        u[a] = max(u.get(a, 0), 1)

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

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

    print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def g(a, b):
    if a > b:
        a, b = b, a
    while b % a:
        a, b = b % a, a
    return a


def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()

    B = 1
    for a in A:
        B *= a // g(B, a)
    
    print(sum(B // a for a in A) % mod)


if __name__ == "__main__":
    main()

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())
mod = int(1e9 + 7)
a = [int(i) for i in input().split()]
ans = int(1)
for i in a:
    ans = lcm(ans,i)

print(sum(ans//i for i in a)%mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
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
    return [w[0],w[1]]
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod + x % mod)% mod
def comb(n,k,mod):
    c = 1
    for i in range(k):
        c = c*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
    return c
n = int(input())
a = list(map(int,input().split()))
g = a[0]
ans = 1
mod = 10**9 + 7
for i in range(1,n):
    p = fractions.gcd(g,a[i])
    g1 = (a[i]//p)*g
    ans *= (g1//g)
    ans %= mod
    ans += g1//a[i]
    ans %= mod
    g = g1
print(ans)

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

n = I()
a = LI()
lst = [0]*(10**6+1)
for i in a:
    l = factorization(i)
    for (j,k) in l:
        lst[j] = max(lst[j],k)

t = 1
for i in range(1,10**6+1):
    if lst[i] != 0:
        t = t*(i**lst[i]) % mod
ans = 0
for i in a:
    ans += t*pow(i,mod-2,mod) % mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
MAX_NUM = 10**3
is_prime = [True] * MAX_NUM
is_prime[0] = False
is_prime[1] = False
primes = []
for i in range(MAX_NUM):
    if is_prime[i]:
        primes.append(i)
        for j in range(2*i, MAX_NUM, i):
            is_prime[j] = False

def prime_factorization(x):
    res = {}
    for prime in primes:
        while x % prime == 0:
            if not prime in res:
                res[prime] = 0
            res[prime] += 1
            x //= prime
    if x > 1:
        res[x] = 1
    return res

def mod_pow(p, q):
    res = 1
    while q:
        if q & 1:
            res = (res * p) % MOD
        p = (p * p) % MOD
        q //= 2
    return res

def mod_inv(p):
    return mod_pow(p, MOD - 2)

def solve(n, a):
    D = {}
    for i in range(n):
        prime_num_mapping = prime_factorization(a[i])
        for prime, num in prime_num_mapping.items():
            if not prime in D:
                D[prime] = 0
            D[prime] = max(D[prime], num)
    L = 1
    for prime, num in D.items():
        L = (L * mod_pow(prime, num)) % MOD
    res = sum(L * mod_inv(x) for x in a)
    return res % MOD

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

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

tg = 1
for a in A:
    tg = lcm(tg, a)
ans = 0
for a in A:
    ans += tg // a
print(ans%(10**9+7))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
l = 1
for x in a:
    l = l * x // gcd(l, x)
ans = 0
for x in a:
    ans += l // x
print(ans % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
import itertools
import sys
import math
import fractions
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def get_lcm(num):
    return reduce(lambda x,y:(x * y) // fractions.gcd(x, y), num, 1)

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

    lcm = get_lcm(A)
    sum = 0
    for a in A:
      sum += lcm // a
    _, ans = divmod(sum, (10**9+7))

    print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

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


def main():
    from fractions import gcd

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

    # 同じコードがPython3だとギリギリ通るが、PyPy3だとTLE
    for ai in a:
        lcm = lcm * ai // gcd(lcm, ai)

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

    print(ans % mod)


if __name__ == '__main__':
    main()