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:
# -*- coding: utf-8 -*-
from sys import stdin
# import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]
MOD = 10**9 + 7


def gcd(a, b):
    """ Greatest Common Divisor(最大公約数) """
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    """ Least Common Multiple(最小公倍数) """
    return a * (b // gcd(a, b))


def calc_inverse_element_with_Fermat(a, MOD):
    """
    法をMODとしたときのaの逆元bを返す
    Fermatの小定理を用いる
    a * b = 1 (mod = MOD)

    Attention
    ---------
    MOD は素数の必要がある
    """
    return pow(a, MOD-2, MOD)


N = _i()
a_list = _li()

a_lcm = 1
for a in a_list:
    a_lcm = lcm(a_lcm, a)

a_lcm %= MOD
ans = 0
for a in a_list:
    ans = (ans + a_lcm * calc_inverse_element_with_Fermat(a, MOD)) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
import random
import math
#file = open('test.in', 'r') 
file = sys.stdin

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


n = (int)(input())
v = list(map(int, input().split()))
lcm = 1
for i in range(n):
	lcm = (v[i] * lcm) // gcd(v[i], lcm)
sm = 0
for i in range(n):
	sm = sm + (lcm // v[i])
print(sm % 1000000007)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

mod = 10**9+7
ism = defaultdict(int)
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

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

for i in range( n):
    dl = factorization(a[i])
    for x, y in dl:
        if ism[x] < y:
            ism[x] = y
lcd = 1
for i in ism.keys():
    lcd = (lcd * (i ** ism[i]))%mod
result = 0
for i in range(n):
    result =(result + lcd *extgcd(a[i],mod)[0])%mod
print(result)

Submission status: Accepted

Solution code:
def gcd(a,b):
  if b==0:
    return a
  return gcd(b,a%b)
def lcm(arr):
  ans = 1
  for i in arr:
    ans = (ans*i)//gcd(ans,i)
  return ans
n = int(input())
arr = list(map(int,input().split())) #list(map(int, input().split()))
l = lcm(arr)
ans = 0;
for i in arr:
  ans+= l//i
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
import fractions

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

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

for i in range(1, n):
    r += ans//a[i]

g = r+ans//a[0]
print(g % (1000000000+7))

Submission status: Accepted

Solution code:
#GCD, LCM
def gcd_base(a, b):
    while b!=0:
        a, b = b, a%b
    return a

def lcm(num_list):
    ans = 1
    for i in num_list:
        ans = ans * i // gcd_base(ans, i)
    return ans

n = int(input())
a = list(map(int, input().split()))
l = lcm(a)
mod = 10**9+7
total = 0
for i in a:
    total += l//i
print(total%mod)

Submission status: Accepted

Solution code:
from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7

n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline

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


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()))
a.sort(reverse=1)
ans=0
m=int(10**9+7)
g=1
l=1
'''
for x in a:
  if l%x!=0:
    g=gcd(l,x)
    l=l*x//g
'''
l=lcm(*a)

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

print(ans%m)

Submission status: Accepted

Solution code:
from sys import stdin, stdout
 
ii = lambda: int(stdin.readline())
mi = lambda: map(int, stdin.readline().strip().split())
li = lambda: list(mi())

mod = int(1e9) + 7

def GCD(x, y): 
   while(y): 
       x, y = y, x % y 
   return x 

N = ii()
A = li()
lcm = A[0]
for i in range(1, len(A)):
	lcm = (lcm // GCD(lcm, A[i])) * A[i]

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

ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = defaultdict(int)
ans = 0

for i in range(N):
    tmp = 1
    a = A[i]
    g_tmp = defaultdict(int)
    while tmp <= A[i] ** 0.5:
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            if tmp not in g_tmp:
                g_tmp[tmp] = 1
            else:
                g_tmp[tmp] += 1
        tmp += 1
    if a > 1:
        if a not in g_tmp:
            g_tmp[a] = 1
        else:
            g_tmp[a] += 1

    for j in g_tmp:
        if j not in g:
            g[j] = g_tmp[j]
        else:
            g[j] = max(g[j], g_tmp[j])

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod)
    l %= mod
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = defaultdict(int)

