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: Wrong Answer

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

import fractions
from functools import reduce

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

def lcm(x, y):
    return (x*y)//gcd(x,y)
    
l = 1
B = 0

for i in range(N):
  l = lcm(l,A[i])
for i in range(N):
  B += l//A[i]
B %= mod

print(B)

Submission status: Wrong Answer

Solution code:
# import math
# import fractions

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

mod = 10 ** 9 + 7


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

# 最小公倍数を素因数分解した形で持つ
l = prime_factorize(a[0])
xs = {}
xs[a[0]] = prime_factorize(a[0])
for i in range(1, n):
  ps = prime_factorize(a[i])
  xs[a[i]] = ps
  for k in ps.keys():
    if k in l:
      l[k] = max(ps[k], l[k])
    else:
      l[k] = ps[k]

# print(l)
# print(xs)

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

answer = 0
for x in a:
  answer = (answer + L * pow(x, mod - 2, mod)) % mod
print(answer)

Submission status: Wrong Answer

Solution code:
# import math
# import fractions

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

mod = 10 ** 9 + 7


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

# 最小公倍数を素因数分解した形で持つ
l = prime_factorize(a[0])
xs = {}
xs[a[0]] = prime_factorize(a[0])
for i in range(1, n):
  ps = prime_factorize(a[i])
  xs[a[i]] = ps
  for k in ps.keys():
    if k in l:
      l[k] = max(ps[k], l[k])
    else:
      l[k] = ps[k]

# print(l)
# print(xs)

answer = 0
for x in a:
  s = 1
  for k in l.keys():
    if k in xs[x]:
      s = (s * (k ** (l[k] - xs[x][k]))) % mod
    else:
      s = (s * (k ** l[k])) % mod
  # print(s)
  answer = (answer + s) % mod
print(answer)

Submission status: Wrong Answer

Solution code:
# import math
# import fractions

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

mod = 10 ** 9 + 7


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

# 最小公倍数を素因数分解した形で持つ
l = prime_factorize(a[0])
xs = {}
xs[a[0]] = prime_factorize(a[0])
for i in range(1, n):
  ps = prime_factorize(a[i])
  xs[a[i]] = ps
  for k in ps.keys():
    if k in l:
      l[k] = max(ps[k], l[k])
    else:
      l[k] = ps[k]

# print(l)
# print(xs)

answer = 0
for x in a:
  s = 1
  for k in l.keys():
    if k in xs[x]:
      s = (s * (k ** (l[k] - xs[x][k]))) % mod
    else:
      s = (s * (k ** l[k])) % mod
  print(s)
  answer = (answer + s) % mod
print(answer)

Submission status: Wrong Answer

Solution code:
# import math
# import fractions

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

mod = 10 ** 9 + 7


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

# 最小公倍数を素因数分解した形で持つ
l = prime_factorize(a[0])
xs = {}
xs[a[0]] = prime_factorize(a[0])
for i in range(1, n):
  ps = prime_factorize(a[i])
  xs[a[i]] = ps
  for k in ps.keys():
    if k in l:
      l[k] = max(ps[k], l[k])
    else:
      l[k] = ps[k]

# print(l)
# print(xs)

answer = 0
for x in a:
  s = 1
  # for k in l.keys():
  #   if k in xs[x]:
  #     s = (s * (k ** (l[k] - xs[x][k]))) % mod
  #   else:
  #     s = (s * (k ** l[k])) % mod
  # print(s)
  answer = (answer + s) % mod
print(answer)

Submission status: Wrong Answer

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

def get_primes(n):
    erat = [False, False] + [True for i in range(n - 1)]
    for i in range(n + 1):
        if erat[i]:
            for j in range(i * 2, n + 1, i):
                erat[j] = False
    return [i for i in range(n + 1) if erat[i]]

primes = get_primes(10000)


def prime_factorization(n):
    d = defaultdict(int)
    def check(k):
        nonlocal d, n
        while n % k == 0:
            d[k] += 1
            n //= k
    for p in primes:
        check(p)
        if n == 1:
            break
    return d

P = [prime_factorization(a) for a in A]

