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:
def gcd(m, n):
    return m if n == 0 else gcd(n, m%n)


def lcm(m, n):
    return m // gcd(m, n) * n


def main():
    MOD = 10**9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    m = 1
    for i in a:
        m = lcm(m, i)
    
    ans = 0
    for i in a:
        b = m // i
        ans += b
    
    print(ans%MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
     
mod = 10 ** 9 + 7
     
def lcm_base(x, y):
    return (x * y) // gcd(x, y)
     
def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
     
    # print('input >>')
N = int(input())
A = list(map(int,(input().split())))
     
lcmn = lcm(A)
    
ans = 0
for i in range(len(A)):
    ans += lcmn // A[i]
     
    # print('-----output-----')
print(int(ans%mod))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
mod=10**9+7

n=int(input())
a=list(map(int,input().split()))
l=a[0]
for i in range(1,n):
  l=lcm(l,a[i])
l%=mod

ans=0
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 gcd

MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
lcm = 1
for i in A:
    lcm = (lcm*i)//gcd(lcm,i)
lcm %= MOD
ans = 0
for i in A:
    ans += lcm*pow(i,MOD-2,MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))


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


MOD = 10 ** 9 + 7
lcm %= MOD
ans = 0
for a in A:
    ans += lcm * pow(a, MOD-2, MOD)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
bbn=1000000007
	
#+++++

def modinv(a,m):
	b=m
	u=1
	v=0
	
	while b > 0:
		t = a //b
		a = a - (t * b)
		a,b = b,a
		u = u - (t * v)
		u,v=v,u
	
	u = u % m
	if u < 0:
		u+=m
	return u

def gcd(a,b):
	while b!= 0:
		a,b=b,a%b
		
	return a
		
def main():
	n = int(input())
	al = list(map(int, input().split()))
	
	#saisyoukoubausuu
	ss=1
	for v in al:
		ss = ss * v //gcd(ss,v)
		#ss %= bbn
	
	ss=ss%bbn
	ret=0
	for v in al:
		ret += ss *modinv(v, bbn)
		ret%=bbn
		
	
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import fractions
import functools
def pin(type=int):
    return map(type,input().split())

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,=pin()
As=list(pin())

