Problem: 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).

Submission attempts (in order):
from itertools import groupby
from collections import Counter


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 = 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()


from math import sqrt
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))

def insuu(N):
  ret = {}
  for i in range(2,int(sqrt(N)+10)):
    if i > 3 and (i%2 == 0 or i%3 == 0):
      continue
    if N%i == 0:
      ret[i] = 1
      N /= i
    while N%i == 0:
      ret[i] += 1
      N /= i
  if N>1:
    ret[N] = 1
  return ret
   
#for a in A:

  

work = insuu(A[0])
for i in range(1,N):
  now = insuu(A[i])
  for k,v in work.items():
    if k in now and now[k] > v:
      work[k] = now[k]
  for k,v in now.items():
    if not k in work:
      work[k] = v
    
#print(work)


ans = 0
mod = int(1e9+7)

for a in A:
  B = 1
  now = insuu(a)
  for k,v in work.items():
    if k in now:
      B = B * k ** (v - now[k]) % mod
    else:
      B = B * k ** v % mod
  ans = (ans + B) % mod
  
print(ans)

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)

from itertools import groupby
from collections import Counter


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 = 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()


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted