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: Time Limit Exceeded

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

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

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

_lcm = 1
for a in A:
    _lcm = lcm(a, _lcm)

ret = 0
for a in A:
    ret += (_lcm // a)
    ret %= MODE

print(ret)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
if n == 1:
	print(1)
else:
	lcm = a[0] * a[1] // gcd(a[0], a[1])
	for x in a[2:]:
		lcm = lcm * x // gcd(lcm, x)
	print(sum([(lcm//x)%MOD for x in a])%MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
if n == 1:
	print(1)
else:
	lcm = a[0] * a[1] // gcd(a[0], a[1])
	for x in a[2:]:
		lcm = lcm * x // gcd(lcm, x)
	ans = 0
	for x in a:
		ans += lcm // x
		ans %= MOD
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

MOD = 10 ** 9 + 7

# 素因数分解
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n ** 0.5 // 1)) + 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

counter = defaultdict(int)
p_list = []
for a in A:
  for p, r in factorization(a):
    if counter[p] == 0:
      p_list.append(p)
    counter[p] = max(counter[p], r)
lcm = 1
  
answer = 0
for a in A:
  counter_a = defaultdict(int)
  for p, r in factorization(a):
    counter_a[p] += r
  tmp = 1
  for p in p_list:
     tmp = (tmp * pow(p, (counter[p] - counter_a[p]), MOD)) % MOD
  answer = (answer + tmp) % MOD

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

MOD = 10 ** 9 + 7

# 素因数分解
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n ** 0.5 // 1)) + 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

counter = defaultdict(int)
p_list = []
for a in A:
  for p, r in factorization(a):
    if counter[p] == 0:
      p_list.append(p)
    counter[p] = max(counter[p], r)
lcm = 1
  
answer = 0
for a in A:
  counter_a = defaultdict(int)
  for p, r in factorization(a):
    counter_a[p] += r
  tmp = 1
  for p in p_list:
     tmp = (tmp * p ** (counter[p] - counter_a[p])) % MOD
  answer = (answer + tmp) % MOD

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from math import *
from collections import defaultdict

MAX_Ai = 10**6
MAX_PRIME = ceil(sqrt(MAX_Ai))
MODE = 10**9+7

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


def get_prime():
    # prime table
    ptb = [True] * MAX_PRIME
    ptb[0] = ptb[1] = False

    for i in range(2, ceil(sqrt(MAX_PRIME)) + 1):
        for j in range(i*2, MAX_PRIME, i):
            ptb[j] = False

    P = [ i for i, v in enumerate(ptb) if v == True]

    return P

def prime_factorization(n, P):
    factor = defaultdict(int)
    for p in P:
        while n % p == 0:
            factor[p] += 1
            n //= p

    if n != 1:
        factor[n] += 1

    return factor

def main():
    P = get_prime()    

    A_fact = list()
    lcm = defaultdict()
    for a in A:
        a_fact = prime_factorization(a, P)
        A_fact.append(a_fact)
        for prime, power in a_fact.items():
            if prime not in lcm:
                lcm[prime] = power
            else:
                if lcm[prime] < power:
                    lcm[prime] = power

    ret = 0
    for a_fact in A_fact:
        b_fact = {key: lcm[key] - a_fact.get(key, 0) for key in lcm.keys()}
        tmp = 1
        for prime, power in b_fact.items():
            tmp *= prime**power
            tmp %= MODE
        ret += tmp
        ret %= MODE

    print(ret)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

def main():
    MOD = 1000000007
    N = int(input())
    A = list(map(int, input().split()))
    lc = 1
    for i in A:
        lc = lcm(lc, i)
        ans = 0
    for i in A:
        ans += lc // i
    print(ans%MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

MOD = 1000000007

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

def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    lc = 1
    for i in A:
        lc = lcm(lc, i)
        ans = 0
    for i in A:
        ans += lc // i
    print(ans%MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

MOD = 1000000007

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

N = int(input())
A = [int(x) for x in input().split()]
lc = 1
for i in A:
    lc = lcm(lc, i)
ans = 0
for i in A:
    ans = (ans + lc // i) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b) :
    if a < b :
        return gcd(b,a)
    r = 0;
    while a % b != 0 :
        r = a % b
        a = b
        b = r
    return b


N = int(input())
A = [int(i) for i in input().split()]
lcm = 1
for i in range(N) :
    lcm = lcm * A[i] / gcd(lcm, A[i])
ans = 0;
for i in range(N) :
    ans += lcm / A[i]
    ans %= 1000000007
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def lcm_list(A):
    l = A[0]
    for a in A[1:]:
        l = lcm(l, a)
    return l

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
L = lcm_list(A)
ans = 0
for a in A:
    ans = (ans + L // a) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

def lcm_list(A):
    l = A[0]
    for a in A[1:]:
        l = lcm(l, a)
    return l

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
L = lcm_list(A)
ans = 0
for a in A:
    ans = (ans + L // a) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

MOD = 10 ** 9 + 7

# 素因数分解
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n ** 0.5 // 1)) + 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

counter = defaultdict(int)
p_list = []
for a in A:
  for p, r in factorization(a):
    if counter[p] == 0:
      p_list.append(p)
    counter[p] = max(counter[p], r)
lcm = 1
for p in p_list:
  lcm *= pow(p, counter[p])
  
answer = 0
for a in A:
  answer = (answer + lcm // a) % MOD

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
from fractions import gcd
def lcm(x,y):
  return x * y // gcd(x,y)
def list_gcd(list):
    c=list[0]
    for i in list:
        c=gcd(c,i)
    return c
def list_lcm(list):
  c=1
  for i in list:
    c=lcm(c,i)
  return c
g=list_gcd(a)
a = [i//g for i in a]
l=list_lcm(a)
a = [l // i % mod for i in a]
#print(a)
print(sum(a)%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def factorization(n):
    dict = defaultdict(int)
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            dict[i] = cnt
    if temp != 1:
        dict[temp] = 1
    if not dict:
        dict[n] = 1
    return dict


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

prime_factors = defaultdict(int)
factors = []

for a in A:
    a_factors = factorization(a)
    for prime, count in a_factors.items():
        prime_factors[prime] = max(count, prime_factors[prime])
    factors.append(a_factors)

ans = 0
for a, div_factors in zip(A, factors):
    num = 1
    for prime, count in prime_factors.items():
        dived_count = count - div_factors[prime]
        num *= pow(prime, dived_count, mod)
    ans += num % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
from fractions import gcd
def lcm(x,y):
  return x * y // gcd(x,y)
def list_gcd(list):
    c=list[0]
    for i in list:
        c=gcd(c,i)
    return c
def list_lcm(list):
  c=1
  for i in list:
    c=lcm(c,i)
  return c

a = [i//list_gcd(a) for i in a]
a = [list_lcm(a) // i % mod for i in a]

print(sum(a)%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

MOD = 10 ** 9 + 7

# 素因数分解
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n ** 0.5 // 1)) + 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

counter = defaultdict(int)
p_list = []
for a in A:
  for p, r in factorization(a):
    if counter[p] == 0:
      p_list.append(p)
    counter[p] = max(counter[p], r)
lcm = 1
for p in p_list:
  lcm *= p ** counter[p]
  
answer = 0
for a in A:
  answer = (answer + lcm // a) % MOD

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def factorization(n):
    dict = defaultdict(int)
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            dict[i] = cnt

    if temp != 1:
        dict[temp] = 1

    if not dict:
        dict[n] = 1

    return dict


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

prime_factors = defaultdict(int)
factors = []

for a in A:
    a_factors = factorization(a)
    for prime, count in a_factors.items():
        prime_factors[prime] = max(count, prime_factors[prime])
    factors.append(a_factors)

B = []
for a, div_factors in zip(A, factors):
    num = 1
    for prime, count in prime_factors.items():
        dived_count = count - div_factors[prime]
        num *= prime ** dived_count
    B.append(num)

print(sum(B)%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def factorization(n):
    dict = defaultdict(int)
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            dict[i] = cnt

    if temp != 1:
        dict[temp] = 1

    if not dict:
        dict[n] = 1

    return dict


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

prime_factors = defaultdict(int)
factors = []

for a in A:
    a_factors = factorization(a)
    for prime, count in a_factors.items():
        prime_factors[prime] = max(count, prime_factors[prime])
    factors.append(a_factors)

B = []
for a, div_factors in zip(A, factors):
    num = 1
    for prime, count in prime_factors.items():
        dived_count = count - div_factors[prime]
        num *= prime ** dived_count
        num %= mod
    B.append(num)

print(sum(B)%mod)

Submission status: Time Limit Exceeded

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

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

lcm = 1
for v in a:
    lcm = lcm * v // gcd(lcm, v)

MOD = 1000000007
ans = 0
for v in a:
    ans += lcm // v
    ans %= MOD;

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

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

INF=10**9+7

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

temp=A[0]
for i in range(1,N):
    temp=lcm(temp,A[i])

ans=0
for a in A:
    ans+=(temp//a)%INF

print(ans%INF)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


def main():
    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])

    print(sum([l // a for a in A]) % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


def main():
    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])

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
P = 10**9 + 7
N = 1000001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
n=int(input())
a=list(map(int,input().split()))
lcm=a[0]
mod=10**9+7
for i in range(1,n):
  lcm=(lcm//gcd(lcm,a[i]))*(a[i]//gcd(lcm,a[i]))*gcd(lcm,a[i])
ans=0
for i in range(n):
  ans+=lcm*inv[a[i]]%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import numpy as np


mod = 10 ** 9 + 7

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


n = int(input())
A = np.array(list(map(int, input().split())), dtype=np.uint64)

num = 1
for a in A:
    num = lcm(num, a)

B = np.array(num // A).astype('int64')
print(sum(B)%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
lcm = A[0]
for i in range(1,N):
    lcm = (lcm*A[i])//gcd(lcm,A[i])

MOD = 10**9+7
ans = 0
for a in A:
    b = lcm//a
    ans += b
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def factorize(n: int) -> dict:
    f = defaultdict(int)
    while n % 2 == 0:
        f[2] += 1
        n //= 2
    p = 3
    while p * p <= n:
        while n % p == 0:
            f[p] += 1
            n //= p
        p += 2
    if n != 1:
        f[n] += 1
    return f


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

a_fac = []
lcm_fac = defaultdict(int)
for i in range(n):
    a_fac.append(factorize(a[i]))
    for k, v in a_fac[i].items():
        lcm_fac[k] = max(lcm_fac[k], v)

# print(lcm_fac)
ans = 0
for i in range(n):
    b_i = 1
    for k, v in lcm_fac.items():
        b_i *= pow(k, v - a_fac[i][k], MOD)
        b_i %= MOD
    # print(i, a[i], b_i)
    ans += b_i
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
P = 10**9 + 7
N = 1000001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]
n=int(input())
a=list(map(int,input().split()))
lcm=a[0]
mod=10**9+7
for i in range(1,n):
  lcm=(lcm//gcd(lcm,a[i]))*(a[i]//gcd(lcm,a[i]))*gcd(lcm,a[i])
ans=0
for i in range(n):
  ans+=lcm*inv[a[i]]%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from functools import reduce
import fractions
 
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())

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

lcm = lcm_list(inp_list)

ans = 0

for i in inp_list:
    ans += lcm // i


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

Submission status: Time Limit Exceeded

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

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

a1 = a[0]
mod_sum = 0
mod1 = 1
for i,name in enumerate(a[1:]):
    b1 = name
    ab1 = lcm(a1, b1)
    mod1 =  (mod1*(ab1//a1) + (ab1//b1))%mod
    a1 = copy.deepcopy(ab1)

print(mod1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = map(int, input().split())
Alist = list(map(int, input().split()))
import fractions
from functools import reduce


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


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


lcm_a = lcm_list(Alist)
mod = 10**9 + 7
ans = 0

for a in Alist:
    ans += (lcm_a // a)
    ans %= mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = map(int, input().split())
Alist = list(map(int, input().split()))
import fractions
from functools import reduce


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


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


lcm_a = lcm_list(Alist)
mod = 10**9 + 7
ans = 0

for a in Alist:
    ans += (lcm_a // a)
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

def gcd_list(list1):
    ans=list1[0]
    for i in range(len(list1)):
        ans=fractions.gcd(ans,list1[i])
    return ans
#リスト内の最大公約数を求める

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

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

large_num = 10**9+7
N = int(input())
A = list(map(int,input().split()))
ans = A[0]
for i in range(1,N):
    ans = ans * A[i] // fractions.gcd(ans,A[i])
lcm_all = ans
result = 0
for num in A:
    result += lcm_all//num
print(result%large_num)

Submission status: Time Limit Exceeded

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


lcm_a = lcm_list(Alist)
mod = 10**9 + 7
ans = 0

for a in Alist:
    ans += (lcm_a // a)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import functools
import fractions
MOD = 10**9+7


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


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


def main():
    n = int(input())
    x = list(map(int, input().split()))

    l = lcm(x)
    ans = 0
    for i in range(n):
        ans += l // x[i]
        ans %= MOD

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def mod_add(a, b, mod):
    return (a + b) % mod

def mod_mul(a, b, mod):
    return a * b % mod

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

def mod_div(a, b, mod):
    return mod_mul(a, mod_power(b, mod-2, mod), mod)

def factor(n):
    ans = []
    i = 0
    while n & 1 == 0:
        n >>= 1
        i += 1

    if i > 0:
        ans.append((2, i))

    for i in range(3, int(n**.5) +1, 2):
        x, y = divmod(n, i)

        if y == 0:
            j = 1
            x1 = x
            while True:
                x1, y = divmod(x, i)
                if y == 0:
                    x = x1
                    j += 1
                else:
                    ans.append((i, j))
                    break
            n = x

    if n > 1:
        ans.append((n, 1))
    return ans

def resolve():
    N = int(input())
    A = list(iim())
    mod = 10**9 + 7

    c = 1
    c2 = dict()
    for a in A:
        for n, m in factor(a):
            if n in c2:
                if c2[n] < m:
                    c2[n] = m
            else:
                c2[n] = m

    c3 = 1
    for n, m in c2.items():
        c3 *= n**m%mod % mod

    s = 0
    for a in A:
        s = mod_add(s, mod_div(c3, a, mod), mod)

    print(s)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def mod_add(a, b, mod):
    return (a + b) % mod

def mod_mul(a, b, mod):
    return a * b % mod

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

def mod_div(a, b, mod):
    return mod_mul(a, mod_power(b, mod-2, mod), mod)

def factor(n):
    ans = []
    i = 0
    while n & 1 == 0:
        n >>= 1
        i += 1

    if i > 0:
        ans.append((2, i))

    for i in range(3, int(n**.5) +1, 2):
        x, y = divmod(n, i)

        if y == 0:
            j = 1
            x1 = x
            while True:
                x1, y = divmod(x, i)
                if y == 0:
                    x = x1
                    j += 1
                else:
                    ans.append((i, j))
                    break
            n = x

    if n > 1:
        ans.append((n, 1))
    return ans

def resolve():
    N = int(input())
    A = list(iim())
    mod = 10**9 + 7

    c = 1
    c2 = dict()
    for a in A:
        for n, m in factor(a):
            if n in c2:
                c2[n] = max(c2[n], m)
            else:
                c2[n] = m

    c3 = 1
    for n, m in c2.items():
        c3 *= n**m%mod % mod

    s = 0
    for a in A:
        s = mod_add(s, mod_div(c3, a, mod), mod)

    print(s)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

def mul(C1, C2):
    return C1 + C2

def div(C1, C2):
    return C1 - C2

def gcd(C1, C2):
    return C1 & C2

def lcm(C1, C2):
    res = C1.copy()
    for k, v in C2.items():
        res[k] = max(C1[k], v)
    return res
    # return C1 | C2

N = INT()
A = LIST()

# 素因数の状態で全体のLCMを出す
A2 = [factorize(a) for a in A]
l2 = Counter()
for a in A2:
    l2 = lcm(l2, a)

# 通常の値に戻す
l = 1
for k, v in l2.items():
    l *= pow(k, v, MOD)
    l %= MOD

ans = 0
for a in A:
    ans += fermat(l, a, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

def mul(C1, C2):
    return C1 + C2

def div(C1, C2):
    return C1 - C2

def gcd(C1, C2):
    return C1 & C2

def lcm(C1, C2):
    return div(mul(C1, C2), gcd(C1, C2))

N = INT()
A = LIST()

# 素因数の状態で全体のLCMを出す
A2 = [factorize(a) for a in A]
l2 = Counter()
for a in A2:
    l2 = lcm(l2, a)

# 通常の値に戻す
l = 1
for k, v in l2.items():
    l *= pow(k, v, MOD)
    l %= MOD

ans = 0
for a in A:
    ans += fermat(l, a, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

MOD = 10 ** 9 + 7

primes = defaultdict(int)

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

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

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
import fractions 
import math
from functools import reduce
#最大公約数
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

#インプット
n = int(input())
a = list(map(int,input().split()))

#最大公約数算出
z=lcm_list(a)

print(sum([z//x for x in a])%((10**9)+7))

Submission status: Time Limit Exceeded

Solution code:
import fractions 
import math
from functools import reduce

#最大公約数
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

#インプット
n = int(input())
a = list(map(int,input().split()))

print(sum([(lcm_list(a))//x for x in a])%((10**9)+7))

Submission status: Time Limit Exceeded

Solution code:
import fractions 
import math
from functools import reduce
#最大公約数
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

#インプット
n = int(input())
a = list(map(int,input().split()))

#最大公約数算出
z=lcm_list(a)

print(sum([z//x for x in a])%((10**9)+7))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

def mul(C1, C2):
    return C1 + C2

def div(C1, C2):
    return C1 - C2

def gcd(C1, C2):
    return C1 & C2

def lcm(C1, C2):
    return C1 | C2

N = INT()
A = LIST()

# 素因数の状態で全体のLCMを出す
A2 = [factorize(a) for a in A]
l2 = Counter()
for a in A2:
    l2 = lcm(l2, a)

# 通常の値に戻す
l = 1
for k, v in l2.items():
    l *= pow(k, v, MOD)
    l %= MOD

ans = 0
for a in A:
    ans += fermat(l, a, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

n=int(input())
a=list(map(int,input().split()))
mod = 10**9+7
c1=a[0]
res = 1
for i in range(1,n):
    c2=(c1*a[i])//gcd(c1,a[i])
    res = (res*(c2//c1))%mod+c2//a[i]
    res %= mod
    c1=c2
print(res)