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:
from fractions import gcd

n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
lcm = aaa[0]
for a in aaa[1:]:
    g = gcd(lcm, a)
    lcm = lcm * a * pow(g, MOD - 2, MOD)
ans = 0
for a in aaa:
    ra = pow(a, MOD - 2, MOD)
    ans = (ans + lcm * ra) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
  
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()))

ans = 0
MOD = 10**9 + 7
GCD = gcd_list(A)
LCM = lcm_list(A)//GCD


for a in A:
  a == a//GCD
  ans += LCM//a
  ans = ans%MOD
  
print(ans)

Submission status: Wrong Answer

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

P = 10**9 + 7
N = (10**6)+1
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

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


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


mod = 10**9+7
lcm = 1
for i in range(N):
    lcm = (lcm*A[i]) * inv_t[fractions.gcd(A[i], lcm)]

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

print(ans)

Submission status: Wrong Answer

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

N = pow(10,9)+7
def gcd(a,b):
    if a>b:return gcd(b,a)
    while b!=0:
        nb = b%a
        a = b
        b = nb
    return a

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

hcm = arr[0]
for i in range(1,n):
    hcm = lcm(hcm,arr[i])

res = 0
for num in arr:
    res += (hcm/num)
    res%=N

print(int(res))

Submission status: Wrong Answer

Solution code:


