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:
import collections
import math
n = int(input())
ai = [int(i) for i in input().split()]

mod = 10**9+7

if n == 1:
    print(1)
    exit()
    
    
# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor


dic = {}
for a in ai:
    pr = prime(a)
    for num, count in pr.items():
        if not num in dic.keys():
            dic[num] = count
        else:
            if dic[num] < count:
                dic[num] = count

kari = 1
for num,count in dic.items():
    kari *= pow(num,count,mod)

kari_old = kari
ans = 0

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    pr = prime(ai[i])
    #kari = 1
    #for j in range(kosu):
    #kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    for num,count in pr.items():
        kari *= pow(pow(num,count,mod),mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
    #print(ans)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
import numpy as np
n = int(input())
ai = [int(i) for i in input().split()]

mod = 10**9+7

if n == 1:
    print(1)
    exit()
    
    
# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor


dic = {}
for a in ai:
    pr = prime(a)
    for num, count in pr.items():
        if not num in dic.keys():
            dic[num] = count
        else:
            if dic[num] < count:
                dic[num] = count

kari = 1
for num,count in dic.items():
    kari *= pow(num,count,mod)

kari_old = kari
ans = 0

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    pr = prime(ai[i])
    #kari = 1
    #for j in range(kosu):
    #kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    for num,count in pr.items():
        kari *= pow(pow(num,count,mod),mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
    #print(ans)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
n = int(input())
ai = [int(i) for i in input().split()]

num = 10**6+1

mod = 10**9+7

if n == 1:
    print(1)
    exit()
    
"""    
def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
"""
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

def prime_factorize(n,sieve):
    P = []
    while n != 1:
        #print(sieve[n],n)
        if sieve[n] == 1:
            P.append(n)
            break
        else:
            P.append(sieve[n])
            n //= sieve[n]
    return P
"""
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
"""
pri_li = []

#prime,sieve = primes(num)

for i in range(n):
    pri_li.append(collections.Counter(prime(ai[i])))
com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(num)]
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

kari = 1

for j in range(kosu):
    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)

kari_old = kari

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    #kari = 1
    #for j in range(kosu):
    #    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    for j in keys:
        kari *= pow(pow(j,pri_li[i][j],mod),mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
n = int(input())
ai = [int(i) for i in input().split()]

num = 10**6+1

mod = 10**9+7

if n == 1:
    print(1)
    exit()
    
"""    
def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
"""
def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i] == 1:
            P.append(i)
            for j in range(2*i, N+1, i):
                sieve[j] = i
    return P,sieve

def prime_factorize(n,sieve):
    P = []
    while n != 1:
        #print(sieve[n],n)
        if sieve[n] == 1:
            P.append(n)
            break
        else:
            P.append(sieve[n])
            n //= sieve[n]
    return P
"""
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
"""
pri_li = []

prime,sieve = primes(num)

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i],sieve)))
com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(num)]
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

kari = 1

for j in range(kosu):
    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)

kari_old = kari

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    #kari = 1
    #for j in range(kosu):
    #    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    for j in keys:
        kari *= pow(pow(j,pri_li[i][j],mod),mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import math
import numpy as np
n = int(input())
ai = [int(i) for i in input().split()]

num = 10**6+1

mod = 10**9+7

if n == 1:
    print(1)
    exit()
    
"""    
def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
"""
def primes(N):
    sieve = [1]*(N+1)
    sieve[:2] = [0, 0]
    P = []
    for i in range(2, N+1):
        if sieve[i] == 1:
            P.append(i)
            for j in range(2*i, N+1, i):
                sieve[j] = i
    return P,sieve

def prime_factorize(n,sieve):
    P = []
    while n != 1:
        #print(sieve[n],n)
        if sieve[n] == 1:
            P.append(n)
            break
        else:
            P.append(sieve[n])
            n //= sieve[n]
    return P
"""
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
"""
pri_li = []

prime,sieve = primes(num)

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i],sieve)))
com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(num)]
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

kari = 1

for j in range(kosu):
    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)

kari_old = kari

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    #kari = 1
    #for j in range(kosu):
    #    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    for j in keys:
        kari *= pow(pow(j,pri_li[i][j],mod),mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
mod=10**9+7
def lcm(a,b):
  s=fractions.gcd(a,b)
  return a*b//s

n=int(input())
a=list(map(int,input().split()))
l=a[0]
for i in a:
  l=lcm(l,i)
ans=0
for j in a:
  ans=(ans+l//j)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
ai = [int(i) for i in input().split()]

num = 10**6+1

mod = 10**9+7

if n == 1:
    print(1)
    exit()

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

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(num)]
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

kari = 1

for j in range(kosu):
    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)

