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:
# -*- coding: utf-8 -*-
#グローバル変数
pn_list = {2:0,3:0}

def next_pn():
    npn = sorted(list(pn_list.keys()))[-1] + 2
    pn_flg = 0
    while pn_flg == 0:
        for i in sorted(list(pn_list.keys())):
            if npn % i == 0:
                break
            if (i ** 2) > npn:
                pn_flg = 1
                break
        if pn_flg == 1:
            break # 素数が見つかったらbreak
        else:
            npn += 2
    pn_list[npn] = 0
    return npn

def check_a(n,a):
    res = "ok"
    for i in range(n):
        if a[i] > 1:
            res = "notyet"
    return res

# 整数の入力
n = int(input())
s = input()
#n = 127
#s ="475616	351822	232032	171944	990135	5931	194170	588306	135611	592952	173857	498063	871165	294451	850920	897743	501068	63231	342963	177184	129959	757280	767233	515970	739786	464954	177546	35241	231863	28242	669585	934828	707084	616363	476691	310154	343148	525292	167120	7105	290239	23255	280490	998113	47140	798570	599634	907705	613595	493232	306263	142531	585290	670863	965713	585296	878670	170122	270480	449693	986267	75647	534966	757279	587178	915588	838743	276417	173896	339891	33794	853568	852882	166517	841798	606048	173055	77131	497064	283034	134261	420083	728780	666793	761299	78409	616084	244059	478976	909963	338951	182412	283681	768615	294288	849838	898261	985237	806298	835042	251645	113001	814583	419061	447249	729345	530032	172115	443571	775150	543644	483059	197601	386031	878770	278846	653861	488448	235336	369875	980765	232797	758998	680944	972478	84978	158345"
#n = 10
#s = "475616	351822	232032	171944	990135	5931	194170	588306	135611	592952"
#n = 3
#s = "1000000 999999 999998"
a = [int(x) for x in s.split()]
aa = [int(x) for x in s.split()]

#素数作成
sqr_max_a = int((1.0 * 10**6) ** 0.5) + 1
#sqr_max_a = int(1.0 * 10**6)
pn = 0
while pn < sqr_max_a:
    pn = next_pn()

# a を素因数分解する
pn_lcm = []
for i in pn_list.keys():
    wareta = 1
    while wareta == 1:
        wareta = 0
        for j in range(len(a)):
            if a[j] % i == 0:
                a[j] = a[j] / i
                wareta = 1
        if wareta == 1:
            pn_list[i] += 1
            pn_lcm.append(i)
    if check_a(n,a) == "ok":
        break

for i in a:
    if i > 1:
        pn_lcm.append(i)

min_bsum = int(0)

for i in aa:
    b = int(1)
    aaa = int(i)
    for j in pn_lcm:
        if aaa % j == 0:
            aaa = aaa / j
        else:
            b = (b * j) % (10**9+7)
    min_bsum = int((min_bsum + int(b)) % (10**9+7))

print(min_bsum)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
#グローバル変数
pn_list = {2:0,3:0}

def next_pn():
    npn = list(pn_list.keys())[-1] + 2
    pn_flg = 0
    while pn_flg == 0:
        for i in pn_list.keys():
            if npn % i > 0:
                pn_flg += 1
        if pn_flg == len(pn_list.keys()):
            break # 素数が見つかったらbreak
        else:
            npn += 2
            pn_flg = 0
    pn_list[npn] = 0
    return npn

def check_a(n,a):
    res = "ok"
    for i in range(n):
        if a[i] > 1:
            res = "notyet"
    return res

# 整数の入力
#n = int(input())
#s = input()
n = 3
s ="1000000 999999 999998"
a = [int(x) for x in s.split()]
aa = [int(x) for x in s.split()]

#素数作成
sqr_max_a = int((1.0 * 10**6) ** 0.5) + 1
pn = 0
while pn < sqr_max_a:
    pn = next_pn()

# a を素因数分解する
for i in pn_list.keys():
    wareta = 1
    while wareta == 1:
        wareta = 0
        for j in range(len(a)):
            if a[j] % i == 0:
                a[j] = a[j] / i
                wareta = 1
        if wareta == 1:
            pn_list[i] += 1
    if check_a(n,a) == "ok":
        break