L=(lcm_list(As))
B=[L//As[i] for i in range(N)]
print(sum(B) % 1000000007)

Submission status: Accepted

Solution code:
import fractions

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

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

c = b % (1000000007)
print(c)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

N, *A = map(int, open(0).read().split())

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

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

MOD = 10 ** 9 + 7
num = lcm_list(A)
print(sum(num * pow(v, MOD - 2, MOD) for v in A) % 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 lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

n = I()
a = LI()
l = lcm(a)
ans = 0
l %= mod
for i in a:
    ans += l*pow(i,mod-2,mod)
    ans %= mod
print(ans)

Submission status: Accepted

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

a=A[0]
for b in A:
    a = (a * b) // fractions.gcd(a, b)

count=0
for i in A:
    count+=a//i

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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

p = 10**9+7
ans = 0

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

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

lcm = lcm_list(A)

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

print(ans%p)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(a,b):
  if b==0:
    return a
  return gcd(b,a%b)
def glm(a,b):
  #print(a,b,gcd(a,b))
  return a*b//gcd(a,b)
from functools import reduce
def glm_multi(iterable):
  return reduce(glm,iterable,1)
def main():
  n=int(input())
  nums=list(map(int,input().split()))
  g=glm_multi(nums)
  #print(g)
  return sum(g//num for num in nums)%(10**9+7)
print(main())

Submission status: Accepted

Solution code:
#互いに素なa,bについて、a*x+b*y=1の一つの解
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

def mod_inv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

import fractions
mod = (10**9)+ 7
n = int(input())
a = list(map(int, input().split()))
lcm = 1
for i in range(n):
    gcd = fractions.gcd(lcm, a[i])
    lcm *= a[i]
    lcm = lcm // gcd
lcm %= mod
ans = 0
for i in range(n):
    k = mod_inv(a[i], mod)
    ans += lcm * k
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9 + 7
t = A[0]

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)
for e in A:
    t = lcm(e,t)

ans = 0
for e in A:
    ans += t//e

print(ans%MOD)

Submission status: Accepted

Solution code:
mod = 10**9+7
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
A_inv = [pow(a, mod-2, mod) for a in A]
m = A[0]
for a in A[1:]:
    m = m*a//gcd(m, a)
m%=mod
ans = 0
for a in A_inv:
    ans+=m*a
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers)
mod = 10**9 + 7
n = int(input())
As = list(map(int, input().split()))

lcm = lcm_list(As)
b = [lcm//As[i] for i in range(n)]

print(sum(b) % mod)

Submission status: Accepted

Solution code:
from fractions import gcd
 
N=int(input())
a_list = tuple(int(i) for i in input().split())
MOD = 10**9+7

def cal_lcm(a, b):
  return int(a*b//gcd(a,b))

lcm = 1
for i in range(N):
  lcm = cal_lcm(lcm, a_list[i])
  
ans = 0
for i in range(N):
  ans += lcm//a_list[i]
print(ans%MOD)

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  from fractions import gcd
  def lcm(a, b):
      return a * b // gcd(a, b)
  
  N = int(input())
  A = tuple(sorted(list(map(int,input().split()))))
  MOD = 10**9+7
  
  L = 1
  for a in A:
    L = lcm(a,L)
  ans = 0
  for a in A:
    #ans += L//a
    ans += L*pow(a,MOD-2,MOD)
  print(ans%MOD)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd
    a = int(input())
    l = list(map(int,input().split()))



    def lcm(a,b):
        return a*b//gcd(a,b)
    A= 1
    MOD = 10**9+7
    ans = 0
    t = 1
    for i in l:
        t = t* i //gcd(t,i)
    for i in l:
        ans +=t//i
    ans %=MOD
    print(ans)
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

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)

Submission status: Accepted

Solution code:
from fractions import gcd

N = int(input())

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

l = A[0]
for a in A:
  l = (l * a) // gcd(l,a)
num=0
for a in A:
  num += l//a
print(num % (10**9 +7))

Submission status: Accepted

Solution code:
def main():
  MOD=10**9+7
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  ans=0
  for i in range(N):
    ans+=z//A[i]
  print(ans%MOD)
  
if __name__=='__main__':
  main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce


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


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


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

mod = 10 ** 9 + 7

L = lcm_list(a)
ans = 0
for i in a:
    ans += L // i

print(ans % mod)

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):
        if b == 0:
            return a
        return gcd(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:
def GCD(x,y):
    if y==0:
        return x
    return GCD(y,x%y)

def func(x):
    if x <= 1:
        return []
    for i in range(2,int(x**0.5)+1):
        if x%i == 0:
            count = 0
            while x%i==0:
                x //= i
                count += 1
            return [[i,count]]+func(x)
    return [[x,1]]
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
lcm = [0]*(10**6)
for i in A:
    for a,b in func(i):
        lcm[a] = max(lcm[a],b)
L = 1
for i in range(2,10**6):
    L *= pow(i,lcm[i],MOD)
    L %= MOD
ans = 0
for i in A:
    ans += L*pow(i,MOD-2,MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import fractions 
N=int(input())
A=list(map(int,input().split()))
t=A[0]
for i in range(1,N):
  t=(t*A[i])//fractions.gcd(t,A[i])
ans=0
for i in range(N):
  ans+=t//A[i]
print(ans%(10**9+7))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
u = sorted(set(a))
if len(u) == 1:
    print(n)
    exit()
else:
    g = 1
    for x in u:
        g = (g * x) // fractions.gcd(g, x)
    b = 0
    for i in range(n):
        b = b + (g // a[i])
print(b%MOD)

Submission status: Accepted

Solution code:
import fractions
N = int(input())
A = list(map(int, input().split()))
L = 1
for i in range(N):
  g = fractions.gcd(A[i], L)
  L = A[i]*L//g
ans = 0
for i in range(N):
  ans += L//A[i]
print(ans%(7+10**9))

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

mod = 10 ** 9 + 7

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

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

# print('input >>')
N = int(input())
A = list(map(int,(input().split())))

lcmn = lcm(A)

ans = 0
for i in range(len(A)):
    ans += lcmn // A[i]

# print('-----output-----')
print(int(ans%mod))

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

b = input()
a = 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)

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

x = lcm_list(a)
ans = 0

for i in a:
    ans += (x//i)
ans %= 1000000007

print(ans)

Submission status: Accepted

Solution code:
import  fractions
N = int(input())
A = list(map(int,input().split()))
mod =10**9+7
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
  
inv_t = [0]+[1]
for i in range(2,10**6+5):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]
  
k=1
ans=0
for a in A:
  k=lcm(k,a)
  ans+=inv_t[a]%mod
k%=mod

print(ans*k%mod)

Submission status: Accepted

Solution code:
#a,bの最大公約数
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a

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

#べき乗関数powを使った逆元の計算(modinvよりもPythonでは高速、PyPyだと遅い)
def modinv2(a,m):
    return pow(a,m-2,m)


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

if N == 1:
    ans = 1

else:

    A.sort()

    inv = modinv2(A[0],P)
    g = A[0]
    invlist = []
    seki = A[0]%P

    for i in range(1,N):
        inv = (inv+modinv2(A[i],P))%P
        seki = seki*A[i]%P

    g = gcd(A[0],A[1])
    l = A[0]//g*A[1]
    cc = modinv2(g,P)
    for i in range(2,N):
        g = gcd(l,A[i])
        l = l//g*A[i]
        cc = cc*modinv2(g,P)%P

    ans = (inv*seki%P)*cc%P

print(ans)

Submission status: Accepted

Solution code:
# import itertools
# import math
import fractions

MOD = 10 ** 9 + 7


def solve(N, A):
    lcm_ans = A[0]
    for i in range(1, N):
        lcm_ans = lcm_ans * A[i] // fractions.gcd(lcm_ans, A[i])

    ans = 0
    for AA in A:
        ans += lcm_ans // AA

    return ans % MOD


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

# P = []
# S = []
# for i in range(N):
#     pp, ss  = map(int, input().split())
#     P.append(pp)
#     S.append(ss)

print(solve(N, A))

Submission status: Accepted

Solution code:
from fractions import gcd

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

    N = int(input())
    A = input().split()
    AP = set(A)
    num = 1
    for n in AP:
        num = (num*int(n))//gcd(num,int(n))

    t = 0
    for n in A:
        t = (t + num//int(n))
    print(t%mod)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
from fractions import gcd
div = 10**9 + 7

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

    val = 1
    def lcm(a, b):
        ret = gcd(a, b)
        ret = a*b//ret
        return ret

    val = sA[0]
    for a in sA[1:]:
        val = lcm(val, a)

    B = [val//a for a in A]
    sumB = sum(B)
    sumB %= div

    print(sumB)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import math
import functools
import fractions


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

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

    L = functools.reduce(lcm, A)


    C = [L // a for a in A]

    print(sum(C)%div)



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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD=10**9+7
import fractions
N=int(input())
if N==1:
  A=int(input())
  print(1)
  exit()

A=list(map(int, input().split()))
 
def f(a, b):
  return a*b//fractions.gcd(a, b)
 
if N>10:
  A1=A[:N//2]
  A2=A[N//2:]
  
  tmp1=f(A1[0], A1[1])
  n1=len(A1)
  for i in range(2, n1):
    tmp1=f(tmp1, A1[i])
    
  tmp2=f(A2[0], A2[1])
  n2=len(A2)
  for i in range(2, n2):
    tmp2=f(tmp2, A2[i])
    
  tmp=f(tmp1, tmp2)
  
  out1=sum([(tmp1//A1[i]) for i in range(n1)])
  out2=sum([(tmp2//A2[i]) for i in range(n2)])
  out1*=(tmp//tmp1)
  out2*=(tmp//tmp2)
  print((out1+out2)%MOD)
  exit()
  
tmp=f(A[0], A[1])
for i in range(2, N):
  tmp=f(tmp, A[i])
out=0
print(sum([(tmp//A[i])%MOD for i in range(N)])%MOD)

Submission status: Accepted

Solution code:
#E
n=int(input())
a=tuple(map(int,input().split()))
import fractions
lcm=a[0]
b_sum=0
for i in range(1,n):
    lcm=lcm*a[i]//fractions.gcd(lcm,a[i])

num=10**9+7
for i in range(n):
    b_sum+=(lcm//a[i])

print(b_sum%num)

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)


n = int(input())

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

# 最大公倍数
target_num = lcm(*a)

ans = 0
for i in range(n):
    ans += target_num//a[i]
#b = [target_num//num for num in a]

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

Submission status: Accepted

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

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

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)


P = 10**9 + 7
N = 10000
inv_t = [0]+[1]
for i in range(2,10**6+1):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
n=input()
hoge=list(map(int,input().split()))
#hoge=[i for i in range(1,10**4)]
ans=0
l=lcm_list(hoge)%mod
for i in hoge:
    tmp=l*inv_t[i]
    ans+=tmp
    ans%=mod
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

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

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

MOD = 10 ** 9 + 7

MAX = max(p) + 1

inv = [0]+[1]
for i in range(2,MAX + 1):
    inv += [inv[MOD % i] * (MOD - MOD // i) % MOD]

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:
        # LCM is product of primes to their
        # higest powers MODulo M
        ans = (ans * power(i, max_map[i])) % MOD
    return ans

sieve()
c = lcmModuloM(p, n)

ans = 0
for x in p:
    ans = (ans + c * inv[x]) % MOD

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
import sys
def lcm_base(x, y):
    return (x * y) // gcd(x, y)
 
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
def solve(N, A):
    mod = 10 ** 9 + 7
    lcm = lcm_list(A)
    ans = [lcm//a for a in A]
    return sum(ans) % mod
    
 
def main():
    read = sys.stdin.buffer.read
    N,*A = map(int,read().split())
    ans = solve(N, A)
    print(ans)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

def power(a):
    T=[a]
    while 2**(len(T))<mod:
        T.append(T[-1]**2%mod)
    b=bin(mod-2)
    ans=1
    for i in range(len(b)-2):
        if int(b[-i-1])==1:
            ans=ans*T[i]%mod
    return ans   

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
def gcd(a,b):
	if b == 0:
		return a
	return gcd(b, a%b)
LCM = A[0]
for i in range(1, N):
	GCD = gcd(LCM, A[i])
	LCM *= A[i]
	LCM //= GCD
LCM %= mod
ans = 0
for i in range(N):
	t = LCM * pow(A[i], mod-2, mod)
	ans += t
	ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()
MAX = 1000001
  
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: 
          
        # LCM is product of primes to their 
        # higest powers modulo M 
        ans = (ans * power(i, max_map[i])) % mod 
    return ans 
  
# Driver code
sieve()
arr = A
n = len(arr)
tmp = lcmModuloM(arr, n)

ans = 0
for i in range(N):
	ans = (ans + (tmp*power(A[i], mod-2))%mod) % mod
print(ans)

Submission status: Accepted

Solution code:
# prim factorization
def prfct(n):
    l=[]
    if n%2==0:
        m=0
        while n%2==0:
            n//=2
            m+=1
        l.append((2,m))
    p=3
    while p**2<=n:
        if n%p==0:
            m=0
            while n%p==0:
                n//=p
                m+=1
            l.append((p,m))
        p+=2
    if n>1:
        l.append((n,1))
    return l

# modulo:mod

# inverse x^(-1)
def inv(x):
    global mod
    return pow(x,mod-2,mod)

mod = 10 ** 9 + 7

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

mp = {}

pfs = []
for Ai in A:
    pf = prfct(Ai)
    for pr, pw in pf:
        if pr not in mp:
            mp[pr] = pw
        else:
            mp[pr] = max(mp[pr], pw)
    pfs.append(pf)
# print(pfs)
# print(mp)

l = 1
for pr in mp:
    pw = mp[pr]
    l *= pow(pr, pw, mod)
# print(l)

ans = 0

for pf in pfs:
    temp = 1
    for prw in pf:
        pr, pw = prw
        temp = temp * pow(pr, pw, mod) % mod
    temp2 = l * inv(temp) % mod
    ans = (ans + temp2) % mod

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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


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

lcm = A[0]
for i in range(1, N):
    lcm = (lcm * A[i] // (gcd(lcm, A[i])))
ans = 0
lcm %= MOD

for a in A:
    ans = (ans + lcm * modinv(a)) % MOD

print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
ferumaC=300000
fac=[0 for i in range(ferumaC)]
fac[0]=1
ifac=[0 for i in range(ferumaC)]
ifac[0]=1
def mpow(x,n):
    num=1
    while n > 0:
        if n&1:
            num=num*x%mod
        x=x*x%mod
        n=n>>1
    return(num)

for i in range(0,ferumaC-1):
    fac[i+1]=(fac[i]*(i+1))%mod
    ifac[i+1]=ifac[i]*mpow(i+1,mod-2)%mod
def comb(a,b):
    if a==0 and b==0:return(1)
    if a<b or a<0:return(0)
    tmp=ifac[a-b]*ifac[b]%mod
    return(tmp*fac[a]%mod)


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

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

value=A[0]
for i in range(1,N):
    value=lcm(value,A[i])
value%=mod
count=0
for a in A:
    count+=value*(mpow(a,mod-2))%mod
    count%=mod
print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from fractions import gcd
import math
n = int(input())
a = list(map(int, input().split()))
def lcm(a, b):
    return (a * b) // gcd(a, b)
m = 1
for x in a:
    m = (m * x) // gcd(m, x)
# print(m)
MOD = 1000000007
ans = 0
for x in a:
    b = m // x
    ans = ans + b
ans = ans % MOD
print(math.floor(ans))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = int(1e+9 + 7)
L = A[0]
p = mod - 2
X = []
while p != 0:
  X = [p%2] + X[:]
  p //= 2

def inved(x):
  y = 1
  for i in range(len(X)):
    if X[i] == 1:
      y *= x
      y %= mod
    if i != len(X) - 1:
      y *= y
      y %= mod
  return y

for i in range(N-1):
  a, b = L, A[i+1]
  while b != 0:
    a, b = b, a % b
  b = A[i+1] // a
  L = b * L
S = 0
for i in range(N):
  S += (L * inved(A[i])) % mod
  S %= mod
print(S)

Submission status: Accepted

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

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

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

k = a[0]
for ai in a:
    k = lcm(ai, k)

res = 0
for ai in a:
    res += k//ai

print(res % 1000000007)

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)

n = int(input())
a = list(map(int, input().split()))
a_ = []
for i in range(n):
    a_.append(pow(a[i], mod - 2, mod))

num_lcm = lcm(*a) % mod
ans = 0
for i in range(n):
    ans = (ans + num_lcm * a_[i] % mod) % mod

print(ans)

Submission status: Accepted

Solution code:
n = int(input().strip())
A = [int(s) for s in input().strip().split()]
M = 10 ** 9 + 7

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

factors = [0] * 1001
large_factors = set()
for a in A:
    d = 0
    while a % 2 == 0:
        d += 1
        a //= 2
    factors[2] = max(factors[2], d)
    for i in range(3, int(a ** 0.5) + 1, 2):
        d = 0
        while a % i == 0:
            d += 1
            a //= i
        factors[i] = max(factors[i], d)
        if a == 1:
            break
    if a > 1000:
        large_factors.add(a)
    elif a > 1:
        factors[a] = max(factors[a], 1)

m = 1
for k, v in enumerate(factors):
    if v > 0:
        m = (m * pow(k, v, M)) % M
for k in large_factors:
    m = (m * k) % M

result = 0
for a in A:
    result = (result + m * modinv(a, M)) % M
print(result)

Submission status: Accepted

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