for p in P:
    for k in p.keys():
        cmn[k] = max(cmn[k], p[k])

ans = 0

for p in P:
    t = 1
    for k in cmn.keys():
        t *= pow(k, max(cmn[k] - p[k], 0), 10 ** 9 + 7)

    ans += t
    ans %= 10 ** 9 + 7

print(ans)

Submission status: Wrong Answer

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

def get_primes(n):
    erat = [False, False] + [True for i in range(n - 1)]
    for i in range(n + 1):
        if erat[i]:
            for j in range(i * 2, n + 1, i):
                erat[j] = False
    return [i for i in range(n + 1) if erat[i]]

primes = get_primes(1000)


def prime_factorization(n):
    d = defaultdict(int)
    def check(k):
        nonlocal d, n
        while n % k == 0:
            d[k] += 1
            n //= k
    for p in primes:
        check(p)
        if n == 1:
            break
    return d

P = [prime_factorization(a) for a in A]

for p in P:
    for k in p.keys():
        cmn[k] = max(cmn[k], p[k])

ans = 0

for p in P:
    t = 1
    for k in cmn.keys():
        t *= pow(k, max(cmn[k] - p[k], 0), 10 ** 9 + 7)

    ans += t
    ans %= 10 ** 9 + 7

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions

MOD = 1000000007
N = int(input())
A = list(map(int,input().split()))
#print(math.gcd(5,4))

LCM = A[0]
for i in range(0,N-1,1):
    LCM = LCM*A[i+1]//fractions.gcd(A[i+1],LCM)
B = [0 for i in range(0,N,1)]
for i in range(0,N,1):
    B[i]=LCM//A[i]

ans = 0
for i in range(0,N,1):
    ans = B[i] + ans

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions

MOD = 1000000007
N = int(input())
A = list(map(int,input().split()))
#print(math.gcd(5,4))

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

Submission status: Wrong Answer

Solution code:
import math

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    
    def gen_primes(upper_bound):
        from collections import deque
        target = deque(range(2,upper_bound+1))
        primes = []
        while target[0] <= upper_bound**0.5:
            top = target.popleft()
            primes.append(top)
            tmp = deque()
            for num in target:
                if num % top != 0:
                    tmp.append(num)
            target = tmp
        return primes + list(target)


    N = II()
    A = LMIIS()
    primes = gen_primes(10**4)
    LCM = [0]*len(primes)
    dp = [[0]*len(primes) for _ in range(N)]
    for i in range(N):
        a = A[i]
        for j in range(len(primes)):
            while a % primes[j] == 0:
                a //= primes[j]
                dp[i][j] += 1
            LCM[j] = max(dp[i][j],LCM[j])
    ans = 0
    for i in range(N):
        t = 1
        for j in range(len(primes)):
            t = t*pow(primes[j],LCM[j] - dp[i][j],MOD)%MOD
        ans = (ans + t) % MOD
    print(ans)




    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from fractions import gcd

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

p=10**9+7
n = 10 ** 6  # N は必要分だけ用意する
#fact = [1, 1]  # fact[n] = (n! mod p)
#factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用 逆元
"""
for i in range(2, n + 1):
    #fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    #factinv.append((factinv[-1] * inv[-1]) % p)
#a//gcd(a,b)*b
"""
def lcm(a,b):
    g=gcd(a,b)
    return ((a*b)*pow(g,p-2,p))%p
    #return a//gcd(a,b)*b

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



#print(LCM)
ans=0
LCM%=p
for i in range(N):
    #ans+=(LCM*inv[A[i]])%p
    ans+=(LCM*pow(A[i],p-2,p))%p
    ans%=p
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from fractions import gcd
N=int(input())
A=list(map(int, input().split()))
A=np.array(A)
p=10**9+7
n = 10 ** 6  # N は必要分だけ用意する
#fact = [1, 1]  # fact[n] = (n! mod p)
#factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用 逆元
 
for i in range(2, n + 1):
    #fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    #factinv.append((factinv[-1] * inv[-1]) % p)