kari_old = kari

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    #kari = 1
    #for j in range(kosu):
    #    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    for j in keys:
        kari *= pow(pow(j,pri_li[i][j],mod),mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import collections
import copy

n = int(input())
ai = [int(i) for i in input().split()]

num = 10**6+1

mod = 10**9+7

if n == 1:
    print(1)
    exit()

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

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(num)]
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

kari = 1

for j in range(kosu):
    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)

kari_old = kari

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    #kari = 1
    #for j in range(kosu):
    #    kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    for j in keys:
        kari *= pow(pow(j,pri_li[i][j],mod),mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import collections
import copy

n = int(input())
ai = [int(i) for i in input().split()]

num = 10**6+1

mod = 10**9+7

if n == 1:
    print(1)
    exit()

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

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(num)]
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

for i in range(n):
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    kari = 1
    for j in range(kosu):
        kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    for j in keys:
        kari *= pow(pow(j,pri_li[i][j],mod),mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import collections
import copy

n = int(input())
ai = [int(i) for i in input().split()]

num = 10**6+1

mod = 10**9+7

if n == 1:
    print(1)
    exit()

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

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(num)]
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

for i in range(n):
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    for j in keys:
        com_ab[j] -= pri_li[i][j]
    kari = 1
    for j in range(kosu):
        kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    ans += kari
    ans %= mod
    for j in keys:
        com_ab[j] += pri_li[i][j]
    #print(ans)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import collections
import copy

n = int(input())
ai = [int(i) for i in input().split()]

num = 10**6+1

mod = 10**9+7

if n == 1:
    print(1)
    exit()

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

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

com_ab = [0]*(num)

sosu_li = [[i,0] for i in range(num)]
kosu = 0

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        #print(sosu_li)
        if sosu_li[j][1] == 0:
            sosu_li[j][1] = 1
            kosu += 1
        com_ab[j] = max(com_ab[j],pri_li[i][j])

sosu_li.sort(reverse=True,key=lambda x: x[1])
"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

for i in range(n):
    com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    for j in keys:
        com_ab_new[j] -= pri_li[i][j]
    kari = 1
    for j in range(kosu):
        kari *= pow(sosu_li[j][0],com_ab_new[sosu_li[j][0]],mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
DIVISOR = 10**9 + 7

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

max_el = max(A)

ans = 0

def enumerate_prime(n: int) -> list:
    lis_prime = [True] * (n + 1)
    lis_prime[0] = False
    lis_prime[1] = False

    primes = []
    for i in range(2, n + 1):
        if lis_prime[i]:
            primes.append(i)
            j = 2 * i
            while True:
                if j > n:
                    break
                lis_prime[j] = False
                j += i

    return primes


def iterated_power(z: int, n: int, mod=None) -> int:
    beta = bin(n)[2:]

    Z, q, t = z, 0, len(beta)
    while beta[t - q - 1] == '0':
        Z = Z * Z
        if mod is not None:
            Z = Z % mod
        q += 1
    result = Z

    for k in range(q + 1, t):
        Z = Z * Z
        if mod is not None:
            Z = Z % mod
        if beta[t - k - 1] == '1':
            result = result * Z
            if mod is not None:
                result = result % mod

    if mod is not None:
        result = result % mod

    return result


primes = enumerate_prime(max_el)
max_prime = [0] * len(primes)

# print(primes)

res = [[0]*len(primes) for i in range(N)]

for i, a in enumerate(A):
    for j, prime in enumerate(primes):
        while True:
            if a % prime == 0:
                a = int(a / prime)
                res[i][j] += 1
            if a % prime != 0:
                break
        max_prime[j] = max(res[i][j], max_prime[j])


# print(res)
# print(max_prime)

for i, a in enumerate(A):
    temp = 1
    for j, prime in enumerate(primes):
        val = max_prime[j] - res[i][j]
        if val > 0 :
            temp *= iterated_power(prime, val, DIVISOR)
    ans += temp % DIVISOR


print(ans % DIVISOR)

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)

n = int(input())
a = list(map(int, input().split()))
a.sort()
mod = 10 ** 9 + 7
ans = 0
b = [0] * n
for i in range(n - 1):
    g = gcd(a[i], a[i + 1])
    if i == 0:
        b[i] = a[i + 1] // g
        b[i + 1] = a[i] // g
        ans += b[i] + b[i + 1]
    else:
        c = a[i + 1] // g
        l = lcm(b[i], c)
        if not l == b[i]:
            ans *= l // b[i]
            ans %= mod
        c = l // c
        b[i + 1] = c * a[i] // g
        ans += b[i + 1]
    ans %= mod
