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 sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
import math
from functools import reduce

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

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

x = reduce(lcm, a, 1)

ans = 0
for i in a:
    ans += x // i

print(ans%100000007)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
import math
from functools import reduce

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

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

x = reduce(lcm, a)

ans = 0
for i in a:
    ans += x // i

print(ans%100000007)

Submission status: Wrong Answer

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

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

a_gcd = 1
a_seki = 1
for i in range(n):
    a_gcd = math.gcd(a_gcd, a[i])
    a_seki = a_seki * a[i]
a_lcm = a_seki//a_gcd

b_sum = 0
for i in range(n):
    b_sum = (b_sum + (a_lcm // a[i])) % mod

print(b_sum)

Submission status: Wrong Answer

Solution code:
from math import gcd
MOD = 10**9+7

def LCM(n,r):
    return ((n*r) * pow(gcd(n,r), MOD-2,MOD)) % MOD
    
N = int(input())
A = list(map(int,input().split()))
lcm = A[0]
for i in range(1,N):
    lcm = LCM(lcm,A[i])

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

Submission status: Wrong Answer

Solution code:
import sys
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

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

MOD = 10**9+7
n, *a = map(int, sys.stdin.buffer.read().split())
l = a[0]
for x in a[1:]:
    l = lcm(x, l)
    l %= MOD

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import math

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

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

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

l = a[0]
for i in range(n):
    l = lcm(l, a[i])

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

print(ans%mod)

Submission status: Wrong Answer

Solution code:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
"""
from math import gcd
mod = 10**9 +7
N = int(input())
A = list(map(int,input().split()))
l = A[0]
for i in range(1,N):
    l = ((l*A[i])//gcd(l,A[i]))%mod

ans = 0
for a in A:
    ans += l//a
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
import functools
import operator


def prime_factor(a, temp):
    while a > 1:
        yield temp[a]
        a //= temp[a]


def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    max_a = 10 ** 6
    temp = [0] * (max_a + 1)
    temp[1] = 1

    for i in range(2, max_a + 1):
        if temp[i]:
            continue

        for j in range(i, max_a + 1, i):
            temp[j] = i
    
    ap_list = [Counter(prime_factor(a, temp)) for a in A]
    lcm = functools.reduce(operator.ior, ap_list)

    mod = 10 ** 9 + 7
    ans = 0
    for ap in ap_list:
        b = 1
        for k, v in (lcm - ap).items():
            for _ in range(v):
                b *= k
                if b > mod:
                    b %= mod
        ans += b
        if ans > mod:
            ans %= mod

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]

def gcd(p,q):
    if q == 0:
        return p
    else:
        return gcd(q,min(p%q,q-p%q))

lcm = 1
for i in range(N-1):
    if i == 0:
        lcm = A[0]*A[1]//gcd(A[0],A[1])
    else:
        lcm = lcm*A[i+1]//gcd(lcm,A[i+1])

ans = 0
for i in range(N):
    ans += (lcm//A[i])%(10**9+7)

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

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce


N = int(input())
A = list(map(int, input().split()))
P = int(1e9+7)

def lcm_base(x, y):
    ret = (x * y) // math.gcd(x, y)
    return ret


def lcm(iter):
    return reduce(lcm_base, iter, 1)


lcm_a = lcm(A)
"""
ans = 0
for a in A:
    ans = (ans + lcm_a//a) %P
print(ans)
"""

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
A = list(map(int, input().split( )))
mod = 10**9 + 7
#Aたちの最小公倍数をMとすれば
#答えはsum_{i}M/A_{i} (mod 10**9 + 7)

#(A,B,C)の最小公倍数　=(A,B)の最小公倍数とCの最小公倍数を利用すれば簡単そう.
a = A[0]
s = 1
for i in range(1, n):
  g = math.gcd(a,A[i])
  d, e = a//g, A[i]//g
  s = (s*e + d)%mod
  print(g,d,e,s)
  a = a*A[i]//g
print(s)

Submission status: Wrong Answer

Solution code:
def factorize(n):
    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
            if i in fact:
                fact[i] = max(fact[i],cnt)
            else:
                fact[i] = cnt
         
    if tmp != 1:
        if tmp in fact:
            fact[tmp] = max(fact[tmp],1)
        else:
            fact[tmp] = 1
    
    if len(fact) == 0:
        if N in fact:
            fact[N] = max(fact[N],1)
        else:
            fact[N] = 1

def inv(n, p):
    return pow(n, p-2, p)
    
N = int(input())
A = list(map(int, input().split()))
p = 10**9+7

fact = {}

for i in range(N):
    factorize(A[i])

lcm = 1

for key, val in fact.items():
    lcm *= pow(key, val, p)
    lcm %= p

inv_sum = 0

for i in range(N):
    inv_sum += inv(A[i], p)
    inv_sum %= p

print(lcm * inv_sum % p)

Submission status: Wrong Answer

Solution code:
n,*aa = map(int, open(0).read().split())
MOD = 10**9+7

from collections import Counter
from math import sqrt, ceil
def factors(x):
    c = Counter()
    while x % 2 == 0:
        c[2] += 1
        x //= 2
    for i in range(3, ceil(sqrt(x)) + 2, 2):
        while x % i == 0:
            c[i] += 1
            x //= i
    return c

factors_of_aa = list(map(factors, aa))

lcm = Counter()
for factors_of_a in factors_of_aa:
    lcm |= factors_of_a

ans = 0
for factors_of_a in factors_of_aa:
    factors_to_add = lcm - factors_of_a
    to_add = 1
    for factor, cnt in factors_to_add.items():
        to_add *= pow(factor, cnt, MOD)
        to_add %= MOD
    ans += to_add
    ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import groupby
from collections import Counter

### https://atcoder.jp/contests/abc152/submissions/15835670
def fast_prime_factorization_many(lst):
  # 素因数分解（ロー法、複数）
  from subprocess import Popen, PIPE
  res = Popen(["factor"] + list(map(str, lst)), stdout=PIPE).communicate()[0].split(b"\n")[:-1]
  return [Counter(list(map(int, r.split()[1:]))) for r in res]

def main():
  import sys
  input = sys.stdin.readline
  N = int(input())
  A = list(map(int, input().split()))
  if N == 1:
    print(1)
    exit(0)
  
  mod = int(1e9+7)
  Factors = fast_prime_factorization_many(A)
  #print(Factors)
  ### lcmを求める
  lcm = 1
  max_factor = [0] * (1000010)
  for f in Factors:
    for k,v in f.items():
      v_prev = max_factor[k]
      if v_prev < v:
        for i in range(v-v_prev):
          lcm = lcm * k % mod
        max_factor[k] = v
        
  print(lcm)
  ans = 0
  for a in A:
    wk =  lcm * pow(a,mod-2,mod)
    print(wk)
    ans += wk
    ans %= mod
  print(ans)
  exit(0)
  
main()

Submission status: Wrong Answer

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

N = int(input())
A = list(map(int, input().split()))
if N == 1:
  print(1)
  exit(0)
  
mod = int(1e9+7)

######
# https://qiita.com/fantm21/items/5e270dce9f4f1d963c1e
import math

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
##########

B = get_sieve_of_eratosthenes(10**3+10)
#print(len(B))
from collections import defaultdict
D = defaultdict(int)
    
def insu_bunkai(a):
  ret = defaultdict(int)
  for b in B:
    while a%b == 0:
      a = a // b
      ret[b] += 1
    if a > 1000:
      ret[a] += 1
      break
  return ret
DA = [[] for _ in range(N)]
idx = 0
for a in A:
  w = insu_bunkai(a)
  for k,v in w.items():
    D[k] = max(D[k], v)
  DA[idx] = w
  idx += 1  
  
ans = 0
for i in range(N):
  wk = 1
  for k,v in D.items():
    if k in DA[i]:
      wk *= pow(k,v-DA[i][k],mod)
    else:
      wk *= pow(k,v,mod) 
    wk %= mod
  ans += wk
  ans %= mod
  
print(ans)

Submission status: Wrong Answer

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

N = int(input())
A = list(map(int, input().split()))
if N == 1:
  print(1)
  exit(0)
  
mod = int(1e9+7)

######
# https://qiita.com/fantm21/items/5e270dce9f4f1d963c1e
import math

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
##########

B = get_sieve_of_eratosthenes(10**3+10)
#print(len(B))
from collections import defaultdict
D = defaultdict(int)
    
def insu_bunkai(a):
  ret = defaultdict(int)
  for b in B:
    while a%b == 0:
      a = a // b
      ret[b] += 1
    if a > 1000:
      ret[a] += 1
      break
  return ret
DA = [[] for _ in range(N)]
for i in range(N):
  a = A[i]
  w = insu_bunkai(a)
  for k,v in w.items():
    D[k] = max(D[k], v)
  DA[i] = w
  
ans = 0
for i in range(N):
  wk = 1
  for k,v in D.items():
    if k in DA[i]:
      wk *= pow(k,v-DA[i][k],mod)
    else:
      wk *= pow(k,v,mod) 
    wk %= mod
  ans += wk
  ans %= mod
  
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N == 1:
  print(1)
  exit(0)
  
mod = int(1e9+7)

######
# https://qiita.com/fantm21/items/5e270dce9f4f1d963c1e
import math

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]
##########

B = get_sieve_of_eratosthenes(10**3+10)
print(len(B))
from collections import defaultdict
D = defaultdict(int)
    
def insu_bunkai(a):
  ret = defaultdict(int)
  for b in B:
    while a%b == 0:
      a = a // b
      ret[b] += 1
    if a > 1000:
      ret[a] += 1
      break
  return ret
DA = []
for a in A:
  w = insu_bunkai(a)
  for k,v in w.items():
    D[k] = max(D[k], v)
  DA.append(w)
  
ans = 0
for i in range(N):
  wk = 1
  for k,v in D.items():
    if k in DA[i]:
      wk *= pow(k,v-DA[i][k],mod)
    else:
      wk *= pow(k,v,mod) 
    wk %= mod
  ans += wk
  ans %= mod
  
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()



D = defaultdict(int)
for i in range(n):
    a = A[i]
    Di = defaultdict(int)
    for j in range(2, int(a ** 0.5) + 1):
        while a % j == 0:
            a //= j
            Di[j] += 1
        if a == 0:
            break
    for k in Di:
        D[k] = max(D[k], Di[k])

ret = 1
for ki in D:
    ret = ret * pow(ki, D[ki], mod)
    ret %= mod

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

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

# エラトステネスの篩(コピペ用)
table_len = 1010
prime_list = [] # 必要に応じて
isprime = [True] * (1010)
isprime[0] = isprime[1] = False
for i in range(table_len):
    if isprime[i]:
        for j in range(2*i, table_len, i):
            isprime[j] = False
        prime_list.append(i) # 必要に応じて

N = int(input())
As = list(map(int, input().split()))
factor_counts = [0] * len(prime_list)
big_factors = []
for A in As:
    for i, p in enumerate(prime_list):
        count = 0
        while A % p == 0:
            A //= p
            count += 1
        factor_counts[i] = max(factor_counts[i], count)
        if A == 1:
            break
    else:
        big_factors.append(A)

A_lcm = 1
for p, count in zip(prime_list, factor_counts):
    A_lcm *= pow(p, count, MOD)
    A_lcm %= MOD

for p in big_factors:
    A_lcm *= p
    A_lcm %= MOD

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

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
a = max(A)
prime_num = [2]
sgn = [0 for _ in range(max(int(a**0.5)+1, 4))]
sgn[2] = 1
for k in range(3, len(sgn), 2):
  if sgn[k] == 0:
    prime_num.append(k)
    for j in range(k, a+1, 2*k):
      sgn[k] = 1
baisu = []
count = [0 for _ in range(a+1)]
each_fac = [[]for _ in range(N)]
for k in range(N):
  b = 0 + A[k]
  for p in prime_num:
    if p**2 <= b:
      if b%p == 0:
        if count[p] == 0:
          baisu.append(p)
        c = 0
        while b % p == 0:
          b //= p 
          c += 1
        each_fac[k].append([p,c]) 
        if c > count[p]:
          count[p] = c
    else:
      break
  if b != 1:
    each_fac[k].append([b, 1])
    if count[b] == 0:
      count[b] = 1
      baisu.append(b)
ans = 0
for k in range(N):
  pr = 1
  flag = [-1 for _ in range(A[k]+1)]
  for item in each_fac[k]:
    flag[item[0]] = item[1]
  for item in baisu:
    if item > A[k]:
      pr *= pow(item, count[item], mod)
      continue
    if flag[item] == -1:
      pr *= pow(item, count[item], mod)
      pr %= mod
    else:
      pr *= pow(item, count[item]-flag[item], mod)
      pr %= mod
  print(pr)
  ans += pr
  ans %= mod

    

"""
product = 1
for item in baisu:
  product *= pow(item, count[item], mod)
  product %= mod

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

ans = 0
for k in range(N):
  ans += product*modinv(A[k])
  ans %= mod
"""
print(ans)

Submission status: Wrong Answer

Solution code:
# !/usr/bin/python3

"""
https://atcoder.jp/contests/abc152/tasks/abc152_e
Flatten.
"""

MOD = int(1e9+7)

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

def inverse(a, b, x=None, y=None):
    if b == 0:
        x = 1
        y = 0
        return (a, x, y);
    d, x1, y1 = inverse(b, a % b, x, y)
    x = y1
    y = x1-y1*(a//b)
    return (d, x, y)

def solve(a, n):
    lcm = 1

    for i in range(n):
        g = gcd(lcm, a[i])
        inv = inverse(g, MOD)[1]
        inv = (inv%MOD+MOD)%MOD
        lcm = lcm*a[i]*inv

    ans = 0
    for i in range(n):
        inv = inverse(a[i], MOD)[1]
        inv = (inv%MOD+MOD)%MOD
        ans = ans+(lcm*inv)%MOD

    return ans%MOD

if __name__ == "__main__":
    n = int(input())
    a = [(lambda x: int(x))(x) for x in input().split()]
    print(solve(a, n))

Submission status: Wrong Answer

Solution code:
# !/usr/bin/python3

"""
https://atcoder.jp/contests/abc152/tasks/abc152_e
Flatten.
"""

MOD = int(1e9+7)

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

def inverse(a, b, x=None, y=None):
    if b == 0:
        x = 1
        y = 0
        return (a, x, y);
    d, x1, y1 = inverse(b, a % b, x, y)
    x = y1
    y = x1-y1*(a//b)
    return (d, x, y)

def solve(a, n):
    lcm = a[0]

    for i in range(1, n):
        g = gcd(lcm, a[i])
        inv = inverse(g, MOD)[1]
        inv = (inv%MOD+MOD)%MOD
        lcm = lcm*a[i]*inv

    ans = 0
    for i in range(n):
        inv = inverse(a[i], MOD)[1]
        inv = (inv%MOD+MOD)%MOD
        ans = ans+(lcm*inv)%MOD

    return ans%MOD

if __name__ == "__main__":
    n = int(input())
    a = [(lambda x: int(x))(x) for x in input().split()]
    print(solve(a, n))

Submission status: Wrong Answer

Solution code:
# !/usr/bin/python3

"""
https://atcoder.jp/contests/abc152/tasks/abc152_e
Flatten.
"""

MOD = int(1e9+7)

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

def inverse(a, b, x=None, y=None):
    if b == 0:
        x = 1
        y = 0
        return (a, x, y);
    d, x1, y1 = inverse(b, a % b, x, y)
    x = y1
    y = x1-y1*(a//b)
    return (d, x, y)

def solve(a, n):
    lcm = a[0]

    for i in range(1, n):
        g = gcd(lcm, a[i])
        inv = inverse(g, MOD)[1]
        lcm = lcm*a[i]*inv

    ans = 0
    for i in range(n):
        inv = inverse(a[i], MOD)[1]
        ans = ans+(lcm*inv)%MOD

    return ans%MOD

if __name__ == "__main__":
    n = int(input())
    a = [(lambda x: int(x))(x) for x in input().split()]
    print(solve(a, n))

Submission status: Wrong Answer

Solution code:
# !/usr/bin/python3

"""
https://atcoder.jp/contests/abc152/tasks/abc152_e
Flatten.
"""

MOD = int(1e9+7)

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

def inverse(a, b, x=None, y=None):
    if b == 0:
        x = 1
        y = 0
        return (a, x, y);
    d, x1, y1 = inverse(b, a % b, x, y)
    x = y1
    y = x1-y1*(a//b)
    return (d, x, y)

def solve(a, n):
    lcm = a[0]

    for i in range(1, n):
        g = gcd(lcm, a[i])
        inv = inverse(g, MOD)[1]
        # print(g, inv)
        lcm = lcm*a[i]*inv
        # print(lcm)

    ans = 0
    for i in range(n):
        inv = inverse(a[i], MOD)[1]
        ans = ans+(lcm*inv)%MOD

    return ans%MOD

if __name__ == "__main__":
    n = int(input())
    a = [(lambda x: int(x))(x) for x in input().split()]
    #MAX_N = max(a)+5
    print(solve(a, n))

Submission status: Wrong Answer

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=LI()
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
lists=[Counter(prime_factorize(lis[i])) for i in range(n)]
C=Counter([])
for i in range(n):
    x=lists[i]
    for j in x.keys():
        C[j]=max(C[j],x[j])
#print(C)

'''ans=0
for i in range(n):
    x=lists[i]
    y=1
    for j in C.keys():
        y=(y*pow(j,C[j]-x[j],mod))%mod
    #print(y%mod)
    ans=(ans+y)%mod
print(ans%mod)'''

Submission status: Wrong Answer

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=LI()
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
lists=[Counter(prime_factorize(lis[i])) for i in range(n)]
'''C=Counter([])
for i in range(n):
    x=lists[i]
    for j in x.keys():
        C[j]=max(C[j],x[j])
#print(C)

ans=0
for i in range(n):
    x=lists[i]
    y=1
    for j in C.keys():
        y=(y*pow(j,C[j]-x[j],mod))%mod
    #print(y%mod)
    ans=(ans+y)%mod
print(ans%mod)'''

Submission status: Wrong Answer

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=LI()
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
lists=[prime_factorize(lis[i]) for i in range(n)]
'''C=Counter([])
for i in range(n):
    x=Counter(lists[i])
    for j in x.keys():
        C[j]=max(C[j],x[j])
#print(C)

ans=0
for i in range(n):
    x=Counter(lists[i])
    y=1
    for j in C.keys():
        y=y*pow(j,C[j]-x[j],mod)
    #print(y%mod)
    ans=(ans+y)%mod
print(ans%mod)'''

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N == 1:
  print(1)
  exit(0)
  
mod = int(1e9+7)

# sqrt(10**6)までの素数を列挙しておく？
def sosu_list(N):
  A = [True] * (N+1)
  A[0] = False
  A[1] = False
  B = []
  for i in range(2,N):
    if not A[i]:
      continue
    if i*i > N:
      break
    B.append(i)
    for j in range(2,N):
      if i*j > N:
        break
      A[i*j] = False
  return B

B = sosu_list(max(A)+1000)
def funcor(D1,D2):
  for k,v in D2.items():
    if k in D1:
      D1[k] = max(D1[k], v)
    else:
      D1[k] = v
  return D1
  
D = {}
for a in A:
  #print(a)
  wk = {}
  for b in B:
    while a%b == 0:
      a /= b
      if b in wk:
        wk[b] += 1
      else:
        wk[b] = 1
  if a > 1:
    wk[a] = 1   
  #print(wk)
  D = funcor(D,wk)

L = 1
for k,v in D.items():
  L *= k**v

"""
#### 
# https://note.nkmk.me/python-gcd-lcm/
from math import gcd
from functools import reduce

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

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
L = lcm_list(A)
print(L)
"""
ans = 0
for a in A:
  ans += L // a
  ans %= mod
  
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N == 1:
  print(1)
  exit(0)
  
mod = int(1e9+7)

# sqrt(10**6)までの素数を列挙しておく？
def sosu_list(N):
  A = [True] * (N+1)
  A[0] = False
  A[1] = False
  B = []
  for i in range(2,N):
    if not A[i]:
      continue
    if i*i > N:
      break
    B.append(i)
    for j in range(2,N):
      if i*j > N:
        break
      A[i*j] = False
  return B

B = sosu_list(max(A))
def funcor(D1,D2):
  for k,v in D2.items():
    if k in D1:
      D1[k] = max(D1[k], v)
    else:
      D1[k] = v
  return D1
  
D = {}
for a in A:
  wk = {}
  for b in B:
    while a%b == 0:
      a /= b
      if b in wk:
        wk[b] += 1
      else:
        wk[b] = 1
  if a > 1:
    wk[a] = 1   
  D = funcor(D,wk)

L = 1
for k,v in D.items():
  L *= k**v

"""
#### 
# https://note.nkmk.me/python-gcd-lcm/
from math import gcd
from functools import reduce

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

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
L = lcm_list(A)
print(L)
"""
ans = 0
for a in A:
  ans += L // a
  ans %= mod
  
print(ans)

Submission status: Wrong Answer

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

mod = 10**9 + 7
MAX = 1_000_000


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


C = [0]*(MAX+1)
primes = gen_primes(MAX)


def prime_fact(n):
    cnt = 0
    for p in primes:
        if n % p:
            continue
        while n % p == 0:
            cnt += 1
            n //= p
        C[p] = max(C[p], cnt)
        cnt = 0
    if n != 1:
        C[n] = 1


for a in A:
    prime_fact(a)

lcm = 1
for i, c in enumerate(C):
    if c:
        lcm = lcm * pow(i, c, mod) % mod

print(lcm)

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

Submission status: Wrong Answer

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

mod = 10**9 + 7
MAX = 1_000_000

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


C = [0]*(MAX+1)
primes = gen_primes(MAX)

def prime_fact(n):
    cnt = 0
    for p in primes:
        if n % p:
            continue
        while n % p == 0:
            cnt += 1
            n //= p
        C[p] = max(C[p], cnt)
        cnt = 0
    if n != 1:
        C[p] = 1

for a in A:
    prime_fact(a)

lcm = 1
for i, c in enumerate(C):
    if c:
        lcm = lcm * pow(i, c, mod) % mod

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

Submission status: Wrong Answer

Solution code:
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[4::2] = False
        self.is_prime[9::3] = False
        self.is_prime[25::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                if i * i < V + 1:
                    self.is_prime[i * i::i] = False
    
    def factorize(self, x):
        assert x >= 1
        if x == 1:
            return [(1, 1)]
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


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

sieve = SieveOfEratosthenes(10**3)
F = [dict(sieve.factorize(a)) for a in A]

lcm = F[0]
for i in range(1, len(F)):
    for p, e in F[i].items():
        if p in lcm:
            lcm[p] = max(lcm[p], e)
        else:
            lcm[p] = e

val = 1
for p, e in lcm.items():
    val = val * pow(p, e, M) % M
print(val)

B = [val * pow(a, M - 2, M) % M for a in A]
print(sum(B) % M)

Submission status: Wrong Answer

Solution code:
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[2::2] = False
        self.is_prime[3::3] = False
        self.is_prime[5::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                if i * i < V + 1:
                    self.is_prime[i * i::i] = False
    
    def factorize(self, x, return_all=False):
        assert x >= 2
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0 or return_all:
                result.append((p, exp))
            if p * p > x and return_all is False:
                break
        if x > 1:
            result.append((x, 1))
        return result


N = int(input())
M = 10**9 + 7
A = list(map(int, input().split()))
num_1 = A.count(1)
A = [a for a in A if a >= 2]

if num_1 == N:
    print(N)
else:
    sieve = SieveOfEratosthenes(10**3)
    F = [sieve.factorize(a, return_all=True) for a in A]

    lcm = F[0]
    for i in range(1, len(F)):
        lcm = [(p, max(e1, e2)) for (p, e1), (_, e2) in zip(lcm, F[i])]

    val = 1
    for p, e in lcm:
        val = val * pow(p, e, M) % M

    B = [val * pow(a, M - 2, M) % M for a in A]
    print((sum(B) + num_1 * val) % M)