#a//gcd(a,b)*b
def lcm(a,b):
    #return ((a*b)*inv[gcd(a,b)])%p
    return a//gcd(a,b)*b

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



#print(LCM)
ans=0
LCM%=p
for i in range(N):
    ans+=(LCM*inv[A[i]])%p
    ans%=p
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from fractions import gcd

N=int(input())
A=list(map(int, input().split()))
A=np.array(A)
p=10**9+7
n = 10 ** 6  # N は必要分だけ用意する
#fact = [1, 1]  # fact[n] = (n! mod p)
#factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用 逆元
 
for i in range(2, n + 1):
    #fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    #factinv.append((factinv[-1] * inv[-1]) % p)
#(a*b)//gcd(a,b)
def lcm(a,b):
    return ((a*b)*inv[gcd(a,b)])%p

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



#print(LCM)
ans=0
for i in range(N):
    ans+=(LCM*inv[A[i]])%p
    ans%=p
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from fractions import gcd

N=int(input())
A=list(map(int, input().split()))
A=np.array(A)
p=10**9+7
n = 10 ** 6  # N は必要分だけ用意する
#fact = [1, 1]  # fact[n] = (n! mod p)
#factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用 逆元
 
for i in range(2, n + 1):
    #fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    #factinv.append((factinv[-1] * inv[-1]) % p)
#(a*b)//gcd(a,b)
def lcm(a,b):
    return ((a*b)*inv[gcd(a,b)])%p

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



print(LCM)
ans=0
for i in range(N):
    ans+=(LCM*inv[A[i]])%p
    ans%=p
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from fractions import gcd

N=int(input())
A=list(map(int, input().split()))
A=np.array(A)
mod=10**9+7
def lcm(a,b):
    return a//gcd(a,b)*b

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