for i in range(N):
    tmp = 1
    a = A[i]
    g_tmp = defaultdict(int)
    while tmp <= A[i] ** 0.5:
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            if tmp not in g_tmp:
                g_tmp[tmp] = 1
            else:
                g_tmp[tmp] += 1
        tmp += 1
    if a > 1:
        if a not in g_tmp:
            g_tmp[a] = 1
        else:
            g_tmp[a] += 1
    for j in g_tmp:
        if j not in g:
            g[j] = g_tmp[j]
        else:
            g[j] = max(g[j], g_tmp[j])

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod)
    l %= mod
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = defaultdict(int)

for i in range(N):
    tmp = 1
    a = A[i]
    g_tmp = defaultdict(int)
    while tmp <= A[i] ** 0.5:
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            if tmp not in g_tmp:
                g_tmp[tmp] = 1
            else:
                g_tmp[tmp] += 1
        tmp += 1
    for j in g_tmp:
        if j not in g:
            g[j] = g_tmp[j]
        else:
            g[j] = max(g[j], g_tmp[j])
    if a > 1:
        if a not in g:
            g[a] = 1

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod)
    l %= mod
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = defaultdict(int)

for i in range(N):
    tmp = 1
    a = A[i]
    g_tmp = defaultdict(int)
    while tmp <= A[i] ** 0.5:
        cnt = 0
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            if tmp not in g_tmp:
                g_tmp[tmp] = 1
            else:
                g_tmp[tmp] += 1
        tmp += 1
    for j in g_tmp:
        g[j] = max(g[j], g_tmp[j])
    if a > 1:
        if a not in g:
            g[a] = 1

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod)
    l %= mod
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

Submission status: Accepted

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

pre = a[0]
for v in a[1:]:
    pre = pre * v // gcd(pre, v)
# print(pre)
# print([pre // v for v in a])
print(sum(pre // v for v in a) % M)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = defaultdict(int)

for i in range(N):
    tmp = 1
    a = A[i]
    g_tmp = defaultdict(int)
    while tmp <= A[i] ** 0.5:
        cnt = 0
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            cnt += 1
        if cnt > 0:
            g_tmp[tmp] = max(g_tmp[tmp], cnt)
        tmp += 1
    for j in g_tmp:
        g[j] = max(g[j], g_tmp[j])
    if a > 1:
        if a not in g:
            g[a] = 1

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod)
    l %= mod
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = defaultdict(int)

for i in range(N):
    tmp = 1
    a = A[i]
    while tmp <= A[i] ** 0.5:
        cnt = 0
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            cnt += 1
        if cnt > 0:
            g[tmp] = max(g[tmp], cnt)
        tmp += 1
    if a > 1:
        if a not in g:
            g[a] = 1

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod)
    l %= mod
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

