Problem:


Score : 500 points

Problem Statement

Given are N positive integers A_1,...,A_N.

Consider positive integers B_1, ..., B_N that satisfy the following condition.

Condition: For any i, j such that 1 \leq i < j \leq N, A_i B_i = A_j B_j holds.

Find the minimum possible value of B_1 + ... + B_N for such B_1,...,B_N.

Since the answer can be enormous, print the sum modulo (10^9 +7).

Constraints

1 \leq N \leq 10^4

1 \leq A_i \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the minimum possible value of B_1 + ... + B_N for B_1,...,B_N that satisfy the condition, modulo (10^9 +7).

Sample Input 1

3
2 3 4

Sample Output 1

13

Let B_1=6, B_2=4, and B_3=3, and the condition will be satisfied.

Sample Input 2

5
12 12 12 12 12

Sample Output 2

5

We can let all B_i be 1.

Sample Input 3

3
1000000 999999 999998

Sample Output 3

996989508

Print the sum modulo (10^9+7).



Sample input:
3
2 3 4


Sample output:
13

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
from fractions import gcd
from functools import reduce
MOD = 10**9 + 7
import math
class Factorizer:
    def __init__(self):
        self.primes_ceil = 5
        self.primes = [2,3]

    def find_primes(self, primes_ceil):
        if primes_ceil <= self.primes_ceil:
            return self.primes

        prev_primes_ceil, self.primes_ceil = self.primes_ceil, primes_ceil
        r, m = prev_primes_ceil//6, prev_primes_ceil%6
        if m <= 1:
            i = r*6 + 1
            mod_flag = True
        else:
            i = r*6 + 5
            mod_flag = False

        while i < self.primes_ceil:
            sieve = True
            for p in self.primes:
                if p*p > i:
                    break
                elif i % p == 0:
                    sieve = False
                    break
            if sieve:
                self.primes.append(i)
            if mod_flag:
                i += 4
                mod_flag = False
            else:
                i += 2
                mod_flag = True

        return self.primes

    def __call__(self, n):
        if (self.primes_ceil-1)**2 < n:
            self.find_primes(int(math.sqrt(n))+1)
        factors = []
        powers = []
        for p in self.primes:
            if p * p > n:
                break
            elif n % p == 0:
                n //= p
                k = 1
                while n % p == 0:
                    n //= p
                    k += 1
                factors.append(p)
                powers.append(k)
        if n > 1:
            factors.append(n)
            powers.append(1)
        return factors, powers

def primes(N):
    P = []
    for i in range(2,N):
        sieve = 1
        for p in P:
            if p*p > i:
                break
            elif i % p == 0:
                sieve = 0
                break
        if sieve == 0:
            continue
        else:
            P.append(i)
    return P

def inv_mod(a, p=MOD):
    p = abs(p)
    a %= p
    stack = []
    p0 = p
    while a > 1:
        d, a, p = p//a, p%a, a
        stack.append(d)
    x, y = 1, 0
    while stack:
        d = stack.pop()
        x, y = y-d*x, x
    return x % p0

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

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

N = int(input())
A = inpl()
M = max(A)
fct = Factorizer()
P = fct.find_primes(M+1)
L = len(P)
pn = dict()
for i in range(L):
    pn[P[i]] = i
factors = [0] * L
for i in range(N):
    f, p = fct(A[i])
    for k in range(len(f)):
        m = pn[f[k]]
        factors[m] = max(factors[m], p[k])
K = 1
for l in range(L):
    K *= pow(P[l],factors[l],MOD)
    K %= MOD
ans = 0
for i in range(N):
    ans += K * inv_mod(A[i])
    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()))
a_lcm=a[-1]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

sum_b=0
for ai in a:
    bi=a_lcm//ai
    sum_b+=bi
print(sum_b%MOD)

Submission status: Accepted