lcm = 1.0
for i in pn_list.keys():
    lcm = lcm * (i ** pn_list[i])

min_bsum = 0.0
for i in aa:
    min_bsum += lcm / i

print(int(min_bsum % (10**9+7)))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
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
if N == 1:
    print(1)
else:
    data = A[0] * A[1] // gcd(A[0] , A[1])
    for i in range(2, N):
        data = data * A[i] // gcd(data, A[i])
    count= 0
    for i in range(N):
        count += data // A[i]
        count % mod
    print(count)

Submission status: Wrong Answer

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

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

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

lcm_A = lcm_list(A)
B = [None]*N
for i in range(N):
    B[i] = lcm_A//A[i]
print(1)
"""
print(int(sum(B)%(10**9+7)))
"""

Submission status: Wrong Answer

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

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

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

lcm_A = lcm_list(A)
print(1)
"""
B = [None]*N
for i in range(N):
    B[i] = lcm_A/A[i]

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import fractions
#from functools import reduce
import functools

MOD = 10**9+7


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

    x = 1
    ans = 0
    # for a in A:
    #     tmp = gcd(x, a)
    #     # ans += (i) * A[i] // tmp + A[i] * x //tmp  
    #     x = (x * a) // tmp
    x = functools.reduce(fractions.gcd, A, 1)
        
    b = 0
    A = np.array(A)
    # for a in A:
    #     b += x // a
    b = np.sum(x//A, axis=0)
    print(b%MOD)
main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd

P = 10**9 + 7
n = int(input())

def lcm(p,q):
    return p*q//gcd(p,q)

a = list(map(int, input().split()))
x = a[0]
for i in range(1,n):
    x = lcm(x,a[i])
ans = 0
for i in range(n):
    ans += x//a[i]
    if i%5==0:
        ans = ans%P
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
l=list(map(int,input().split()))
C=10**9+7
def gc(a,b):
  ma=max(a,b)
  mi=min(a,b)
  while mi>0:
    nex_ma=mi
    mi=ma%mi
    ma=nex_ma
  return ma
def lc(a,b):
  g=gc(a,b)
  return a*b//g
lca=l[0]
for i in range(1,N):
  lca=lc(lca,l[i])
ans=0
for i in range(N):
  ans+=(l[i]//lca)
  ans=ans%C
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from fractions import gcd

MOD = 10**9+7


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

    x = 1
    ans = 0
    for a in A:
        tmp = gcd(x, a)
        # ans += (i) * A[i] // tmp + A[i] * x //tmp  
        x = (x * a) // tmp
    
    b = 0
    A = np.array(A)
    # for a in A:
    #     b += x // a
    b = np.sum(x//a)
        
    print(b%MOD)
main()

Submission status: Wrong Answer

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

from collections import defaultdict

MOD = 10**9 + 7

primes = defaultdict(int)

for a in A:
    p = 2
    while p * p <= a:
        if a % p == 0:
            cnt = 0
            while a % p == 0:
                cnt += 1
                a //= p
            primes[p] = max(primes[p], cnt)
        p += 1
    if a != 1:
        primes[a] = 1

lcm = 1
for p in primes:
    lcm *= pow(p, primes[p], MOD) % MOD

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

print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

def lcm(a,b):
    return a*b*pow(gcd(a,b),mod-2,mod) % mod

n = I()
a = LI()
l = 1
for i in range(n):
    l = lcm(l,a[i])

ans = 0
for i in range(n):
    ans += l *pow(a[i],mod-2,mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

def lcm(a,b):
    return a*b*pow(gcd(a,b),mod-2,mod)

n = I()
a = LI()
l = 1
for i in range(n):
    l = lcm(l,a[i])

ans = 0
for i in range(n):
    ans += l *pow(a[i],mod-2,mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

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

N  = int(input())
lst_A = np.array(list(map(int, input().split())))
inv_A = 1/lst_A
mod = 10**9+7
lcm_A = lcm(lst_A)
print(int(np.sum(inv_A*lcm_A)) % mod)

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
        
def lcm(a,b):
    return a*b//gcd(a,b)
    
N = int(input())
A = list(map(int, input().split()))

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

mod = 10**9+7
print(ans & mod)

Submission status: Wrong Answer

Solution code:
from fractions import*;n,*a=map(int,open(0).read().split());l=1;p=[l*i//gcd(l,i)for i in a][-1];print(sum(p//i for i in a)%(10**9+7))

Submission status: Wrong Answer

Solution code:
# エラトステネスを素因数分解とlcm


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

def inverse(a): #aに対し、a**(mod-2)、つまり逆元を返す
  T=[a]
  while 2**(len(T))<mod: #a**1,a**2.a**4,a**8,...を計算しておく
      T.append(T[-1]**2%mod)
  b=bin(mod-2) #mod-2を2進数表記にする
  ans=1
  for i in range(len(b)-2):
      if int(b[-i-1])==1:
          ans=ans*T[i]%mod
  return ans

def eratosthenes(n): #エラストテネスの篩(最大の素因数を格納した配列)
    A = [0] * n
    A[0], A[1] = -1, -1
    for i in range(2, n):
      if A[i] == 0:
        j = i
        while j < n:
          A[j] = i
          j += i
    return A

E = eratosthenes(10**6+5)
l = {}

for a in A:
  now = a
  f = [] #素因数格納配列

  while now > 1:
    f.append(E[now])
    now //= E[now]

  chk = 0 

  for p in f:
    if chk == p: #同じ素因数が複数あるときに飛ばす
      continue
    chk = p
    if p in l.keys(): #辞書に素因数がある場合、個数の多いほう
      l[p] = max(l[p], f.count(p))
    else: #辞書にない場合新規追加
      l[p] = f.count(p)
 
lcm = 1
for k in l:
  for i in range(l[k]):
      lcm= lcm * k % mod

s = 0
for i in range(N):
    s += lcm // A[i] % mod
    s %= mod
print(s)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = []
        for i in range(2, int(math.sqrt(m)) + 1):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False
        self.ds_memo = {}
        self.ds_memo[1] = set([1])

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d


def main():
    n = I()
    a = LI()
    pr = Prime(10**7)
    ad = collections.defaultdict(int)
    da = []
    for c in a:
        d = pr.division(c)
        for k,v in d.items():
            if ad[k] < v:
                ad[k] = v
        da.append(d)
    r = 0
    for d in da:
        t = 1
        for k,v in ad.items():
            t *= pow(k, v - d[k], mod)
            t %= mod
        r += t
        r %= mod

    return r


print(main())

Submission status: Wrong Answer

Solution code:
import math

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

max_primes = {}
for n in range(N):
  p = A[n]
  for i in range(2, int(math.sqrt(p)) + 1):
    c = 0
    while p % i == 0:
      c += 1
      p = p // i
    if c > 0:
      if i in max_primes:
        max_primes[i] = max(max_primes[i], c)
      else:
        max_primes[i] = c
  if p != 1:
    max_primes[p] = 1
    
muls = 1
for k, v in max_primes.items():
  muls = muls * k **v 

total = 0
for n in range(N):
  p = A[n]
  total += muls // p

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

Submission status: Wrong Answer

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)

from collections import defaultdict

N = int(readline().rstrip())
al = map(int, readline().strip())

# 最大公約数
from fractions import gcd

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

lcm_ = 0
for a in al:
    if lcm_ == 0:
        lcm_ = a
    lcm_ = lcm(a, lcm_)

prime = 10 ** 9 + 7
bl = []
for a in al:
    b = lcm_ / a / prime
    bl.append(b)

answer = sum(bl)
print(answer)

Submission status: Wrong Answer

Solution code:
import math
import decimal
import queue
import bisect
import heapq
import time
import itertools

mod = int(1e9+7)

class Library():
    @staticmethod
    def Swap(a,b):
        return [b,a]

    @staticmethod
    def myRound(a,dig=0): # 四捨五入
        p = 10 ** dig
        return (a * p * 2 + 1) // 2 / p

    @staticmethod
    def Roundup(a,dig=0): # 切り上げ
        if a < 0:
            return int(a)
        else:
            return int(a + 0.9)

    @staticmethod
    def Gcd(a,b): #最大公約数
        if (a<b):
            a,b = Library.Swap(a,b)
        if (b==0):
            return a
        else:
            return Library.Gcd(b,a%b)

    @staticmethod
    def Lcm(a,b): #最小公倍数
        return a//Library.Gcd(a,b)*b

    @staticmethod
    def Divisors(a): # 約数列挙
        divisors = []
        for i in range(1,int(a**0.5)+1):
            if a%i==0:
                divisors.append(i)
                if i!=a//i:
                    divisors.append(a//i)
        divisors.sort()
        return divisors

class Prime():
    # コンストラクタ
    # エラストテネスの篩
    def __init__(self,num):
        self.num = num
        self.sieve = [0 for i in range(self.num + 1)]
        self.sieve[0] = -1
        self.sieve[1] = -1
        for i in range(2,self.num + 1):
            if self.sieve[i] == 0:
                self.sieve[i] = i
                for j in range(i + i,self.num + 1,i):
                    self.sieve[j] = i
    
    # 素数判定
    def isPrime(self,num = None):
        if num is None:
            num = self.num
        if self.sieve[num] == num:
            return True
        else:
            return False
    
    # 素数列挙
    def PrimeNum(self,num = None):
        if num is None:
            num = self.num
        prime = []
        for i in range(2,num):
            if self.sieve[i] == i:
                prime.append(i)
        return prime
    
    # 素因数分解
    def PrimeFact(self,num = None):
        if num is None:
            num = self.num
        fact = []
        while self.sieve[num] != num:
            fact.append(self.sieve[num])
            num //= self.sieve[num]
        fact.append(num)
        return fact

def main():
    n = int(input())
    a = list(map(int,input().split()))
    time1 = time.time()
    prime = []
    p = Prime(max(a))
    for i in range(n):
        _p = p.PrimeFact(a[i])
        mp = {}
        for x in _p:
            mp[x] = mp.get(x,0) + 1
        prime.append(mp)
    lcm = {}
    for x in prime:
        for y in x.keys():
            lcm[y] = max(lcm.get(y,0),x.get(y))
    ans = 0
    for x in prime:
        num = 1
        for y in lcm.keys():
            num = num * (y ** (lcm.get(y) - x.get(y,0)))
        ans += num
        ans %= mod
    print(ans)
    time2 = time.time()
    print(time2 - time1)
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

mod = 10**9+7

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        # if is_prime[i]:
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

primes = sieve(10**3)

def primeFactorization(n):
    ans = [0 for _ in range(len(primes))]
    temp = n
    for i in range(len(primes)):
        while temp%primes[i] == 0:
            ans[i] += 1
            temp /= primes[i]
    return ans

AFactorized = list(map(primeFactorization, A))
# print(primeFactorization(1))
# print(primeFactorization(2))
# print(primeFactorization(3))

lcm = [0 for _ in range(len(primes))]
for i in range(len(primes)):
    for j in AFactorized:
        lcm[i] = max(lcm[i], j[i])

# print(lcm)

lcm_val = 1
for i in range(len(primes)):
    lcm_val *= pow(primes[i], lcm[i], mod)

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

print(ans)

Submission status: Wrong Answer

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

mod = 10**9+7

def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

primes = sieve(10**3)

def primeFactorization(n):
    ans = [0 for _ in range(len(primes))]
    temp = n
    for i in range(len(primes)):
        while temp%primes[i] == 0:
            ans[i] += 1
            temp /= primes[i]
    return ans

AFactorized = list(map(primeFactorization, A))

lcm = [0 for _ in range(len(primes))]
for i in range(len(primes)):
    for j in AFactorized:
        lcm[i] = max(lcm[i], j[i])

lcm_val = 1
for i in range(len(primes)):
    lcm_val *= pow(primes[i], lcm[i], mod)

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

print(ans)

Submission status: Wrong Answer

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

mod = 10**9+7

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

lcm = A[0]
for a in A[1:]:
    lcm = (lcm*a)*pow((gcd(lcm,a)),mod-2,mod)
    lcm %= mod

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

Submission status: Wrong Answer

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

mod = 10**9+7

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

lcm = A[0]
for a in A[1:]:
    lcm = (lcm*a)*pow((gcd(lcm,a)),mod-2,mod)

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

Submission status: Wrong Answer

Solution code:
import fractions
import numpy as np
from functools import reduce
from operator import mul

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

mod = 10**9+7

# エラトステネスの篩
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

primes = sieve(10**3)

def primeFactorization(n):
    ans = [0 for _ in range(len(primes))]
    temp = n
    for i in range(len(primes)):
        while temp%primes[i] == 0:
            ans[i] += 1
            temp /= primes[i]
    return ans

AFactorized = list(map(primeFactorization, A))

lcm = [0 for _ in range(len(primes))]
for i in range(len(primes)):
    for j in AFactorized:
        # lcm = np.maximum(lcm, i)
        lcm[i] = max(lcm[i], j[i])

lcm_val = 1
for i in range(len(primes)):
    lcm_val *= pow(primes[i], lcm[i], mod)

# print(lcm_val)

# B = [lcm-a for a in AFactorized]

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

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
import numpy as np
from functools import reduce
from operator import mul

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

mod = 10**9+7

# エラトステネスの篩
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

primes = sieve(10**3)

def primeFactorization(n):
    ans = [0 for _ in range(len(primes))]
    temp = n
    for i in range(len(primes)):
        while temp%primes[i] == 0:
            ans[i] += 1
            temp /= primes[i]
    return ans

AFactorized = list(map(primeFactorization, A))

lcm = [0 for _ in range(len(primes))]
for i in range(len(primes)):
    for j in AFactorized:
        # lcm = np.maximum(lcm, i)
        lcm[i] = max(lcm[i], j[i])

lcm_val = 1
for i in range(len(primes)):
    lcm_val *= pow(primes[i], lcm[i], mod)

# print(lcm_val)

# B = [lcm-a for a in AFactorized]

ans = 0
for a in A:
    ans += lcm_val // a
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
import numpy as np
from functools import reduce
from operator import mul

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

mod = 10**9+7

# エラトステネスの篩
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

primes = sieve(10**3)

def primeFactorization(n):
    ans = [0 for _ in range(len(primes))]
    temp = n
    for i in range(len(primes)):
        while temp%primes[i] == 0:
            ans[i] += 1
            temp /= primes[i]
    return ans

AFactorized = list(map(primeFactorization, A))

lcm = [0 for _ in range(len(primes))]
for i in AFactorized:
    lcm = np.maximum(lcm, i)

B = [lcm-a for a in AFactorized]

ans = 0
for b in B:
    ans += reduce(mul, primes**b%mod)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]
    
def main():
    n = inp()
    a = inpl()
    dic = defaultdict(int)
    pre = [defaultdict(int) for _ in range(n)]
    for i in range(n):
        x = a[i] 
        check = 2
        while(x!=1 and check <= int(x**0.5)+2):
            cnt = 0
            while x%check==0:
                x //= check
                cnt += 1
            if cnt > 0:
                pre[i][check] = cnt
                if dic[check] < cnt:
                    dic[check] = cnt
            check += 1
        if x != 1:
            dic[x] = max(dic[x],1)
    ans = 0
    for i in range(n):
        x = 1
        for e in dic:
            x = (x*pow(e,dic[e]-pre[i][e],mod))%mod
        ans = (ans+x) % mod
    print(ans)
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    
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 = 1
    for i in range(n):
        LCM = lcm(a[i],LCM)
    ans = 0
    for i in range(n):
        ans += (LCM//a[i])%mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def extgcd(a,b): # ax+by=1 をみたす(x,y)の組を求める
    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]]
# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return ( m + x%m ) % m
    
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 nCk(n,k):
    res = 1
    a=n-k
    b=k
    for i in range(1,a+b+1):
        res = res*i%mod
    for i in range(1,a+1):
        res = res*mod_inv(i,mod)%mod
    for i in range(1,b+1):                                 
        res = res*mod_inv(i,mod)%mod
    return res
    
def main():
    n = inp()
    a = inpl()
    dic = defaultdict(int)
    pre = [defaultdict(int) for _ in range(n)]
    for i in range(n):
        x = a[i] 
        check = 2
        while(x!=1 and check <= int(x**0.5)+2):
            cnt = 0
            while x%check==0:
                x //= check
                cnt += 1
            if cnt > 0:
                pre[i][check] = cnt
                if dic[check] < cnt:
                    dic[check] = cnt
            check += 1
        if x != 1:
            dic[x] = max(dic[x],1)
    ans = 0
    for i in range(n):
        x = 1
        for e in dic:
            x = (x*pow(e,dic[e]-pre[i][e],mod))%mod
            print(i,x,e,dic[e]-pre[i][e])
        ans = (ans+x) % mod
    print(ans)

if __name__ == "__main__":
    main()