def gcd_core(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm_core(a,b):
    g = gcd_core(a,b)
    return (a*b)//g

def lcm(arr):
    m = 10**9+7
    mcnt = 0
    l = lcm_core(arr[0],arr[1])
    for i in range(2,len(arr)):
        l = lcm_core(l,arr[i])
        mcnt += l//m
        l %= m
    return l,mcnt

n = int(input())

if n == 1:
    print(1)
else:
    arr = list(map(int,input().split()))
    l,mcnt = lcm(arr)
    m = 10**9+7
    ans = 0
    for i in range(n):
        temp = l + (m%arr[i])*mcnt
        ans += (temp//arr[i]) + (m//arr[i])*mcnt
        ans %= m
    
    print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce

from sys import stdin

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(stdin.readline())
a = list(map(int, stdin.readline().split()))

l = reduce(lcm, a)

s = 0

MOD = 1000000007

for i in a:
    s += (l // i) % MOD

print(s)

Submission status: Wrong Answer

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

import fractions

k=A[0]

for i in range(N-1):
  l=fractions.gcd(A[i+1],k)
  k=k*A[i+1]//l
print(k)
x=0
for i in range(N):
  x+=k//A[i]
  x=x%1000000007
print(x)

Submission status: Wrong Answer

Solution code:

from fractions import gcd
import random
n = int(input())
a = list(map(int, input().split( )))
random.shuffle(a)
#最小公倍数でよいか？
#全てのjについてAiBiはAjで割り切れる
#計算時間は？

mod =10**9+7
def lcd(x,y):
    g = gcd(x,y)
    return x*y//g

ag1 = 1
for i in range(n//2):
    ag1 = lcd(ag1,a[i])
ag2 = 1
for i in range(n//2,n):
    ag2 = lcd(ag2,a[i])

ag3 = lcd(ag1,ag2)

ans = 0

for i in range(n//2):
    ans += ag1//a[i]
ans*=ag3//ag1
ans %=mod
ans2 = 0
for i in range(n//2,n):
    ans2 += ag2//a[i]
ans2*= ag3//ag2
ans2%=mod 
ans += ans2


print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


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


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


mod = 10**9+7
lcm = 1
for i in range(N):
    lcm = (lcm*A[i]) * modinv(fractions.gcd(lcm, A[i]))

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

n=int((input()))
a=list(map(int,input().split()))
mod=10**9+7
b=0
for i in a:
    b+=(pow(i,mod-2,mod))
    
tmp=b%mod


def gcd(x,y):
    while y!=0:
        x,y=y,x%y
    return x
    
def lcm(x,y):
    G=gcd(x,y)
    return (x)*(y)*pow(G,mod-2,mod)
    
L=a[0]%mod
for i in a:
    L=lcm(L,i)%mod
    

print(L*tmp%mod)

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def power(x, y):
   if y == 0:
       return 1
   elif y == 1:
       return x % mod
   elif y % 2 == 0:
       return power(x, y/2) ** 2 % mod
   else:
       return power(x, (y-1)/2) ** 2 * x % mod

def main():
	N = INT()
	A = LIST()

	tmp = A[0]

	for i in range(1, N):
		tmp = (tmp * A[i])*power(gcd(tmp, A[i]), mod-2)

	B = [tmp//A[i] for i in range(N)]

	ans = 0
	for i in range(N):
		ans = (ans+B[i])%mod
	print(ans)

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

MOD = 10**9+7

def lcm_base(a, b):
    return (a * b) * pow(gcd(a, b), MOD-2, MOD)


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


N = int(input())
A = list(map(int, input().split()))
tmp = lcm(A)
ans = 0
for a in A:
    ans = (ans + tmp // a)%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

n=int((input()))
a=list(map(int,input().split()))
mod=10**9+7
b=[]
for i in a:
    b.append(pow(i,mod-2,mod))
    
tmp=sum(b)%mod


def gcd(x,y):
    while y!=0:
        x,y=y,x%y
    return x
    
def lcm(x,y):
    return (x%mod)*(y%mod)//gcd(x,y)
    
L=a[0]%mod
for i in a:
    L=lcm(L,i%mod)%mod
    


print(L*tmp%mod)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
from fractions import gcd
import fractions
import statistics
import collections
from functools import reduce
import itertools
from collections import defaultdict
import bisect
from fractions import Fraction


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

num = A[0]
AB = list(set(A))
for i in range(1, len(AB)):
    num = num * AB[i] // fractions.gcd(num, AB[i])

ans = 0

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

print(ans)

Submission status: Wrong Answer

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

# 雑な方法
primes = []
for i in range(2, 1001):
    for j in range(2, math.floor(math.sqrt(i))+1):
        if i % j == 0:
            break
    else:
        primes.append(i)

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

cts = Counter()
for a in As:
    x = a
    ct = Counter()
    for p in primes:
        if p > x:
            break
        while x % p == 0:
            x //= p
            ct[p] += 1
    for k, v in ct.items():
        ctsk = cts[k]
        cts[k] = ctsk if ctsk >= v else v

ans = 1
for k, v in cts.items():
    ans *= pow(k, v, MOD)
    ans %= MOD

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

Submission status: Wrong Answer

Solution code:
def findDivisor(num):
    # 2,3 are the most common divisor for many numbers hence I go by divisor of 2,3
    # if not then by the same number as divisor
    if num%2 == 0:
        return 2
    elif num%3==0:
        return 3
    return num

def findLCM(lcmArray):
    lcm = 1
    while len(lcmArray) > 0:
        minOfLCMArray = min(lcmArray)
        divisor = findDivisor(minOfLCMArray)        

        for x in range(0, len(lcmArray)):
            Quotient = lcmArray[x]//divisor
            Reminder = lcmArray[x]%divisor
            if Reminder == 0:
                lcmArray[x] = Quotient

        lcm*=divisor
        minOfLCMArray = min(lcmArray)
        if minOfLCMArray == 1:
            lcmArray.remove(minOfLCMArray)
    return lcm

n = input()
a = input().split()
a = [int(i) for i in a]
b = a[:]

lcm = findLCM(a)

count = 0
for i in b:
    count += (lcm // i)
    count %= 1000000007

print (count)

Submission status: Wrong Answer

Solution code:
def LCM(arr, n): 
      
    # Find the maximum value in arr[] 
    max_num = 0; 
    for i in range(n): 
        if (max_num < arr[i]): 
            max_num = arr[i]; 
  
    # Initialize result 
    res = 1; 

  
    x = 2; # Current factor. 
    while (x <= max_num): 

          
        indexes = []; 
        for j in range(n): 
            if (arr[j] % x == 0): 
                indexes.append(j); 

  
        if (len(indexes) >= 2): 

              
            for j in range(len(indexes)): 
                arr[indexes[j]] = int(arr[indexes[j]] / x); 
  
            res = res * x; 
        else: 
            x += 1;
    for i in range(n): 
        res = res * arr[i]; 
  
    return res; 

n=int(input())
l=[int(x) for x in input().split()]
if(n==1):
        print(1)
else:
        lcm=LCM(l,n)
        k=0
        for i in l:
                k=(k+lcm//i)%(10**9+7)
        print(k)

Submission status: Wrong Answer

Solution code:
N=int(input())
a = list(map(int, input().split()))
import fractions
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
import numpy as np
aa = np.array(a)
print(sum((ans//aa)%(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)


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

    AN_lcm = lcm_list(AN) % 10**9 + 7

    ans = 0
    for A in AN:
        ans += AN_lcm // A
        ans %= 10**9 + 7

    print(ans)


main()

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

ans = 0
MOD = 10**9 + 7
LCM = lcm_list(A)

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

Submission status: Wrong Answer

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

def GCD(x,y):
    if y==0:
        return x
    return GCD(y,x%y)
lcm = 1
for i in A:
    lcm = lcm*i*pow(GCD(lcm,i),MOD-2,MOD)
ans = 0
for i in A:
    ans += lcm*pow(i,MOD-2,MOD)
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
from fractions import gcd
MOD = 10**9 + 7

n = int(input())
a = [int(item) for item in input().split()]


lcm = 1
for item in a:
    lcm = lcm * item * pow(gcd(lcm, item), MOD-2, MOD)
    lcm %= MOD

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = np.array(read().split(),np.int64)

MOD = 10 ** 9 + 7

U = 10 ** 6 + 10
is_prime = np.zeros(U, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
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

for x in A.tolist():
    lcm *= x
    lcm %= MOD

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

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = np.array(read().split(),np.int32)

MOD = 10 ** 9 + 7

U = 10 ** 6 + 10
is_prime = np.zeros(U, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
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

for x in A.tolist():
    lcm *= x
    lcm %= MOD

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


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

#solve
def solve():
    n = II()
    a = LI()
    lcm_ = lcm(a)
    ans = 0
    for i in a:
        ans += lcm_ * pow(i, mod-2, mod)
        ans %= mod
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce


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


def main():
    _ = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    a_lcm = reduce(lcm, a)
    print(sum([(a_lcm // aa) % mod for aa in a]) % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

def main():
    MOD = 10 ** 9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    prime = [True] * (a[-1] + 1)
    prime[0] = False
    prime[1] = False
    for i in range(len(prime)):
        if prime[i] == False:
            continue
        j = i * 2
        while j <= a[-1]:
            prime[j] = False
            j += i
    lst = []
    for i, v in enumerate(prime):
        if v:
            lst.append([i, 0])
    for i in a:
        for j, v in enumerate(lst):
            c = 0
            while i >= v[0]:
                if i % v[0] != 0:
                    break
                i //= v[0]
                c += 1
            if lst[j][1] < c:
                lst[j][1] = c
    ans = 0
    for i in a:
        d = 1
        for j, v in enumerate(lst):
            c = 0
            while i >= v[0]:
                if i % v[0] != 0:
                    break
                i //= v[0]
                c += 1
            d *= v[0] ** (v[1] - c) % MOD
        ans = (ans + d) % MOD
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

ps = []
for i in range(2, 1000):
    is_p = True
    for j in range(2, i):
        if i % j == 0:
            is_p = False
            break
    if is_p:
        ps.append(i)

def factorization(n):
    arr = defaultdict(int)
    temp = n
    for i in ps:
        if i > int(-(-n**0.5//1))+1:
            break
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt
    if temp!=1:
        arr[temp] = 1
    if arr==[]:
        arr[n] = 1
    return arr


aa = defaultdict(int)

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

fs = [[]] * 1000001
for i in a:
    if not fs[i]:
        fs[i] = factorization(i)

for i in a:
    for k, v in fs[i].items():
        aa[k] = max(aa[k], v)


mod = 10 ** 9 + 7
ans = 0
for i in a:
    t = 1
    for k, v in aa.items():
        t = (t * k ** (v - fs[i][k])) % mod
    ans = (ans + t) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p

P = eratosthenes(10**6+1)

@mt
def slv(N, A):
    c = Counter()
    for a in A:
        for p in P:
            t = 0
            while a % p == 0:
                t += 1
                a //= p
            if t > 0:
                c[p] = max(c[p], t)
            if a == 1:
                break

    M = Mod(10**9+7)
    L = 1
    for k, v in c.items():
        L = M.mul(L, M.pow(k, v))

    ans = 0
    for a in A:
        ans = M.add(ans, M.div(L, a))

    return ans




def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p

P = eratosthenes(10**6+1)

@mt
def slv(N, A):
    c = Counter()
    for a in A:
        for p in P:
            t = 0
            while a % p == 0:
                t += 1
                a //= p
            if t > 0:
                c[p] = max(c[p], t)

    M = Mod(10**9+7)
    L = 1
    for k, v in c.items():
        L = M.mul(L, M.pow(k, v))

    ans = 0
    for a in A:
        ans = M.add(ans, M.div(L, a))

    return ans




def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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


prime = [0] * (10**6 + 1)
for i in range(N):
    c = Counter(prime_factorize(A[i]))
    for j in c.items():
        prime[j[0]] = max(j[1], prime[j[0]])
lcm = 1
for i in range(10**6):
    if prime[i] > 0:
        lcm *= pow(i, prime[i], MOD)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import chain
import numpy as np
from collections import Counter
import time


MOD = 1000000007  # type: int


def factorize(n: int):
    """nを素因数分解する"""
    # 2
    count = 0
    while n % 2 == 0:
        count += 1
        n = n // 2
    if count > 0:
        arr = [(2, count)]
    else:
        arr = []

    # 3 以降
    for facter in range(3, n + 1, 2):
        if facter * facter > n:
            if n > 1:
                arr.append((n, 1))
            break
        count = 0
        while n % facter == 0:
            count += 1
            n = n // facter
        if count > 0:
            arr.append((facter, count))

    return Counter(dict(arr))


def solve(N: int, A: "List[int]"):
    max_factor = Counter()
    for a in A:
        factor = factorize(a)
        max_factor = max_factor | factor
    gcm = 1
    for prime, count in max_factor.items():
        gcm = (gcm * prime**count)
    answer = 0
    for a in A:
        answer = (answer + gcm // a) % MOD
    return answer


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    answer = solve(N, A)
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from typing import List, Counter, Tuple
from collections import Counter
from itertools import permutations


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))

def lcd(a):
    if len(a) == 1:
        return a[0]
    mid = len(a)//2
    c, d = lcd(a[:mid]), lcd(a[mid:])
    return c*d//math.gcd(c, d)


def solve() -> int:
    modulo = 10**9+7
    N = read_int()
    A = read_ints()
    l = lcd(A)
    return sum((l//a)%modulo for a in A)%modulo


if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
import math
from typing import List, Counter, Tuple
from collections import Counter
from itertools import permutations


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> int:
    modulo = 10**9+7
    N = read_int()
    A = read_ints()
    lcd = 1
    for a in A:
        lcd = a*lcd//math.gcd(a, lcd)
    return sum((lcd//a)%modulo for a in A)%modulo


if __name__ == '__main__':
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from itertools import chain
import numpy as np
from collections import Counter

MOD = 1000000007  # type: int


def factorize(n: int):
    """nを素因数分解する"""
    # 2
    count = 0
    while n % 2 == 0:
        count += 1
        n = n // 2
    if count > 0:
        arr = [(2, count)]
    else:
        arr = []

    # 3 以降
    for facter in range(3, n + 1, 2):
        if facter * facter > n:
            if n > 1:
                arr.append((n, 1))
            break
        count = 0
        while n % facter == 0:
            count += 1
            n = n // facter
        if count > 0:
            arr.append((facter, count))

    return Counter(dict(arr))


def solve(N: int, A: "List[int]"):
    factors = []
    max_factor = Counter()
    for a in A:
        factor = factorize(a)
        max_factor = max_factor | factor
        factors.append(factor)
    ans = 0
    for factor in factors:
        n = 1
        for prime, count in (max_factor - factor).items():
            n = (n * prime ** count) % MOD
        ans = (ans + n) % MOD
    return ans


def main():
    tokens = chain(*(line.split() for line in sys.stdin))
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    answer = solve(N, A)
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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_lcm = 1
for i in range(n):
    a_lcm = a_lcm * a[i] // math.gcd(a_lcm, a[i])

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

print(b_sum)

Submission status: Time Limit Exceeded

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_lcm = 1
for i in range(n):
    a_lcm = lcm(a_lcm, a[i])

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

print(b_sum)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def factorization(n):
    '''
    [base,power]のリストを返す
    '''
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i,cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n,1])

    return arr

def factorization_d(n):
    '''
    [base,power]のリストを返す
    '''
    d = defaultdict(int)
    temp = n
    for i in range(2, int(n**0.5) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            d[i] = cnt
    if temp!=1:
        d[temp] = 1
    if len(d) == 0:
        d[n] = 1

    return d
N = int(input())
a_ls = list(map(int, input().split()))

i_d = defaultdict(lambda: {})
Ld = defaultdict(int)
for i,a in enumerate(a_ls):
    arr = factorization_d(a)
    i_d[i] = arr
    # これ素因数分解に組み込むのはあり
    for base,power in arr.items():
        Ld[base] = max(Ld[base],power)

mod = 10**9+7
ans = 0
for i,a in enumerate(a_ls):
    b = 1
    d_a = i_d[i]
    for base,power in Ld.items():
        b *= base**(power - d_a[base])
        b %= mod
    #print(b)
    ans += b
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def factorization(n):
    '''
    [base,power]のリストを返す
    '''
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i,cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr == []:
        arr.append([n,1])

    return arr

def factorization_d(n):
    '''
    [base,power]のリストを返す
    '''
    d = defaultdict(int)
    temp = n
    for i in range(2, int(n**0.5) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            d[i] = cnt
    if temp!=1:
        d[temp] = 1
    if arr == []:
        d[n] = 1

    return d
N = int(input())
a_ls = list(map(int, input().split()))

d = defaultdict(int)
for a in a_ls:
    arr = factorization(a)
    for base,power in arr:
        d[base] = max(d[base],power)

mod = 10**9+7
ans = 0
for a in a_ls:
    b = 1
    d_a = factorization_d(a)
    for base,power in d.items():
        b *= base**(power - d_a[base])
        b %= mod
    #print(b)
    ans += b
    ans %= mod
print(ans)