Solution code:
import fractions
N = int(input())
list_number = list(map(int,input().split(" ")))
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)
number_max = lcm_list(list_number)
newlist = list(map(lambda x: number_max // x, list_number))
print(sum(newlist) % 1000000007)

Submission status: Accepted

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

count = 0
for ai in a:
    count += ans//ai
print(count%1000000007)

Submission status: Accepted

Solution code:
#from fractions import gcd
from collections import Counter
mod = 10**9+7
def inv(a):
  return pow(a,mod-2,mod)
def prm(a):
  if a == 1 or a == 4:
    return False
  for i in range(2,int((a)**0.5+1)):
    if a%i == 0:
      return False
  else:
    return True
prime = []
for i in range(1,10**4+1):
  if prm(i):
    prime.append(i)
def sepa(a):
  ans = []
  while a>1:
    for x in prime:
      if a%x == 0:
        ans.append(x)
        a = a//x
        break
      elif x == prime[-1]:
        ans.append(a)
        a = 1
  return Counter(ans)
n = int(input())
a = list(map(int,input().split()))
f = [inv(a[i]) for i in range(n)]
lcm = sepa(1)
for i in range(n):
  x = sepa(a[i])
  for y,z in x.items():
    if z>lcm[y]:
      lcm[y] = z
k = 1
for i,j in lcm.items():
  k = k*(i**j)%mod
print(k*sum(f)%mod)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(2147483647)

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

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

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

    lcm = lcm_list(A)
    S = 0
    for i in range(N):
        S += lcm // A[i]

    print(round(S % (round(1e9) + 7)))

main()

Submission status: Accepted

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

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

g = fractions.gcd(a[0], a[1])
f = a[0]*a[1]//g
ans = a[0]//g+a[1]//g

for i in range(2, n):
    # print(ans, g, f)
    h = fractions.gcd(f, a[i])
    g = a[i] // h
    f = f*a[i]// h
    ans *= g
    ans += f // a[i]
    ans %= mod
print(ans%mod)

Submission status: Accepted

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

Submission status: Accepted

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

#最大公約数
def gcb(a, b):
    while b!=0:
        a,b=b,a%b
    return a

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

lc = 1
for i in range(n):
    lc = lcm(lc, a[i])

ans = 0
for i in range(n):
    ans += lc // a[i]
print(ans % div)

Submission status: Accepted

Solution code:
import sys #追加
sys.setrecursionlimit(500*500)

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

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

LCM = lcm(A)

ans = 0
for a in A:
    ans += LCM//a

ans %= 1000000007

print(ans)

Submission status: Accepted

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

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

ans = my_list[0]

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

ret = 0

for i in range(n):
    ret = ret + (ans // my_list[i])

print(ret % 1000000007)

Submission status: Accepted

Solution code:
import sys

MOD = 1000000007

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

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

N = int(input())
A = list(map(int, sys.stdin.readline().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()]
mod=10**9+7
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
lcm=A[0]

chk=True

for i in range(1,n):
  if lcm%A[i]!=0:
    lcm=lcm*A[i]//gcd(lcm,A[i])
  if lcm>10**50000:
    chk=False
    break

if chk:
  ans=0
  for i in range(n):
    ans=(ans+lcm//A[i])%mod
  print(ans)
else:
  ans=0
  mult=1
  for a in A:
    mult=(mult*a)%mod
  for a in A:
    ans=(ans+mult*pow(a,mod-2,mod))%mod
  print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7 #素数 変える場所 
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

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

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def pow(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return pow(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * pow(n, r-1, mod) % mod

def com(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
n=int(input())
a=list(map(int,input().split()))
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // gcd(ans, a[i])
cnt=ModInt(0)
ans=ModInt(ans)
for i in range(n):
    cnt+=ans/ModInt(a[i])
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
s = list(map(int, input().split()))
def ngcd(a):
    y = a[0]
    for i in range(1, len(a)):
        y = y * a[i] // gcd(y, a[i])
    return y
g = ngcd(s)
ans = 0
for i in range(n):
    ans += g // s[i]
print(ans%1000000007)

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 // int(gcd(a, b))

import functools

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

l = functools.reduce(lcm, A)

ans = sum(l // Ai for Ai in A) % (10 ** 9 + 7)
print(ans)

Submission status: Accepted

Solution code:
#E
mod=10**9+7
def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            a.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        a.append(n)
    return a

N=int(input())
A=list(map(int,input().split()))
Ainv=[]
for i in range(N):
    Ainv.append(pow(A[i],mod-2,mod))
SSS=0
for u in Ainv:
    SSS=(SSS+u)%mod
    
data=[0]*(max(A)+1)
for i in range(N):
    h=prime_factorize(A[i])
    cnt=1
    for i in range(1,len(h)):
        if h[i]==h[i-1]:
            cnt+=1
        else:
            data[h[i-1]]=max(data[h[i-1]],cnt)
            cnt=1
    if h:
        data[h[-1]]=max(data[h[-1]],cnt)
ans=1
for i in range(1,len(data)):
    if data[i]==0:
        continue
    else:
        ans=ans*pow(i,data[i],mod)%mod
print(ans*SSS%mod)

Submission status: Accepted

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

#N = 10000
#A = [i*2+1 for i in range(1,N+1)]

MOD = 10**9+7

sm = 0
for x in A:
  sm += pow(x,MOD-2,MOD)
  sm %= MOD

def gcd(x: int, y: int):
  while(y!=0):
    tmp = x%y
    x = y
    y = tmp
  return x

g = 1
for i in range(N):
  g = g * A[i] // gcd(g, A[i]) #pow(gcd(g, A[i]), MOD-2, MOD)
  #print(g)

an = g * sm % MOD

'''
for x in A:
  #print(g,g//x)
  an += g*pow(x,MOD-2,MOD)
  an %= MOD
  print(g,g//x,an)
'''

print(an)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
def lcm(X,Y):
    x=X
    y=Y
    if y>x:
        x,y=y,x
    while x%y!=0:
        x,y=y,x%y
    return X*Y//y

cnt=0
ans=0
Z=1
for i in range(n):
    Q=lcm(Z,A[i])
    cnt*=Q//Z
    Z=Q
    cnt+=Q//A[i]
print(cnt%mod)

Submission status: Accepted

Solution code:
import math
from fractions import gcd

def lcm(a):
	
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = int(input())

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

saisho = lcm(nums)

B = []

for num in nums:
    B.append(saisho//num)

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

Submission status: Accepted

Solution code:
def gcd(a,b):
    for xx in range(1000001):
        a,b=b,a%b
        if b==0:
            break
    return a

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

P = 10**9 + 7
N = 1000001
inv_t = [0]+[1]
for i in range(2,N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

n=int(input())
A=[int(i) for i in input().split()]

#kyodai=lcm_list(A)
kyodai=A[0]
for i in range(1,n):
    kyodai=lcm_base(kyodai,A[i])

ans=0

for i in range(n):
    ans+=inv_t[A[i]]
    ans=ans%P
ans=ans*kyodai
ans=ans%P

print(ans)

Submission status: Accepted

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

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

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

ans = 0
mod = 10**9+7
l = a[0]
for i in range(1,n):
    l = lcm(l,a[i])

for i in range(n):
    ans += l//a[i]

print(ans%mod)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

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

def modpow(a, n, mod): # a^n mod
    result = 1
    while n > 0:
        if n & 1: result = result * a % mod
        a = a * a % mod
        n >>= 1
    return result

h = reduce(lcm, A)
B = [h * modpow(A[i], MOD-2, MOD) for i in range(N)]
print(sum(B) % MOD)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
from functools import reduce
def input(): return sys.stdin.readline().rstrip()

def main():
    MOD = 10 ** 9 + 7
    n = int(input())
    A = tuple(map(int, input().split()))
    gcd_v = reduce(lcm, A)

    ans = 0
    for i in A:
        ans += gcd_v * pow(i, MOD-2, MOD) % MOD
        ans %= MOD
    print(ans)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]


def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


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


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


p = 10**9+7
N = int(input())
mul = 1
inv_sum = 0
for x in input().split():
    a = int(x)
    inv_sum += mod_inv(a, p)
    inv_sum %= p
    mul = lcm(mul, a)

print(mul * inv_sum % p)

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)

def run():
  N = int(input())
  A_li = list(map(int, input().split()))
  A_lcm = 1
  for A in A_li:
    A_lcm = lcm(A_lcm, A)
  ans = 0
  for A in A_li:
    ans += A_lcm//A
  print(ans%(10**9+7))

if __name__ == '__main__':
  run()

Submission status: Accepted

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

def lcm(a,b):
  return (a*b)//gcd(a,b)
 
n = int(input())
arr = [int(x) for x in input().split()] 
mod=1000000007
lc = arr[0]
for i in range(1, len(arr)): 
  	lc = lcm(lc,arr[i])
ans=0
for i in range(n):
    ans=ans+lc//arr[i]
print(int(ans)%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

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

#最小公倍数(least common multiple)
import fractions
from functools import reduce
def lcm_base(x, y):
    return (x  * y ) // fractions.gcd(x, y)

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

lcm_a = lcm(*a)
b = [lcm_a//i for i in a]
print(sum(b)%(10**9+7))

Submission status: Accepted

Solution code:
from fractions import gcd

M = 10 ** 9 + 7

def xgcd(a, b):
    x0, x1 = 1, 0
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
    return x0 % M

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

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

ans = 0
for a in A:
    m = xgcd(a, M)
    ans = ans + lcm_ * m

print(ans % M)

Submission status: Accepted

Solution code:

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

mod = 10**9 + 7

from collections import defaultdict

B = [defaultdict(int) for i in range(N)]
C = defaultdict(int)

for x in range(N):
    a = A[x]
    for i in range(2,int(a**0.5)+1):
        while a%i==0 and a>0:
            B[x][i]+=1
            a//=i
            #print(a)
            C[i]=max(C[i],B[x][i])
    #print(a)
    if a>1:
        B[x][a]+=1
        C[a] = max(C[a],B[x][a])
#print(B,C)
l = 1
for key in C:
    l*=pow(key,C[key],mod)
    l%=mod

ans = 0
for i in range(N):
    b = l
    for key in B[i]:
        c = pow(key,B[i][key],mod)
        b *= pow(c,mod-2,mod)
    ans+=b
    ans%=mod

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

def lcm_base(x, y):
    return (x * y) // gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

key = lcm_list(l)
ans = 0

for i in l:
  ans += key // i
print(ans % (10** 9 + 7))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#-*- coding: utf-8 -*-
"""
oj dl https://atcoder.jp/contests/abc116/tasks/abc116_d -d test-d
oj test -d test-d -c "python abc116d.py"
oj test -d test-d -c "python abc116d.py" test-d/sample-3.in
"""
from collections import defaultdict
import sys
import math
from datetime import datetime
import re
import math
#sys.setrecursionlimit(314159265)

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


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

def lcm_list(nums):
    if len(nums) == 0:
        return None
    if len(nums) == 1:
        return nums[0]
    if len(nums) == 2:
        lcm(nums[0], nums[1])
    else: # > 2
        a = lcm(nums[0], nums[1])
        for i in range(2, len(nums)):
            A = lcm(a, nums[i])
            a = A
        return a




def sol(S):
    mod = 10**9 + 7
    x = lcm_list(S)
    #print(x)
    T = [ x//s for s in S]
    return sum(T) % mod







do_submit = True
#do_submit = False

def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(map(str, line.split())) for line in lines]
    print(parsed_lines)
    # n = int(parsed_lines[0][0])
    # k = int(parsed_lines[0][1])
    S = parsed_lines[0][0]
    return S


if not do_submit:
    S = input_parse("""
    1905
    """)
    print(sol(S))

    S = input_parse("""
    0112
    """)
    print(sol(S))

    S = input_parse("""
    1700
    """)
    print(sol(S))

    S = input_parse("""
    0000
    """)
    print(sol(S))

    S = input_parse("""
    1001
    """)
    print(sol(S))



else:
    n = int(input())
    S = list(map(int, input().split()))
    #S = input()
    print(sol(S))

    # S = input().strip()
    # print(sol(S))
    # print(lcm(2, 3))
    # print(lcm_list([2, 3, 4]))
    # print(lcm_list([27, 9, 3]))

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n = int(input())
    p = list(map(int,input().split()))
    if n==1:
        print(1)
        exit()
    a = gcd(p[0],p[1])
    lcm = p[0]*p[1]//a
    for i in range(1,n):
        a = gcd(lcm,p[i])
        lcm *= p[i]//a%Mod
    anslist = []
    for i in p:
        anslist.append(lcm//i)
    print(sum(anslist)%Mod)

if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
mod = 10**9+7
import fractions,collections
def lcm(a,b):
    return (a*b)//fractions.gcd(a,b)
N = int(input())
A = list(map(int,input().split()))
C = collections.Counter(A)
k = list(C.keys())
v = list(C.values())
lc = 1
for i in range(len(k)):
    lc = lcm(lc,k[i])
ans = 0
for i in range(len(k)):
    ans += lc//k[i]*v[i]
print(ans%mod)

Submission status: Accepted

Solution code:
import fractions
def mainFunc():
    N = int(input())
    arr = list(map(int, input().split(" ")))
    if N == 1:
        print(1)
        return
    
    lcmOfArr = lcm(arr[0], arr[1])
    for i in range(2, N):
        lcmOfArr = lcm(lcmOfArr, arr[i])
    
    ans = 0

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

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

mainFunc()

Submission status: Accepted

Solution code:
from functools import reduce
import fractions

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

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

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

lcm_A = lcm_list(A)

for item in A:
    B+=(lcm_A//item)

print(B%div)

Submission status: Accepted

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

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

common=lcm(A)
ans=0
for i in range(N):
    ans+=common//A[i]
print(ans%a)

Submission status: Accepted

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

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

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

t = m[0]
for i in m[1:]:
  t = lcm(t,i)

ans=0
for i in m:
  ans += t//i
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
from fractions import gcd

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


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


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

cnt = 0

for a in A:
    b = lcmA // a
    cnt += b

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

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

x = lcm(*A) % mod
ans = sum([x * pow(a, mod-2, mod) for a in A]) % mod
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

n = int(input())
a = list(map(int,input().split()))
g = a[0]
for i in range(n):
  g = lcm(g,a[i])
ans = 0
for i in range(n):
  ans += g // a[i]
print(ans%1000000007)

Submission status: Accepted

Solution code:
import array

n= int(input())

maxN = 1000000
a = list(map(int, input().split()))

def calculate_prime():
    primes = [True] * maxN
    primes[0] = primes[1] = False
    prim = []
    prime_map = dict()
    for i in range(2, maxN):
        if primes[i] == True:
            prime_map[i] = 0
            prim.append(i)
            j = i * i
            while j < maxN:
                primes[j]= False
                j+=i
    return prime_map, array.array('i',prim)

prime_map, prim = calculate_prime()

pppp = []
#print(prim)
for i in list(set(a)):
    if i in prime_map:
        if prime_map[i] < 1:
            pppp.append(i)
            prime_map[i] = 1

    else:
        k = i
        for j in prim:
            if k % j == 0:
                tmp = 0
                while k % j == 0:
                    k = k // j
                    tmp += 1
                if tmp > prime_map[j]:
                    if prime_map[j] == 0:
                        pppp.append(j)
                    prime_map[j] = tmp
            if k in prime_map:
                if prime_map[k] < 1:
                    pppp.append(k)
                    prime_map[k] = 1
                    break
            if k == 1:
                break

lcm = 1
for k in list(set(pppp)):
    lcm = lcm * (k**prime_map[k])

#print(lcm)
result = 0

for i in a:
    result += lcm // i

if result >= 1000000007:
    result = result % 1000000007
print(result)

Submission status: Accepted

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

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)

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read


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


def sieve_of_eratosthenes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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

primes = sieve_of_eratosthenes(max(A) + 1)
dic = {i: 0 for i in primes}

n = len(primes)
p = [0] * n
for i in A:
    tmp = Counter(prime_factorize(i))
    for key, value in tmp.items():
        #print(key, value)
        if dic[key] < value:
            dic[key] = value

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

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

print(answer)

Submission status: Accepted

Solution code:
n = int(input())
L = list(map(int,input().split()))
mod = 10**9+7
from fractions import gcd
import functools
def lcm(x,y):
    return (x * y) // gcd(x, y)
def lcmL(L):
    return functools.reduce(lcm,L)
a = lcmL(L)

sum1 = 0
for i in range(n):
    sum1+=a//L[i]
print(sum1%mod)

Submission status: Accepted

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

#sol = 0
#for i in range(N):
#    sol += lcm_m / a[i]
#print(int(sol)%(10**9+7))
sol=sum([lcm_m//x for x in a])
print(sol%mod)
#print(sol)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split(" ")]
mod=10**9+7

def GCD(a,b):
    if min(a,b)==0:
        return max(a,b)
    else:
        return GCD(min(a,b),max(a,b)%min(a,b))

def LCM(a,b):
    return int(a*b//GCD(a,b))





lcm=1
for a in A:
    lcm=LCM(lcm,a)


retval=0
for a in A:
    retval+=lcm//a

print(int(retval%mod))