#print(LCM)
print(int((LCM//A).sum())%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
from fractions import gcd

N=int(input())
A=list(map(int, input().split()))
A=np.array(A)
mod=10**9+7
def lcm(a,b):
    return a//gcd(a,b)*b

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



#print(LCM)
print(int((LCM//A).sum()%mod))

Submission status: Wrong Answer

Solution code:
import numpy as np
from fractions import gcd

N=int(input())
A=list(map(int, input().split()))
A=np.array(A)
mod=10**9+7
def lcm(a,b):
    return a//gcd(a,b)*b

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



#print(LCM)
print((LCM//A).sum()%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


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


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


def main():
    n = int(input())
    A = list(map(int, input().split()))
    l = 1
    for a in A:
        l = lcm(l, a)
    c = 0
    for a in A:
        c += l * pow(a, MOD - 2, MOD)
    ans = l * c % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

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

kbs = A[0]
for i in range(1,N):
  kbs = kbs*A[i]*pow(gcd(kbs,A[i]),mod-2,mod)
  kbs %= mod
  
ans = 0
for i in range(N):
  ans += kbs*pow(A[i],mod-2,mod)
  ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from fractions import gcd

    MOD = 10 ** 9 + 7

    N = int(input())

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

    B = [1] * (N + 1)

    for index, a in enumerate(A):
        tmp = gcd(B[index], a)
        B[index + 1] = B[index] * a // tmp

    C = [1] * (N + 1)
    for i in range(N - 1, -1, -1):
        tmp =gcd(C[i + 1], A[i])
        C[i] = C[i + 1] * A[i] // tmp

    return 

    # print (B)
    # print (C)

    ans = 0
    for i in range(N):
        tmp1 = gcd(B[i], C[i + 1])
        tmp2 = B[i] * C[i + 1] // tmp1

        tmp3 = gcd(tmp2, A[i])
        tmp4 = tmp2 * A[i] // tmp3

        ans += (tmp4 // A[i] % MOD)
        ans %= MOD

        # print (ans)

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
        b = m
        u = 1
        v = 0
        while b:
            t = a//b
            a -= t * b
            a, b = b, a
            u -= t * v
            u, v = v, u
        
        u %= m
        if u < 0:
            u += m
        return u

    from fractions import gcd

    MOD = 10 ** 9 + 7

    N = int(input())

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

    B = [1] * (N + 1)

    for index, a in enumerate(A):
        tmp = gcd(B[index], a)
        B[index + 1] = B[index] * a // tmp

    C = [1] * (N + 1)
    for i in range(N - 1, -1, -1):
        tmp =gcd(C[i + 1], A[i])
        C[i] = C[i + 1] * A[i] // tmp

    return

    # print (B)
    # print (C)

    ans = 0
    for i in range(N):
        tmp1 = gcd(B[i], C[i + 1])
        tmp2 = B[i] * C[i + 1] // tmp1

        tmp3 = gcd(tmp2, A[i])
        tmp4 = tmp2 * A[i] // tmp3

        ans += (tmp4 // A[i] % MOD)
        ans %= MOD

        # print (ans)

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4


def main():
    mod = 1000000007                  # 10^9+7
    inf = float('inf')
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():  return int(input())
    def mi():  return map(int, input().split())
    def mi_0(): return map(lambda x: int(x)-1, input().split())
    def lmi(): return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():  return list(input())
    

    class Eratos:
        def __init__(self, num):
            self.table_max = num
            # self.table[i] は i が素数かどうかを示す (bool)
            self.table = [False if i == 0 or i == 1 else True for i in range(num+1)]
            for i in range(2, int(math.sqrt(num)) + 1):
                if self.table[i]:
                    for j in range(i ** 2, num + 1, i):    # i**2 からスタートすることで定数倍高速化できる
                        self.table[j] = False
            # self.table_max 以下の素数を列挙したリスト
            self.prime_numbers = [2] if self.table_max >= 2 else []
            for i in range(3, self.table_max + 1, 2):
                if self.table[i]:
                    self.prime_numbers.append(i)
        
        def is_prime(self, num):
            if num > self.table_max:
                raise ValueError('Eratos.is_prime(): exceed table_max({}). got {}'.format(self.table_max, num))
            return self.table[num]
        
        def prime_factorize(self, num):
            if num > self.table_max:
                raise ValueError('Eratos.prime_factorize(): exceed table_max({}). got {}'.format(self.table_max, num))
            factorized_dict = defaultdict(int)    # 素因数分解の結果を記録する辞書
            candidate_prime_numbers = [i for i in range(2, int(math.sqrt(num)) + 1) if self.is_prime(i)]
            # n について、√n 以下の素数で割り続けると最後には 1 or 素数となる
            # 背理法を考えれば自明 (残された数が √n より上の素数の積であると仮定。これは自明に n を超えるため矛盾)
            for p in candidate_prime_numbers:
                # これ以上調査は無意味
                if num == 1:
                    break
                while num % p == 0:
                    num //= p
                    factorized_dict[p] += 1
            if num != 1:
                factorized_dict[num] = 1
            return factorized_dict

    # import time
    # s = time.time()

    n = ii()
    L = lmi()
    a_max = max(L)
    # O(AlglgA) で前処理
    eratos = Eratos(a_max)
    # print('preprocessed (Eratostenes)')
    # print(time.time() - s)

    # O(n) * O(√A) で LCM を素因数分解した形で保存する
    lcm_dict = eratos.prime_factorize(L[0])
    for i in range(1, n):
        d = eratos.prime_factorize(L[i])
        for k, v in d.items():
            lcm_dict[k] = max(lcm_dict[k], v)
    # print('prime factorized')
    # print(time.time() - s)
    
    # O(√A)
    lcm_mod = 1
    for k, v in lcm_dict.items():
        lcm_mod = (lcm_mod * pow(k, v, mod)) % mod
    
    # O(n)
    ans = 0
    for a in L:
        # a^p-2 ≡ 1/a
        inverse_element = pow(a, mod-2, mod)
        ans = (ans + lcm_mod * inverse_element) % mod

    # print(time.time() - s)
    print(ans)

Submission status: Wrong Answer

Solution code:
import fractions

N = int(input())
A = list(map(int,input().split()))
MOD = 10** 9 + 7
lcm = 1
for a in A:
    lcm = a // fractions.gcd(a,lcm) * lcm

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

Submission status: Wrong Answer

Solution code:
import fractions

N = int(input())
A = list(map(int,input().split()))
MOD = 10** 9
lcm = 1
for a in A:
    lcm = a // fractions.gcd(a,lcm) * lcm

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

print(sum(lcm//a for a in A)%MOD)

Submission status: Wrong Answer

Solution code:
import fractions

N = int(input())
A = list(map(int,input().split()))
MOD = 10** 9
lcm = 1
for a in A:
    lcm = a // fractions.gcd(a,lcm) * lcm

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

print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import fractions

N = int(input())
A = list(map(int,input().split()))
MOD = 10** 9
lcm = 1
for a in A:
    lcm = a // fractions.gcd(a,lcm) * lcm

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

print(ans//MOD)

Submission status: Wrong Answer

Solution code:
import fractions
from functools import reduce
MOD = 10**9 + 7

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

def lcm_base(x, y):
    return (((x * y)%MOD)*pow(fractions.gcd(x, y),MOD-2,MOD))%MOD

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

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

print(int(ans))

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
def factorization(n):
    arr=[]
    tmp=n
    for i in range(2,int(n**0.5)+1):
        if(tmp%i==0):
            cnt=0
            while tmp%i==0:
                cnt+=1
                tmp//=i
            arr.append([i,cnt])
    if(not arr):
        arr.append([1,1])
    if(tmp!=1):
        arr.append([tmp,1])
    return arr
def moddiv(a,m):
    return pow(a,m-2,m)
N=int(input())
A=list(map(int,input().split()))
cnt={}
for i in range(N):
    arr=factorization(A[i])
    for a,b in arr:
        cnt[a]=max(cnt.get(a,0),b)
g=1;res=0
for i in range(2001):
    g=g*(pow(i,cnt.get(i,0),MOD))%MOD
for i in range(N):
    res=(res+(g*moddiv(A[i],MOD))%MOD)%MOD
print(res)

Submission status: Wrong Answer

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
d = {}
mod = 1000000007

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

q = []
for i in range(n):
    p = collections.Counter(prime_factorize(a[i]))
    #print(p)
    q.append(p)
    for x,y in p.items():
            d[x] = max(d.get(x,0),y)  
print(len(d))

ma = 1
for x,y in d.items(): 
    ma *= (x**y)
#print(ma)
            
ans = 0
for i in range(n):
    ans += ma//a[i]
    ans %= mod
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

factors=defaultdict(lambda: 0)

for i in a:
    lfactors=defaultdict(lambda: 0)
    for prime in primes:
        if prime>i:
            lfactors[i]+=1
            break
        while i%prime==0:
            i=i//prime
            lfactors[prime]+=1
    for key,value in zip(lfactors.keys(),lfactors.values()):
        factors[key]=max(factors[key],value)
ans=1
for fact,p in zip(factors.keys(),factors.values()):
    ans=(ans*pow(fact,p))%mod
print(sum([(ans*pow(i,mod-2,mod))%mod for i in a])%mod)

Submission status: Wrong Answer

Solution code:
import fractions

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

n = int(input())
A = list(map(int, input().split(' ')))
lcm_A = 1
for a in A:
  lcm_A = lcm(lcm_A, a)

B_sum = 0
for a in A:
  B_sum += lcm_A // a
  B_sum %= 100000000 + 7

print(B_sum)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

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

import sys
input = sys.stdin.readline


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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
import collections
import copy

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

num = 10**6+1

mod = 10**9+7

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

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

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(num)]
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
exit()
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

for i in range(n):
    com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    for j in keys:
        com_ab_new[j] -= pri_li[i][j]
    kari = 1
    for j in range(kosu):
        kari *= pow(sosu_li[j][0],com_ab_new[sosu_li[j][0]],mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
import collections
import copy

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

num = 10**3

mod = 10**9+7

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

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

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(10**6+1)]
print(sosu_li[10**6])
exit()
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        #com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
exit()
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

for i in range(n):
    com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    for j in keys:
        com_ab_new[j] -= pri_li[i][j]
    kari = 1
    for j in range(kosu):
        kari *= pow(sosu_li[j][0],com_ab_new[sosu_li[j][0]],mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)