n = int(input())
lst = list(map(int, input().split()))
ans = 0
mod = 10**9+7
lcd = reduce(lambda x,y : x*y//gcd(x,y), lst)
for i in lst:
    ans += lcd//i

print(ans%mod)

Submission status: Accepted

Solution code:
import fractions

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

N = int(input())
A = [int(i) for i in input().split()]
mod = 10**9+7
ll = A[0]
for i in A:
    ll = lcm(ll, i)
ans = 0
for i in A:
    ans += ll // i
print(int(ans%mod))

Submission status: Accepted

Solution code:
"""
the condition is straightforward.
each element of A and B must multiply to the same value.
to minimise the total of B, simply make that value as small
as possible (since A is fixed).

lcm(2, 3, 4) = 12
therefore B is
12/2, 12/3, 12/4
and the sum of B is
12/2 + 12/3 + 12/4

lcd of a list is loop: lcd(partial, new_value)
lcd(a, b) = ab / gcd(a, b)
"""

from fractions import gcd


def lcm(list_ints):
    lcm_ongoing = 1
    for val in list_ints:
        lcm_ongoing = val*lcm_ongoing//gcd(val, lcm_ongoing)
    return lcm_ongoing


def flatten(N, A):
    # get lcm
    lcm_of_A = lcm(A)
    # get sum of lcm/values
    ans = sum(lcm_of_A//value for value in A)
    modulo_value = int(int(1e9)+7)
    return ans % modulo_value


if __name__ == "__main__":
    test1 = \
"""3
2 3 4"""
    test2 = \
"""5
12 12 12 12 12"""
    test3 = \
"""3
1000000 999999 999998"""
    test = test3
    # N = int(test.split("\n")[0])
    # A = list(map(int, test.split("\n")[1].split()))
    N = int(input())
    A = list(map(int, input().split()))
    print(flatten(N, A))

Submission status: Accepted

Solution code:
"""
the condition is straightforward.
each element of A and B must multiply to the same value.
to minimise the total of B, simply make that value as small
as possible (since A is fixed).

lcm(2, 3, 4) = 12
therefore B is
12/2, 12/3, 12/4
and the sum of B is
12/2 + 12/3 + 12/4

lcd of a list is loop: lcd(partial, new_value)
lcd(a, b) = ab / gcd(a, b)
"""

from fractions import gcd


def lcm(list_ints):
    lcm_ongoing = 1
    for val in list_ints:
        lcm_ongoing = val*lcm_ongoing//gcd(val, lcm_ongoing)
    return lcm_ongoing


def flatten(N, A):
    # get lcm
    lcm_of_A = lcm(A)
    # get sum of lcm/values
    ans = sum(lcm_of_A//value for value in A)
    modulo_value = int(int(10e8)+7)
    return ans % modulo_value


if __name__ == "__main__":
    test1 = \
"""3
2 3 4"""
    test2 = \
"""5
12 12 12 12 12"""
    test3 = \
"""3
1000000 999999 999998"""
    test = test3
    # N = int(test.split("\n")[0])
    # A = list(map(int, test.split("\n")[1].split()))
    N = int(input())
    A = list(map(int, input().split()))
    print(flatten(N, A))

Submission status: Accepted

Solution code:
# abc 152 e
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

MOD = 10 ** 9 + 7

N = int(readline().strip())
A = list(map(int, readline().split()))

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

lcm_ = 1  # 倍数を出したいので初期値は1
for i in range(N):
    lcm_ = lcm(lcm_, A[i])

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

print(ans % MOD)

Submission status: Accepted

Solution code:
import fractions


def lcm_list(numbers):
    ans = numbers[0]
    for number in numbers[1:]:
        ans = (((number * ans)) //(fractions.gcd(number, ans)))
    return ans


MOD = 10 ** 9 + 7
N = input()
i = 0
arrs = list(map(int, input().split()))
lcms = lcm_list(arrs)
result = 0
for arr in arrs:
    result += (lcms // arr)
result = result % MOD
ans = str(result).replace('.0', '')
print(ans)

Submission status: Accepted

Solution code:

from fractions import gcd
MOD = 10**9+7
N = input()
i = 0
arrs = list(map(int, input().split()))
result = 0
lcms = 1
for number in arrs:
    lcms = (((number * lcms)) //(gcd(number, lcms)))
for arr in arrs:
    result += (lcms//arr)
result = result%MOD
ans = str(result).replace('.0','')
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

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 main():
    n = inp()
    a = inpl()
    LCM = a[0]
    for e in a:
        LCM = lcm(LCM,e)
    sumation = 0
    for e in a:
        sumation = (sumation + pow(e,mod-2,mod))%mod
    print((LCM%mod)*sumation%mod)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))


# 素因数分解
def prime_factorization(n):
    fact=[]
    fact=defaultdict(int)
    for i in range(2, int(sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            # fact.append(i)
            fact[i]+=1
            # print(n,i)
    if n!=1:
        fact[n]+=1
    return fact

class Eratosthenes:
    def __init__(self, N:int):
        self.data = [-1]*(N+1) ##data[i]:=iの素因数が一つ入ってるリスト
        for i in range(2,int(sqrt(N)+1)):
            if self.data[i]!=-1:
                continue
            j = 2*i
            while j<=N:
                self.data[j] = i
                j += i

    def prime_factorization(self,n):
        res = defaultdict(int)
        while self.data[n] != -1:
            prime = self.data[n]
            res[prime] += 1
            n //= prime
        if n!=1:
            res[n] += 1
        return res

def main():
    N=I()
    A=LI()
    A_max = max(A)
    Eratos = Eratosthenes(A_max)

    lcm = defaultdict(int)
    for a in A:
        p = Eratos.prime_factorization(a)
        for k in p.keys():
            lcm[k] = max(p[k],lcm[k])
    
    L = ModInt(1)
    for l,v in lcm.items():
        L *= l**v
    ans = ModInt(0)
    for a in A:
        ans += L/a
    print(ans)
    
if __name__ == '__main__':
    main()

# #
# # 　　  ⋀_⋀　 
# #　　  (･ω･)  
# # .／ Ｕ ∽ Ｕ＼
# #  │＊　合　＊│
# #  │＊　格　＊│ 
# #  │＊　祈　＊│ 
# #  │＊　願　＊│ 
# #  │＊　　　＊│ 
# #      ￣
# #
# import sys
# sys.setrecursionlimit(10**6)
# input=sys.stdin.readline
# # from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
# # from heapq import heappop, heappush, heappushpop
# # from collections import Counter,defaultdict,deque
# # from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
# # from bisect import bisect_left,bisect_right
# # from copy import deepcopy
# from fractions import gcd
# inf=float('inf')
# mod = 10**9+7
# def pprint(*A): 
#     for a in A:     print(*a,sep='\n')
# def INT_(n): return int(n)-1
# def MI(): return map(int,input().split())
# def MF(): return map(float, input().split())
# def MI_(): return map(INT_,input().split())
# def LI(): return list(MI())
# def LI_(): return [int(x) - 1 for x in input().split()]
# def LF(): return list(MF())
# def LIN(n:int): return [I() for _ in range(n)]
# def LLIN(n: int): return [LI() for _ in range(n)]
# def LLIN_(n: int): return [LI_() for _ in range(n)]
# def LLI(): return [list(map(int, l.split() )) for l in input()]
# def I(): return int(input())
# def F(): return float(input())
# def ST(): return input().replace('\n', '')
# #mint
# class ModInt:
#     def __init__(self, x):
#         self.x = x % mod
    
#     def __str__(self):
#         return str(self.x)
    
#     __repr__ = __str__

#     def __add__(self, other):
#         if isinstance(other, ModInt):
#             return ModInt(self.x + other.x)
#         else:
#             return ModInt(self.x + other)

#     __radd__ = __add__
        
#     def __sub__(self, other):
#         if isinstance(other, ModInt):
#             return ModInt(self.x - other.x)
#         else:
#             return ModInt(self.x - other)

#     def __rsub__(self, other):
#         if isinstance(other, ModInt):
#             return ModInt(other.x - self.x)
#         else:
#             return ModInt(other - self.x)

#     def __mul__(self, other):
#         if isinstance(other, ModInt):
#             return ModInt(self.x * other.x)
#         else:
#             return ModInt(self.x * other)

#     __rmul__ = __mul__

#     def __truediv__(self, other):
#         if isinstance(other, ModInt):
#             return ModInt(self.x * pow(other.x, mod-2,mod))
#         else:
#             return ModInt(self.x * pow(other, mod - 2, mod))
            
#     def __rtruediv(self, other):
#         if isinstance(other, self):
#             return ModInt(other * pow(self.x, mod - 2, mod))
#         else:
#             return ModInt(other.x * pow(self.x, mod - 2, mod))
            

#     def __pow__(self, other):
#         if isinstance(other, ModInt):
#             return ModInt(pow(self.x, other.x, mod))
#         else:
#             return ModInt(pow(self.x, other, mod))
            

#     def __rpow__(self, other):
#         if isinstance(other, ModInt):
#             return ModInt(pow(other.x, self.x, mod))
#         else:
#             return ModInt(pow(other, self.x, mod))

# def main():
#     N=I()
#     A=LI()
#     l = 1
#     for a in A:
#         l *= a//gcd(l,a)
#     ans = 0
#     l = ModInt(l)
#     for a in A:
#         ans += l/a
#     print(ans)
# if __name__ == '__main__':
#     main()

Submission status: Accepted

Solution code:
import fractions

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

lcm = 1
for a in A:
    lcm *= (a // fractions.gcd(lcm, a)) % (10**9 + 7)

for i in range(len(A)):
    A[i] = lcm // A[i]

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

Submission status: Accepted

Solution code:
import math
import fractions
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 union_lcm(lists):
    if len(lists)==1:
        return lists[0]
    elif len(lists)>1:
        num=lists[0]
        for i in range(1,len(lists)):
            num=num*lists[i]//fractions.gcd(num,lists[i])
        return num


#最大公約数
def union_gcd(lists):
    if len(lists)==1:
        return lists[0]
    elif len(lists)>1:
        num=lists[0]
        for i in range(1,len(lists)):
            num=fractions.gcd(num,lists[i])
        return num
mod=10**9+7   
n=int(input())
lists=list(map(int,input().split()))
a=union_lcm(lists)
c=0
a=a%mod

for i in range(n):
    c+=a*modinv(lists[i],mod)
   
print(c%mod)

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
 
ans = 0
MOD = 1000000007
 
LCM = A[0]
for i in range(1, N):
    LCM *= A[i] // gcd(LCM, A[i])
    
for a in A:
  ans += LCM // a
  
print(ans%MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
n = input()    
m = n.split()
p = [int(i) for i in m]
a = 0
b = 1
import fractions
for i in p:
    c = fractions.gcd(i, b)
    a = (a * i // c + b // c) % 1000000007
    b = b * i // c
 

print(a)

Submission status: Accepted

Solution code:
from fractions import gcd
import sys

if True:
    N, *A = map(int, sys.stdin.read().split())
else:
    N = int(input())
    A = list(map(int, input().split()))

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

MOD = int(1e9) + 7
sum_ = 0
for v in A:
    sum_ += a // v

print(sum_ % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

from collections import defaultdict

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

def prime_factors(d,N): #素因数 1を含まないことに注意
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            c = 0
            while tmp%i == 0:
                tmp //= i
                c += 1
            if d[i] < c:
                d[i] = c
    if tmp != 1:
        if d[tmp] == 0:
            d[tmp] = 1

Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    # d = defaultdict( int)
    # for a in A:
    #     prime_factors(d, a)
    s = 1
    for a in A:
        s = s*a//gcd(s,a)
    # for key, value in d.items():
    #     s *= pow( key, value)
    ans = 0
    for a in A:
        ans += s*pow(a,Q-2,Q)
    print(ans%Q)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import defaultdict

def prime_factors(d,N): #素因数 1を含まないことに注意
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            c = 0
            while tmp%i == 0:
                tmp //= i
                c += 1
            if d[i] < c:
                d[i] = c
    if tmp != 1:
        if d[tmp] == 0:
            d[tmp] = 1

Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    d = defaultdict( int)
    for a in A:
        prime_factors(d, a)
    s = 1

    for key, value in d.items():
        s *= pow( key, value)
    ans = 0
    for a in A:
        ans += s*pow(a,Q-2,Q)
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import defaultdict

def prime_factors(d,N): #素因数 1を含まないことに注意
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            c = 0
            while tmp%i == 0:
                tmp //= i
                c += 1
            if d[i] < c:
                d[i] = c
    if tmp != 1:
        if d[tmp] == 0:
            d[tmp] = 1

Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    d = defaultdict( int)
    for a in A:
        prime_factors(d, a)
    s = 1

    for key, value in d.items():
        s *= pow( key, value)
    ans = 0
    for a in A:
        ans += s*pow(a,Q-2,Q)
    print(ans%Q)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
#input
N = int(input())
A = list(map(int, input().split()))
 
#output
import fractions, functools
 
def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)
 
lcm = lcm_list(A)
 
answer = 0
for i in range(N):
    answer += lcm//A[i]
 
print(answer % (10**9 + 7))

Submission status: Accepted

Solution code:
# E
from fractions import gcd

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

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

mod = 10**9+7

ans = 0
for i in A:
    ans += value // i

print(ans%mod)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
import fractions
from functools import reduce

n=int(input())
c = list(map(int, input().split()))
mod=pow(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)

v=lcm(*c)%mod
ans=0

for i in range(n):
    ans += v * pow(c[i],mod-2,mod)
    ans%=mod

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())
l=list(map(int,input().split()))
a=lcm_list(l)
ans_l = []
for i in l:
    ans_l.append(a//i)
print(int(sum(ans_l)%(10**9+7)))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.read


# 最小素因数を求める（エラトステネスの篩の亜種？）
def min_factor(n):
    sieve = list(range(n + 1))
    sieve[2::2] = [2] * (n // 2)
    for i in range(3, int(n ** 0.5) + 2, 2):
        if sieve[i] == i:
            sieve[i * i::2 * i] = [i] * ((n - i * i - 1) // (2 * i) + 1)
    return sieve


# 素因数分解
def prime_factorize(n):
    a = defaultdict(int)
    while n != 1:
        b = table[n]
        a[b] += 1
        n //= b
    return a


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

table = min_factor(10 ** 6)
dic = defaultdict(int)

for i in A:
    for key, value in prime_factorize(i).items():
        dic[key] = max(dic[key], value)


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

answer = sum(lcm * pow(i, mod - 2, mod) for i in A) % mod
print(answer)