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 fractions
import sys
input = sys.stdin.readline

mod = 10 ** 9 + 7
def modpow(a, x):
    if a == 0:
        return 0
    if x == 0:
        return 1
    elif x % 2 == 0:
        return modpow((a * a) % mod, x // 2) % mod
    else:
        return (modpow((a * a) % mod , x // 2) % mod * a) % mod


def factorization(x):
    ans = {}
    i = 2
    in_x = x
    while i <= x:
        count = 0
        while x % i == 0:
            x = x // i
            count += 1
        if count > 0:
            ans[i] = count
        i += 1
    return ans


N = int(input())
A = list(map(int, input().split(" ")))
primes = {}
for a in A:
    factors = factorization(a)
    for f in factors:
        if f in primes:
            primes[f] = max(primes[f], factors[f])
        else:
            primes[f] = factors[f]

ans = 0
for a in A:
    factors = factorization(a)
    tmp = 1
    for p in primes:
        if p in factors:
            tmp *= modpow(p, (primes[p] - factors[p]))
        else:
            tmp *= modpow(p, primes[p])
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
def modpow(a, x):
    if a == 0:
        return 0
    if x == 0:
        return 1
    elif x % 2 == 0:
        return modpow((a * a) % mod, x // 2) % mod
    else:
        return (modpow((a * a) % mod , x // 2) % mod * a) % mod


def factorization(x):
    ans = []
    i = 2
    in_x = x
    while i <= x:
        count = 0
        while x % i == 0:
            x = x // i
            count += 1
        if count > 0:
            ans.append((i, count))
        i += 1
    return ans


N = int(input())
A = list(map(int, input().split(" ")))
primes = {}
for a in A:
    factors = factorization(a)
    for f in factors:
        if f[0] in primes:
            primes[f[0]] = max(primes[f[0]], f[1])
        else:
            primes[f[0]] = f[1]

lcm = 1
for p in primes:
    lcm *= modpow(p, primes[p])
    lcm %= mod

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

Submission status: Time Limit Exceeded

Solution code:
import fractions

mod = 10 ** 9 + 7
def modpow(a, x):
    if a == 0:
        return 0
    if x == 0:
        return 1
    elif x % 2 == 0:
        return modpow((a * a) % mod, x // 2) % mod
    else:
        return (modpow((a * a) % mod , x // 2) % mod * a) % mod


def factorization(x):
    ans = []
    i = 2
    in_x = x
    while i <= x:
        count = 0
        while x % i == 0:
            x = x // i
            count += 1
        if count > 0:
            ans.append((i, count))
        i += 1
    return ans


N = int(input())
A = list(map(int, input().split(" ")))
primes = {}
for a in A:
    factors = factorization(a)
    for f in factors:
        if f[0] in primes:
            primes[f[0]] = max(primes[f[0]], f[1])
        else:
            primes[f[0]] = f[1]

lcm = 1
for p in primes:
    lcm *= modpow(p, primes[p])
    lcm %= mod


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

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7
def modpow(a, x):
    if a == 0:
        return 0
    if x == 0:
        return 1
    elif x % 2 == 0:
        return modpow((a * a) % mod, x // 2) % mod
    else:
        return (modpow((a * a) % mod , x // 2) % mod * a) % mod


rev = [modpow(i, mod - 2) % mod for i in range(10 ** 6 + 1)]
N = int(input())
A = list(map(int, input().split(" ")))
lcm = 1
for a in A:
    lcm = lcm * a * rev[fractions.gcd(lcm, a)]
print(lcm % mod)

ans = 0
for a in A:
    ans += (lcm * rev[a]) % mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

mod = 10 ** 9 + 7
def modpow(a, x):
    if a == 0:
        return 0
    if x == 0:
        return 1
    elif x % 2 == 0:
        return modpow((a * a) % mod, x // 2) % mod
    else:
        return (modpow((a * a) % mod , x // 2) % mod * a) % mod


rev = [modpow(i, mod - 2) % mod for i in range(10 ** 6 + 1)]
N = int(input())
A = list(map(int, input().split(" ")))
lcm = 1
for a in A:
    lcm = lcm * a * rev[fractions.gcd(lcm, a)]
print(lcm % mod)

ans = 0
for a in A:
    ans += (lcm * rev[a]) % mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#かけて最小公倍数になる　そのために必要な数がB
from fractions import gcd
N=int(input())
mod=10**9+7
A=list(map(int, input().split()))
def lcm(a,b):
  return a//gcd(a,b)*b

LCM=1
#LCM%=mod
for i in range(N):
  LCM=lcm(LCM, A[i])
  #LCM%=mod
  
#print(LCM)
ans=0
for a in A:
  ans+=LCM//a
  ans%=mod

print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:

#かけて最小公倍数になる　そのために必要な数がB
from fractions import gcd
N=int(input())
if N==1:
  print(1)
  exit()

mod=10**9+7
A=list(map(int, input().split()))
def lcm(a,b):
  return a//gcd(a,b)*b

if N==2:
  LCM=lcm(A[0],A[1])
  ans=((LCM//A[0])+(LCM//A[1]))%mod
  print(ans)
  exit()

LCM=1
#LCM%=mod
for a in A:
  LCM=lcm(LCM, a)
  #LCM%=mod
  
#print(LCM)
ans=0
for a in A:
  ans+=LCM//a
  #ans%=mod

print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:

#かけて最小公倍数になる　そのために必要な数がB
from fractions import gcd
N=int(input())
if N==1:
  print(1)
  exit()

mod=10**9+7
A=list(map(int, input().split()))
def lcm(a,b):
  return (a*b)/gcd(a,b)

if N==2:
  LCM=lcm(A[0],A[1])
  ans=((LCM//A[0])+(LCM//A[1]))%mod
  print(ans)
  exit()

LCM=1
#LCM%=mod
for a in A:
  LCM=lcm(LCM, a)
  #LCM%=mod
  
#print(LCM)
ans=0
for a in A:
  ans+=LCM//a
  #ans%=mod

print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:

#かけて最小公倍数になる　そのために必要な数がB
from fractions import gcd
N=int(input())
if N==1:
  print(1)
  exit()

mod=10**9+7
A=list(map(int, input().split()))
def lcm(a,b):
  return (a*b)/gcd(a,b)

if N==2:
  LCM=lcm(A[0],A[1])
  ans=((LCM//A[0])+(LCM//A[1]))%mod
  print(ans)
  exit()

LCM=lcm(A[0],A[1])
#LCM%=mod
for i in range(2,N):
  LCM=lcm(LCM, A[i])
  #LCM%=mod
  
#print(LCM)
ans=0
for a in A:
  ans+=LCM//a
  #ans%=mod

print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:

#かけて最小公倍数になる　そのために必要な数がB
from fractions import gcd
N=int(input())
if N==1:
  print(1)
  exit()

mod=10**9+7
A=list(map(int, input().split()))
def lcm(a,b):
  return (a*b)/gcd(a,b)

if N==2:
  LCM=lcm(A[0],A[1])
  ans=((LCM//A[0])+(LCM//A[1]))%mod
  print(ans)
  exit()

LCM=lcm(A[0],A[1])
#LCM%=mod
for i in range(2,N):
  LCM=lcm(LCM, A[i])
  #LCM%=mod
  
#print(LCM)
ans=0
for a in A:
  ans+=LCM//a
  ans%=mod

print(int(ans%mod))

Submission status: Time Limit Exceeded

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

bucket = [0] * (M + 1)
for val in A:
    for i in range(2, math.floor(math.sqrt(val)) + 1):
        #print(val, i)
        temp = 0
        while val % i == 0:
            val //= i
            temp += 1
        bucket[i] = max(bucket[i], temp)
    if val != 1:
        bucket[val] = max(bucket[val], 1)
#print(bucket)

L = 1
for n in range(M + 1):
    L *= n ** bucket[n]
#print(L)

ans = 0
for val in A:
    ans = (ans + L // val) % MOD
print(ans)

Submission status: Time Limit Exceeded

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

import fractions
l = 1
for val in A:
    l = (l * val // fractions.gcd(val, l))
#print(l)

ans = 0
for val in A:
    ans = (ans + l // val) % 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

l = 1
for a in A:
    l = a*l//(gcd(a,l))
ans = 0
for a in A:
    ans += l//a % MOD
    if ans >= 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

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

Submission status: Time Limit Exceeded

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

N = int(input())
A = [int(i) for i in input().split()]
MOD = 10**9 + 7

def gcd(n, m):
    if m == 0:
        return n
    while m != 0:
        n, m = m, n % m
    return n

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

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

ans = 0
for i, a in enumerate(A):
    ans += L // a
    if i == N // 2:
        ans %= MOD

print(ans % 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 prime_factorize(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

primes = defaultdict(int)
for a in A:
    for x, p in prime_factorize(a):
        primes[x] = max(primes[x], p)
lcm = 1
for prime, ind in primes.items():
    lcm *= prime ** ind
ans = 0
for i in range(N):
    ans += lcm // A[i]
    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
lcm = A[0]
for i in range(1, N):
    lcm = lcm * A[i] // gcd(lcm, A[i])
ans = 0
for i in range(N):
    ans += lcm // A[i]
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    MOD = 10**9 + 7

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

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

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

    ans = 0
    for i, a in enumerate(A):
        ans += n//a
        if i == N//2:
            ans %= MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7


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

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def main():

    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7
    def lcm(a,b):
        return a*b // gcd(a,b)

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

    B = []
    for i in range(N):
        B.append(LCM // A[i])

    print(sum(B) % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7
def lcm(a,b):
    return a*b // fractions.gcd(a,b)

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

B = []
for i in range(N):
    B.append(LCM // A[i])

print(sum(B) % 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

# A の最小公倍数を求める
lcm = 1
for i in range(N):
    lcm = lcm*A[i] // gcd(lcm, A[i])

ans = 0
for a in A:
    ans += lcm//a
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
mod = 7 + 10 ** 9

def lcm(a, b):
    a, b = max(a, b), min(a, b)
    c = a * b
    while a % b > 0:
        a, b = b, a % b
    return c // b

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    L = A[0]
    for i in range(1, N): L = lcm(L, A[i])
    ans = 0
    for a in A:
        ans += (L * pow(a, mod - 2, mod)) % mod
        ans %= mod
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        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]]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def make_divisors2(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    prime_list = prime(max(a))
    prime_count = dict()
    for value in prime_list:
        prime_count[value] = 0
    
    for i in range(n):
        value = a[i]
        divisors = make_divisors(value)
        for d in divisors:
            if d in prime_count:
                c, v = 0, value
                while v%d == 0:
                    c += 1
                    v //= d
                if prime_count[d] < c:
                    prime_count[d] = c
    
    ans = 0
    inf = pow(10, 9)+7
    
    for value in a:
        sub = 1
        for p in prime_list:
            k = prime_count[p]
            v = value
            while v%p == 0:
                v //= p
                k -= 1
            sub *= pow(p, k, inf)
            sub %= inf
        ans += sub
        ans %= inf
    
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        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]]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def make_divisors2(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    prime_list = prime(max(a))
    prime_count = dict()
    for value in prime_list:
        prime_count[value] = 0
    
    for i in range(n):
        value = a[i]
        divisors = make_divisors(value)
        for d in divisors:
            if d in prime_count:
                c, v = 0, value
                while v%d == 0:
                    c += 1
                    v //= d
                if prime_count[d] < c:
                    prime_count[d] = c
    
    ans = 0
    inf = pow(10, 9)+7
    
    for value in a:
        sub = 1
        for p in prime_list:
            k = prime_count[p]
            v = value
            while v%p == 0:
                v //= p
                k -= 1
            sub *= pow(p, k, inf)
            sub %= inf
        ans += sub
        ans %= inf
    
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import collections


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


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

l = {}
answer = 0
for aa in a:
    c = collections.Counter(prime_factorize(aa))
    cc.append(c)
    for k in c.keys():
        if k in l:
            l[k] = max(c[k], l[k])
        else:
            l[k] = c[k]

for idx, aa in enumerate(a):
    ll = 1
    c = cc[idx]
    for k in l.keys():
        if k in c:
            ll = ll * (k ** (l[k] - c[k]))
        else:
            ll = ll * (k ** l[k])
    answer += ll
    if answer >= 10 ** 9 + 7:
        answer = answer % (10 ** 9 + 7)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import collections


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


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

l = {}
answer = 0
for aa in a:
    c = collections.Counter(prime_factorize(aa))
    for k in c.keys():
        if k in l:
            l[k] = max(c[k], l[k])
        else:
            l[k] = c[k]

for aa in a:
    ll = 1
    c = collections.Counter(prime_factorize(aa))
    for k in l.keys():
        if k in c:
            ll = ll * (k ** (l[k] - c[k]))
        else:
            ll = ll * (k ** l[k])
    answer += ll
    if answer >= 10 ** 9 + 7:
        answer = answer % (10 ** 9 + 7)

print(answer)

Submission status: Time Limit Exceeded

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)

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

l = lcm(a)
answer = 0
for aa in a:
    answer += l // aa
    if answer >= 10 ** 9 + 7:
        answer = answer % (10 ** 9 + 7)

print(answer)

Submission status: Time Limit Exceeded

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)

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

l = lcm(a)
answer = 0
for aa in a:
    answer += l // aa
    answer = answer % (10 ** 9 + 7)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n = int(input())
    a = list(map(int, readline().split()))

    def factorization(n):
        factors = []

        while n % 2 == 0:
            factors.append(2)
            n //= 2

        for i in range(3, int(n ** 0.5) + 5, 2):
            while n % i == 0:
                factors.append(i)
                n //= i
        if n != 1:
            factors.append(n)

        return Counter(factors)

    a_fac = [0] * n

    for i, num in enumerate(a):
        a_fac[i] = factorization(num)

    lcm = {1: 1}

    for fac in a_fac:
        for key, value in fac.items():
            lcm[key] = max(lcm.get(key, 0), value)

    ans = 0

    for fac in a_fac:
        temp = 1
        for key, value in lcm.items():
            p = value - fac.get(key, 0)
            temp *= pow(key, p)
            temp %= MOD
        ans += temp
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)



def main():
    from collections import Counter
    n = int(input())
    a = list(map(int, readline().split()))

    def enum_primes(n):
        if n == 2:
            return [2]

        flag_num = (n + 1) // 2
        prime_flag = [True] * flag_num


        for i in range(1, int(n ** 0.5) + 1, 2):
            if prime_flag[i]:
                p = 2 * i + 1
                for j in range(2 * i * (i + 1), flag_num, p):
                    prime_flag[j] = False

        primes = [2]
        temp = [i * 2 + 1 for i in range(1, flag_num) if prime_flag[i]]
        primes.extend(temp)

        return primes

    nmax = max(a)

    if nmax == 1:
        print(n)
        sys.exit()

    primes = enum_primes(nmax)

    def factorization(n):
        factors = []

        for i in primes:
            while n % i == 0:
                factors.append(i)
                n //= i
        if n != 1:
            factors.append(n)

        return Counter(factors)

    a_fac = [0] * n

    for i, num in enumerate(a):
        a_fac[i] = factorization(num)

    lcm = Counter([1])

    for i, fac in enumerate(a_fac):
        add_temp = fac - lcm
        add = Counter({key: value for key, value in add_temp.items() if value > 0})
        lcm += add

    b = [0] * n
    ans = 0

    for i, fac in enumerate(a_fac):
        b_fac = lcm - fac
        temp = 1
        for key, value in b_fac.items():
            temp *= pow(key, value)
            temp %= MOD
        ans += temp
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n = int(input())
    a = list(map(int, readline().split()))

    def factorization(n):
        factors = []

        while n % 2 == 0:
            factors.append(2)
            n //= 2

        for i in range(3, int(n ** 0.5) + 5, 2):
            while n % i == 0:
                factors.append(i)
                n //= i
        if n != 1:
            factors.append(n)

        return Counter(factors)

    a_fac = [0] * n

    for i, num in enumerate(a):
        a_fac[i] = factorization(num)

    lcm = Counter([1])

    for i, fac in enumerate(a_fac):
        add_temp = fac - lcm
        add = Counter({key: value for key, value in add_temp.items() if value > 0})
        lcm += add

    b = [0] * n
    ans = 0

    for i, fac in enumerate(a_fac):
        b_fac = lcm - fac
        temp = 1
        for key, value in b_fac.items():
            temp *= pow(key, value)
            temp %= MOD
        ans += temp
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

sum_b = 0
for i in range(n):
  sum_b = (sum_b + lcm // a[i]) % mod
print(sum_b)

Submission status: Time Limit Exceeded

Solution code:
import fractions
mod = 10 ** 9 + 7

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

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

LCM = 1
for i in a:
    LCM = lcm(LCM,i)

ans = 0
for i in a:
    ans += LCM // i
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions
mod = 10 ** 9 + 7

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

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

LCM = 1
for i in a:
    LCM = lcm(LCM,i)

ans = 0
for i in a:
    ans += LCM // i
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from fractions import gcd

n = int(readline())
a = list(map(int, readline().split()))
ans = 0
gcd_ans = a[0]
lcm_ans = a[0]
mod = 10 ** 9 + 7
for i in range(1, n):
    gcd_ans = gcd(lcm_ans, a[i])
    lcm_ans = lcm_ans * a[i] // gcd_ans
for i in range(n):
    ans += lcm_ans // a[i]
    ans %= mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


def lcm(X, Y):
    x = X
    y = Y
    if y > x:
        x, y = y, x
    while x % y != 0:
        x, y = y, x % y
    return X * Y // y


cnt = 0
ans = 0
LCM = 1
for i in range(n):
    Q = lcm(LCM, A[i])
    cnt *= Q // LCM
    LCM = Q
    cnt += Q // A[i]
print(cnt % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7
num = tuple(num)

from collections import Counter
def factorization(a):
        yy, j = [], 2
        y = yy.append
        while(a > 1):
            for i in range(j, int(a**0.5)+1):
                if a % i == 0:
                    y(i)
                    a, j = a//i, i
                    break
            else:
                y(a)
                break
        return Counter(yy)

lcd = dict()
for i in num:
  j = factorization(i)
  for x,y in j.items():
    if not x in lcd.keys():
      lcd[x] = y
    else:
      lcd[x] = max(lcd[x],y)

lc = 1
for i,j in lcd.items():
  lc *= pow(i,j,mod)
  
ans =0
for i in range(n):
  ans += lc*pow(num[i], mod-2, mod)
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7

from collections import Counter
def factorization(a):
        yy, j = [], 2
        y = yy.append
        while(a > 1):
            for i in range(j, int(a**0.5)+1):
                if a % i == 0:
                    y(i)
                    a, j = a//i, i
                    break
            else:
                y(a)
                break
        return Counter(yy)

lcd = dict()
for i in num:
  j = dict(factorization(i))
  for x,y in j.items():
    if not x in lcd.keys():
      lcd[x] = y
    else:
      lcd[x] = max(lcd[x],y)

lc = 1
for i,j in lcd.items():
  lc *= pow(i,j,mod)
  
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

ans =0
for i in range(n):
  ans += lc*modinv(num[i],mod)
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main(): 
  import sys
  input = sys.stdin.readline
  n = int(input())
  num = list(map(int, input().split()))
  mod = 10**9+7

  from collections import Counter
  # 高速素因数分解(√n)
  def factorization(a):
          yy, j = [], 2
          y = yy.append
          while(a > 1):
              for i in range(j, int(a**0.5)+1):
                  if a % i == 0:
                      y(i)
                      a, j = a//i, i
                      break
              else:
                  y(a)
                  break
          return Counter(yy)

  lcd = dict()
  for i in num:
    j = dict(factorization(i))
    for x,y in j.items():
      if not x in lcd.keys():
        lcd[x] = y
      else:
        lcd[x] = max(lcd[x],y)

  lc = 1
  for i,j in lcd.items():
    lc *= pow(i,j,mod)

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

  ans =0
  for i in range(n):
    ans += lc*modinv(num[i],mod)
    ans %= mod
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
D=[]
def factorization(N):
   i=2
   res={}
   while i*i<=N:
       if N%i!=0:
           i+=1
           continue
       res[i]=0
       while N%i==0:
           res[i]+=1
           N//=i
       i+=1
   if N!=1:
       res[N]=1
   return res

G={}
for a in A:
    b=factorization(a)
    D.append(b)
    for k in b.keys():
        if k in G:
            G[k]=max(G[k], b[k])
        else:
            G[k]=b[k]
ans=0
P=10**9+7
cnt=0
for i in range(len(A)):
    x=1
    b=D[i]
    for g in G:
        if g in b:
            x*=g**(G[g]-b[g])
        else:
            x*=g**(G[g])
        x%=P
    ans+=x
    ans%=P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
D=[]
def factorization(N):
    temp={}
    while True:
        divided=False
        for i in range(2, int(N**0.5)+1):
            if N%i==0:
                if i in temp:
                    temp[i]+=1
                else:
                    temp[i]=1
                N=N//i
                divided=True
                break
        if not divided:
            if N in temp:
                temp[N]+=1
            else:
                temp[N]=1
            break
    return temp
G={}
for a in A:
    b=factorization(a)
    D.append(b)
    for k in b.keys():
        if k in G:
            G[k]=max(G[k], b[k])
        else:
            G[k]=b[k]
ans=0
P=10**9+7
cnt=0
for i in range(len(A)):
    x=1
    b=D[i]
    for g in G:
        if g in b:
            x*=g**(G[g]-b[g])
        else:
            x*=g**(G[g])
        x%=P
    ans+=x
    ans%=P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
D=[]
def factorization(N):
    temp={}
    while True:
        divided=False
        for i in range(2, int(N**0.5)+1):
            if N%i==0:
                if i in temp:
                    temp[i]+=1
                else:
                    temp[i]=1
                N=N//i
                divided=True
                break
        if not divided:
            temp[1]=1
            if N in temp:
                temp[N]+=1
            else:
                temp[N]=1
            break
    return temp
G={}
for a in A:
    b=factorization(a)
    D.append(b)
    for k in b.keys():
        if k in G:
            G[k]=max(G[k], b[k])
        else:
            G[k]=b[k]
ans=0
P=10**9+7
for i in range(len(A)):
    x=1
    b=D[i]
    for g in G:
        if g in b:
            x*=g**(G[g]-b[g])
        else:
            x*=g**(G[g])
    ans+=x
    ans%=P
print(ans)