print(ans if n >= 2 else 1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
mod = 10**9+7
A = list(map(int,input().split()))
B = max(A)
cnt = [0]*(B+1)
def f(x):
  a = []
  while x % 2 == 0:
    a.append(2)
    x //= 2
  f = 3
  while f * f <= x:
    if x % f == 0:
      a.append(f)
      x //= f
    else:
      f += 2
  if x != 1:
    a.append(x)
  return Counter(a).items()
for i in range(n):
  dct = f(A[i])
  for l in dct:
    if cnt[l[0]] < l[1]:
      cnt[l[0]] = l[1]
ans1 = 1
for i in range(B+1):
  ans1 *= (i**cnt[i])
ans = 0
for i in range(n):
  if A[i] > 0:
    ans += ans1 // A[i]
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

from functools import reduce


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

n = int(input())
a_list = [int(x) for x in input().split()]

temp = reduce(lcm, a_list)

mod = 10 ** 9 + 7
ans = sum([temp // a for a in a_list]) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import collections
import copy

n = int(input())
ai = [int(i) for i in input().split()]

mod = 10**9+7

if n == 1:
    print(1)
    exit()

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

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

pri_li0 = copy.copy(pri_li[0])

for i in range(n-1):
    pri_li[0] += pri_li[i+1]

b_li = [pri_li[0]-pri_li0]

for i in range(1,n):
    b_li.append(pri_li[0]-pri_li[i])

com = copy.copy(b_li[0])
#print(com)
for i in range(1,n):
    com &= b_li[i]
#print(com)
#exit()
for i in range(n):
    b_li[i] -= com

ans = 0

for i in range(n):
    tmp = 1
    #print(len(b_li[i]))
    keys = b_li[i].keys()
    #print(keys)
    for j in keys:
        #print(b_li[i][j])
        #exit()
        tmp *= pow(j, b_li[i][j],mod)
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import collections
import copy

n = int(input())
ai = [int(i) for i in input().split()]

mod = 10**9+7

if n == 1:
    print(1)
    exit()

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

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

pri_li0 = copy.copy(pri_li[0])

for i in range(n-1):
    pri_li[0] += pri_li[i+1]

b_li = [pri_li[0]-pri_li0]

for i in range(1,n):
    b_li.append(pri_li[0]-pri_li[i])

com = copy.copy(b_li[0])
#print(com)
for i in range(1,n):
    com &= b_li[i]
#print(com)
#exit()
for i in range(n):
    b_li[i] -= com

ans = 0

for i in range(n):
    tmp = 1
    #print(len(b_li[i]))
    keys = b_li[i].keys()
    #print(keys)
    for j in keys:
        #print(b_li[i][j])
        #exit()
        tmp *= j ** b_li[i][j]
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans%mod)
exit()

b_li = []

seki = 1

for i in range(n):
    seki *= ai[i]
    seki %= mod

print(seki)

for i in range(n):
    tmp = seki/ai[i]
    print(tmp)
    exit()
    #tmp %= mod
    b_li.append(seki/ai[i])

t_gcd = fractions.gcd(b_li[0],b_li[1])

for i in range(n-2):
    t_gcd = int(fractions.gcd(t_gcd,b_li[i+2]))

#print(t_gcd,b_li,seki)
#exit()

ans = 0

for i in range(n):
    ans += int(seki/t_gcd/ai[i])
    
print(ans%mod)

Submission status: Time Limit Exceeded

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

lcm = 1
from fractions import gcd
for i in range(n):
    lcm *= a[i] // gcd(a[i], lcm)

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n=int(input())
a = list(map(int, input().split()))
memo = defaultdict(int)
x = []
for y in a:
    i = y
    xx = defaultdict(int)
    c = 0
    while i%2==0:
        c += 1
        i //= 2
    memo[2] = max(memo[2], c)
    xx[2]=c
    for j in range(3, int(i**.5)+2, 2):
        c=0
        while i%j==0:
            c += 1
            i //= j
        memo[j] = max(memo[j], c)
        xx[j] = c
    if i!=1:
        xx[i]=1
        memo[i] = max(memo[i], 1)
    x.append(xx)
mod = 10**9+7
result = 0
for i in range(n):
    num = 1
    for s, t in memo.items():
        num *= pow(s, t-x[i][s])
    result = (result+num)%mod

print(result)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(map(int, input().split()))
memo = {2:0}
x = []
for y in a:
    i = y
    xx = {}
    c = 0
    while i%2==0:
        c += 1
        i //= 2
    memo[2] = max(memo[2], c)
    xx[2]=c
    for j in range(3, int(i**.5)+2, 2):
        if i%j==0:
            c=0
            while i%j==0:
                c += 1
                i //= j
            if j in memo:
                memo[j] = max(memo[j], c)
            else:
                memo[j] = c
            xx[j] = c
    if i!=1:
        xx[i]=1
        if i in memo:
            memo[i] = max(memo[i], 1)
        else:
            memo[i] = 1
    x.append(xx)
mod = 10**9+7
result = 0
for i in range(n):
    num = 1
    for s, t in memo.items():
        if s in x[i]:
            num *= pow(s, t-x[i][s])
        else:
            num *= pow(s,t)
    if result+num >= mod:
        result = (result+num)%mod
    else:
        result += num
print(result)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(map(int, input().split()))
memo = {}
x = []
for i in a:
    xx = {}
    for j in range(2, int(i**.5)+2):
        if i%j==0:
            c=0
            while i%j==0:
                c += 1
                i //= j
            if j in memo:
                memo[j] = max(memo[j], c)
            else:
                memo[j] = c
            xx[j] = c
    if i!=1:
        xx[i]=1
        if i in memo:
            memo[i] = max(memo[i], 1)
        else:
            memo[i] = 1
    x.append(xx)
mod = 10**9+7
result = 0
for i in range(n):
    num = 1
    for s, t in memo.items():
        if s in x[i]:
            num *= pow(s, t-x[i][s])
        else:
            num *= pow(s,t)
    if result+num >= mod:
        result = (result+num)%mod
    else:
        result += num
print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
mod = 10**9+7
res = [0]*(max(a)+1)
ma = 0
for i in a:
    for j in range(2,int(i**0.5)+1):
        cnt = 0
        while i%j==0:
            i//=j
            cnt+=1
        res[j] = max(res[j],cnt)
    if i!=1:
        res[i] = max(res[i],1)

d = 1
for i in range(max(a)+1):
    if res[i]>0:
        d*=i**res[i]
ans = 0
for i in range(n):
    ans = (ans+d//a[i])%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
mod = 10**9+7
res = [0]*(max(a)+1)
for i in a:
    for j in range(2,int(i**0.5)+1):
        cnt = 0
        while i%j==0:
            i//=j
            cnt+=1
        res[j] = max(res[j],cnt)
    if i!=1:
        res[i] = max(res[i],1)

d = 1
for i in range(max(a)+1):
    d *= max(i**res[i],1)
ans = 0
for i in range(n):
    ans = (ans+d//a[i])%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
lcm_val=a[0]
for i in range(n-1):
  lcm_val=lcm(lcm_val,a[i+1])
# print(lcm_val)
b=[]
for aa in a:
  b.append(lcm_val//aa)

ans=0
for bb in b:
  ans+=bb
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
lcm_val=a[0]
for i in range(n-1):
  lcm_val=lcm(lcm_val,a[i+1])
# print(lcm_val)
b=[]
for aa in a:
  b.append((lcm_val//aa)%mod)

ans=0
for bb in b:
  ans+=bb
  ans%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def eratosthenes(N):
	is_prime = [True] * (N + 1)
	is_prime[0], is_prime[1] = False, False
	for i in range(2, int(N**(1/2)) + 1):
		if is_prime[i]:
			for j in range(i * 2, N + 1, i):
				is_prime[j] = False
	return [i for i in range(N+1) if is_prime[i]]

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
primes = eratosthenes(10**6+1)

tot_cnt = defaultdict(lambda: 0)

def factorization(num):
	tmp_cnt = defaultdict(lambda: 0)
	for p in primes:
		if p > num:
			break

		while True:
			if num % p == 0:
				num //= p
				tmp_cnt[p] += 1
			else:
				break

	return tmp_cnt

for a in A:
	T = factorization(a)
	for t in T:
		tot_cnt[t] = max(tot_cnt[t], T[t])

lcm = 1
for t in tot_cnt:
	lcm *= pow(t, tot_cnt[t], mod)
	lcm %= mod

ans = 0
for a in A:
	tmp = lcm * pow(a, mod-2, mod)
	ans += tmp
	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_total = defaultdict(int)

for a in A:
    tmp = a
    primes_a = defaultdict(int)
    p = 2
    while p * p <= tmp:
        while tmp % p == 0:
            primes_a[p] += 1
            tmp //= p
        p += 1
    if tmp != 1:
        primes_a[tmp] += 1

    for k in primes_a.keys():
        primes_total[k] = max(primes_total[k], primes_a[k])

lcm = 1
for k in primes_total.keys():
    lcm *= pow(k, primes_total[k], MOD)
    lcm %= MOD

ans = 0

for a in A:
    # フェルマーの小定理より
    ans += lcm * pow(a, MOD - 2, MOD)
    ans %= MOD

print(ans)