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:
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 = []
    for i in range(n):
        p = Prime(a[i])
        _p = p.PrimeFact()
        mp = {}
        for x in _p:
            if x in mp.keys():
                mp[x] += 1
            else:
                mp[x] = 1
        prime.append(mp)
    lcm = {}
    for x in prime:
        for y in x.keys():
            if y in lcm.keys():
                lcm[y] = max(lcm[y],x[y])
            else:
                lcm[y] = x[y]
    b = []
    for x in prime:
        num = 1
        for y in lcm.keys():
            if y in x.keys():
                num *= y ** (lcm[y] - x[y])
                num %= mod
            else:
                num *= y ** lcm[y]
                num %= mod
        b.append(num)
    ans = 0
    for i in range(n):
        ans += b[i]
        ans %= mod
    print(ans)
    time2 = time.time()
    print(time2 - time1)
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import fractions

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

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

ans = 0

for a in A:
    ans += ( lm//a )% Mod

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions

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

def lcm(L):
    r = 1
    for l in L:
        r = r*l // fractions.gcd(r,l)
    return r

ans = 0
lm = lcm(A)
for a in A:
    ans += ( lm//a )% Mod

print(ans)

Submission status: Wrong Answer

Solution code:
import functools

MOD = 10**9 + 7


def lcm(a, b):
    c, d = a, b
    while d != 0:
        c, d = d, c % d
    return a / c * b


def inv_mod(x):
    return pow(x, MOD - 2)


def pow(x: int, n: int) -> int:
    res = 1
    while n > 0:
        if n & 1 == 1:
            res = res * x % MOD
        x = x * x % MOD
        n >>= 1

    return res


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

    lcm_an = functools.reduce(lcm, an)
    lcm_an %= MOD

    ans = 0
    for a in an:
        ans = (ans + lcm_an * inv_mod(a)) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import fractions
import functools

MOD = int(1e9) + 7


def lcm(a, b):
    c, d = a, b
    while d != 0:
        c, d = d, c % d
    return a // c * b


class Inv:

    @classmethod
    def pow(cls, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % MOD
            x = x * x % MOD
            n >>= 1
        return ret

    @classmethod
    def inv(cls, x: int) -> int:
        return cls.pow(x, MOD - 2)


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

v = functools.reduce(lcm, A)
v %= MOD
ans = 0
for a in A:
    ans = (ans + v // a) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

n=int(input())
a=[int(i) for i in input().split()]
L=a[0]
for i in a:
    if L%i!=0:
        L=L*i//gcd(L,i)
L%=(10**9+7)
ans=0
for i in a:
    ans=(ans+L//i)%(10**9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
import functools

MOD = int(1e9) + 7


class Inv:

    @classmethod
    def pow(cls, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % MOD
            x = x * x % MOD
            n >>= 1
        return ret

    @classmethod
    def inv(cls, x: int) -> int:
        return cls.pow(x % MOD, MOD - 2)


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

MAX_A = 1000010

facts = [0] * MAX_A
p = [False] * MAX_A

def prime():

    for i in range(2, MAX_A):
        p[0] = p[1] = True
        if not p[i]:
            j = 2 * i
            while j < MAX_A:
                p[j] = True
                j += i

prime()

for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            ii = a // i
            c1 = 0
            while a % i == 0:
                c1 += 1
                a //= i
            c2 = 0
            while p[ii] and a % ii == 0:
                c2 += 1
                a //= ii
            facts[i] = max(facts[i], c1)
            facts[ii] = max(facts[ii], c2)
        i += 1
    if not p[a]:
        facts[a] = max(facts[a], 1)

tar = 1
for idx, c in enumerate(facts):
    if c == 0:
        continue
    tar *= Inv.pow(idx, c)
    tar %= MOD

ans = 0
for a in A:
    ans += tar * Inv.inv(a) % MOD
    ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
import functools

MOD = int(1e9) + 7


class Inv:

    @classmethod
    def pow(cls, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % MOD
            x = x * x % MOD
            n >>= 1
        return ret

    @classmethod
    def inv(cls, x: int) -> int:
        return cls.pow(x % MOD, MOD - 2)


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

MAX_A = 1000010

facts = [0] * MAX_A

for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            ii = a // i
            c1 = 0
            while a % i == 0:
                c1 += 1
                a //= i
            c2 = 0
            while a % ii == 0:
                c2 += 1
                a //= ii
            facts[i] = max(facts[i], c1)
            facts[ii] = max(facts[ii], c2)
        i += 1
    if a != 1:
        facts[a] = max(facts[a], 1)

tar = 1
for idx, c in enumerate(facts):
    if c == 0:
        continue
    tar *= Inv.pow(idx, c)
    tar %= MOD

ans = 0
for a in A:
    ans += tar * Inv.inv(a) % MOD
    ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int, input().split()))
mod = 10**9+7
def sep(x):
  a = [0]*1000
  for i in range(2,1000):
    while not x%i:
      x //= i
      a[i] += 1
  return tuple(a)

t = [0]*1000
for x in l:
  a = sep(x)
  for i in range(1000):
    if t[i] < a[i]:
      t[i] = a[i]
ans = 0
for x in l:
  a = sep(x)
  g = [x-y for x,y in zip(t,a)]
  d = 1
  for i,e in enumerate(g):
    if e:
      d = d*i**e%mod
  ans = (ans+d)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
#from math import gcd
import numpy as np
N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
def lcm(a,b):
    return a*b // gcd(a,b)
B = np.array([1]*N,dtype=np.int64)
for i in range(N-1):
    a_mul = 1
    lc = lcm(A[i],A[i+1])
    t = lc // A[i]
    if gcd(B[i],t) != 1:
        #print(B[i],t)
        b_mul = lcm(B[i],t) // B[i]
        a_mul = lcm(B[i],t) // t
        B[i] = lc*a_mul // A[i]
        B[:i] *= b_mul
    else:
        B[i] = t
    B[i+1] = lc*a_mul // A[i+1]
    #print(B)

print(sum(B)%M)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
class sieve:
  def __init__(self, n):
    self.n = n
    self.sv = [1] * (n + 1)
    self.sv[0] = 0
    self.sv[1] = 0
    for i in range(2, n + 1):
      if self.sv[i]:
        for j in range(i * 2, n + 1, i):
          self.sv[j] = 0
  def isprime(self, x):
    if x > self.n:
      return False
    return self.sv[x] == 1
  def factorize(self, x):
    res = []
    for i in range(2, self.n + 1):
      if self.sv[i]:
        while x % i == 0:
          x //= i
          res.append(i)
    if x != 1:
      res.append(x)
    return res
  def modlcm(self, a, mod):
    res = [0] * (self.n + 1)
    ex = []
    for i in range(len(a)):
      f = self.factorize(a[i])
      for j in f:
        if j > self.n:
          ex.append(j)
          continue
        res[j] = max(f.count(j), res[j])
    rres = 1
    for i in range(self.n + 1):
      if res[i] != 0:
        rres *= pow(i, res[i], mod)
        rres %= mod
    for i in ex:
      rres *= i
      rres %= mod
    return rres
sv = sieve(10 ** 3)
lcm = sv.modlcm(a, 10 ** 9 + 7)
res = 0
for x in a:
  res += lcm * pow(x, 10 ** 9 + 5, 10 ** 9 + 7)
  res %= 10 ** 9 + 7
print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


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


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


def solve(N: int, A: "List[int]"):

    # 最小公倍数
    lcm = 1
    for a in A:
        lcm = LCM(lcm, a)
    lcm = lcm % MOD
    print(sum([lcm//a for a in A]) % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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())
a = list(map(int, input().split()))

A = lcm(a);
ans = 0

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

Submission status: Wrong Answer

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
from collections import Counter
MAX = 1000005
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()
N = int(input())
A = list(map(int, input().split()))

primes = {}

for val in A:
    p = 2
    while val >= p * p:
        if val % p == 0:
            # 割り切れるならそこから話が始まる
            cnt = 0
            while val % p == 0:
                cnt += 1
                val //= p
            if p not in primes:
                primes[p] = cnt
            else:
                primes[p] = max(cnt, primes[p])
        p += 1
    if val != 1:
        if val not in primes:
            primes[val] = 1

lcm = 1
for p, cnt in primes.items():
    lcm *= p * cnt
    lcm %= MOD

ans = 0
for val in A:
    ans += lcm * inverse[val]
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
# 二項係数を"やるだけ"にしてくれるライブラリ
from collections import Counter
MAX = 1000007
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX


# テーブルを作る前処理
def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD


# 二項係数計算
def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD


# 前処理完了
COMinit()

# 素因数分解する
N = int(input())
A = list(map(int, input().split()))

e = [0] * (max(A)+1)

for a in A:
    cur = a  # aを素因数分解する
    for j in range(2, int(a**(1/2)+4)):
        cnt = 0
        while cur % j == 0:
            cnt += 1
            e[j] = max(e[j], cnt)
            cur //= j

        if cur == a:
            e[a] = 1

lcm = 1
mod = 10**9 + 7
for i in range(1, len(e)):
    if e[i] == 0:
        continue
    lcm *= (i**e[i]) % mod
    lcm %= mod

ans = 0
for a in A:
    ans += (lcm * inverse[a])
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
import fractions
#import numpy as np

mod=int(10**9+7)

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

#main
N=int(input())
A=list(map(int,input().split()))
l=A[0]
for a in range(1,N):
    l=lcm(l,A[a])
l%=mod

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
import fractions
#import numpy as np

mod=int(10**9+7)

def lcm(a,b):
    ab=a*b
    return ab*pow(fractions.gcd(a,b),mod-2,mod)

#main
N=int(input())
A=list(map(int,input().split()))
l=A[0]
for a in range(1,N):
    l=lcm(l,A[a])
l%=mod

ans=0
for a in A:
    ans+=l*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):
        for j in range(i*2, n+1):
            if j%i == 0:
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

primes = sieve(int(max(A)**0.5)*2)

def primeFactorization(n):
    temp = n
    ans = [0 for _ in range(len(primes))]
    for i in range(len(primes)):
        while temp%primes[i] == 0:
            temp /= primes[i]
            ans[i] += 1
    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 heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True
import fractions
ans=0

n=I()
a=LI()
g=a[0]
for i in range(1,n):
    g=fractions.gcd(a[i],g)

m=1
for i in a:
    m*=i
    m%=mo
x=1
for i in a:
    x+=m*pow(i,mo-2,mo)
    x%=mo
    
x*=pow(g,mo-2,mo)
x%=mo

print(x)

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):
        for j in range(i*2, n+1):
            if j%i == 0:
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

primes = sieve(int(max(A)**0.5)+1)

def primeFactorization(n):
    temp = n
    ans = [0 for _ in range(len(primes))]
    for i in range(len(primes)):
        while temp%primes[i] == 0:
            temp /= primes[i]
            ans[i] += 1
    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:
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):
        for j in range(i*2, n+1):
            if j%i == 0:
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

primes = sieve(int(max(A)**0.5)+1)

def primeFactorization(n):
    temp = n
    ans = [0 for _ in range(len(primes))]
    for i in range(len(primes)):
        while temp%primes[i] == 0:
            temp /= primes[i]
            ans[i] += 1
    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)
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
MOD = 10**9 + 7
U = 10**6 + 10

is_prime = np.zeros(U,np.bool) #素数列挙(エラトステネス)
is_prime[2] = 1
is_prime[3::2] = 1
# print(is_prime)
for p in range(3,U,2):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::p+p] = 0

M = 10**3
small_primes = np.where(is_prime[:M])[0].tolist()
B = A.copy()
lcm = 1
for p in small_primes:
    e = 0
    while np.any(A % p == 0):
        e += 1
        A[A%p == 0] //= p
    lcm *= p**e
    lcm %= MOD

# Mより大きい数は、ここに現れる
for x in set(A.tolist()):
    print(x)

ans = sum(pow(x, MOD-2, MOD) for x in B.tolist()) % MOD
ans *= lcm
ans %= MOD
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = defaultdict(int)  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return primes

PC = [primeCount(a) for a in set(A)]

primes = defaultdict(int)
for pc in PC:
    for p, c in pc.items():
        if c > primes[p]:
            primes[p] = c

print(0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = defaultdict(int)  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return primes

PC = [primeCount(a) for a in A]

primes = defaultdict(int)
for pc in PC:
    for p, c in pc.items():
        if c > primes[p]:
            primes[p] = c

print(0)

Submission status: Wrong Answer

Solution code:

import numpy as np 
N = int(input())
A = np.array(list(map(int, input().split())))
MOD = 10**9 + 7
U = 10**6 + 10

is_prime = np.zeros(U,np.bool) #素数列挙(エラトステネス)
is_prime[2] = 1
is_prime[3::2] = 1
# print(is_prime)
for p in range(3,U,2):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::p+p] = 0

M = 10**3
small_primes = np.where(is_prime[:M])[0].tolist()
B = A.copy()
lcm = 1
for p in small_primes:
    e = 0
    while np.any(A % p == 0):
        e += 1
        A[A%p == 0] //= p
    lcm *= p**e
    lcm %= MOD

ans = sum(pow(x, MOD-2, MOD) for x in B.tolist()) % MOD
ans *= lcm
ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
mod = 10**9 + 7
n = int(input())
lst = list(map(int, input().split()))
koubai = lst[0]
def gcd(a, b):
    if a > b:
        a, b = b, a
    while b > 0:
        a, b = b, a % b
    return a
for i in range(1, n):
    koubai = koubai*lst[i]//gcd(koubai, lst[i])
 
total = 0
for l in lst:
    b = koubai//l
print(total%mod)

Submission status: Wrong Answer

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

mod = 10**9 + 7

primes = [2,3,5,7]
for i in range(8,1001):
    check = True
    for j in primes:
        if(j > i**0.5):
            break
        if(i%j == 0):
            check = False
            break
    if(check):
        # print(i)
        primes.append(i)

p_fac = {}
for i in primes:
    p_fac[i] = 0

for i in range(n):
    temp = a[i]
    for j in primes:
        count = 0
        if(temp%(j**max(1,p_fac[j])) == 0):
            temp = temp // j
            count = p_fac[j]+1
            while(True):
                if(temp%j == 0):
                    temp = temp // j
                    count += 1
                else:
                    break
            p_fac[j] = count
        else:
            while(True):
                if(temp%j == 0):
                    temp = temp // j
                else:
                    break
    if(temp > 1):
        primes.append(temp)
        p_fac[temp] = 1

lcm = 1
for key, value in p_fac.items():
    for i in range(value):
        lcm = lcm*key % mod

# aの逆元を求める
max = max(a)
inv = [0]*(max+1)
inv[0] = 1
inv[1] = 1
for i in range(2,max+1):
    inv[i] = inv[mod % i] * (mod - mod//i ) % mod

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

print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
lcm=1
d=dict()
for i in range(n):
  k=a[i]
  for j in range(1,int(a[i]**0.5)+1):
    cnt=0
    while k%(j+1)==0:
      k//=j+1
      cnt+=1
    if j+1 in d:
      if d[j+1]<cnt:
        lcm*=(j+1)**(cnt-d[j+1])
        d[j+1]=cnt
    else:
      lcm*=(j+1)**cnt
      d[j+1]=cnt
  if k in d:
    if d[k]<1:
      lcm*=k
      d[k]=1
  else:
    lcm*=k
    d[k]=1
ans=0
print(d)
for i in range(n):
  ans+=(lcm//a[i])%mod
print(ans%mod)

Submission status: Wrong Answer

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

MOD = 10**9+7

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

def main():
    N = int(input())
    a = [int(i) for i in input().split()]
    A = np.array(a)  

    lcm = reduce(lcm_base, A, 1)
    B = lcm // A

    print(np.sum(B) % MOD)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
lcm=1
d=dict()
for i in range(n):
  k=a[i]
  for j in range(1,int(a[i]**0.5)+1):
    cnt=0
    while k%(j+1)==0:
      k//=j+1
      cnt+=1
    if j+1 in d:
      if d[j+1]<cnt:
        lcm*=(j+1)**(cnt-d[j+1])
        d[j+1]=cnt
    else:
      lcm*=(j+1)**cnt
      d[j+1]=cnt
  if k in d:
    if d[j+1]<1:
      lcm*=k
      d[k]=1
ans=0
for i in range(n):
  ans+=(lcm//a[i])%mod
print(ans%mod)

Submission status: Wrong Answer

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

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

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

L = A[0]
A = set(A)
for a in A:
    L = lcm(L, a)

ans = 0
for a in A:
    ans += L // a
    ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
lst = []
s = 0
ele = input()

# for i in range(0, n): 
#     ele = (input()) 
  
#     lst.append(ele)



lst = list(ele.split(" "))

for i in range(n):
    lst[i] = int(lst[i])


    

def compute_lcm(x, y):
  # choose the greater number
  if x > y:
      greater = x
  else:
      greater = y
  while(True):
      if((greater % x == 0) and (greater % y == 0)):
          lcm = greater
          break
      greater += 1
  return lcm
   
lccm = lst[0];
for i in range(n):
    lccm = compute_lcm(lccm, lst[i])
    

lsst = []
s = 0
for i in range(n):
    s = lccm/lst[i]
    lsst.append(s)
    
s = 0
for i in range(n):
    s = s + lsst[i]
    
s = s%(10^9 + 7)

print(int(s))

Submission status: Wrong Answer

Solution code:
import math

M = 10 ** 9 + 7

def calc_primes(n):
	max = math.ceil(math.sqrt(n))
	table = [True] * (max + 1)
	i = 2
	while i <= max:
		if table[i]:
			j = i * 2
			while j <= max:
				table[j] = False
				j *= 2
		
		i += 1
	primes = []
	for i in range(2, max + 1):
		if table[i]:
			primes.append(i)
	return primes

factor_cache = {}

def calc_factors(n, i = 0):
	if n in factor_cache:
		return factor_cache[n]
	max = math.ceil(math.sqrt(n))
	p = primes[i]
	while True:
		if n % p == 0:
			factors = calc_factors(n // p, i).copy()
			if p in factors:
				factors[p] += 1
			else:
				factors[p] = 1
			factor_cache[n] = factors
			return factors
		else:
			i += 1
			if i >= prime_count:
				break
			p = primes[i]
	if n != 1:
		factors = {n: 1}
		factor_cache[n] = factors
		return factors
	else:
		return {}

N = int(input())

primes = calc_primes(1024)
prime_count = len(primes)

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

total_factors = {}
factors_list = []

for A in A_list:
	factors = calc_factors(A)
#	print(factors)
	factors_list.append(factors)
	for factor, count in factors.items():
		if factor not in total_factors:
			total_factors[factor] = count
		elif total_factors[factor] < count:
			total_factors[factor] = count

total = 0
for A, factors in zip(A_list, factors_list):
	B = 1
	for factor, count in total_factors.items():
		if factor in factors:
			count -= factors[factor]
#		for _ in range(count):
#			B = (B * factor) % M
		B = (B * pow(factor, count, M)) % M
	total = (total + B) % M

print(total)

Submission status: Wrong Answer

Solution code:
from collections import *
import sys
input = sys.stdin.readline

#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


mod = 10**9+7
n = int(input())
a = tuple(map(int,input().split()))

pr = primes(10**6+1)

d = defaultdict(lambda : 0)

for elt in a:
    for p in pr:
        if elt < p:
            break
        c = 0
        while not elt%p:
            c += 1
            elt //= p
        if c > d[p]:
            d[p] = c
    if elt > 1 and d[elt] == 0:
        d[elt] = 1

print(d)

lcm  = 1
for elt in d:
    lcm = lcm*pow(elt,d[elt],mod)%mod

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