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:
def prime(x):
    y = list(range(1, x + 1))
    y[0] = 0
    x_sqrt = x ** 0.5
    for i in y:
        if i > x_sqrt:
            break
        elif i == 0:
            continue
        for not_prime in range(2 * i, x + 1, i):
            y[not_prime - 1] = 0
    return [i for i in y if i > 0]

def prime_factrize(a, prime):
    x = []
    for p in prime:
        n = 0
        while a % p == 0:
            a = a // p
            n += 1
        x.append(n)
    return x

def lcm_prime(a, b):
    return list(map(max, zip(a, b)))

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
prime_list = prime(max(a))
a_prime = []
l_prime = [0 for _ in range(len(prime_list))]

for ai in a:
    a_prime.append(prime_factrize(ai, prime_list))
    l_prime = lcm_prime(l_prime, a_prime[-1])

ans = 0
for ai in a_prime:
    x = 1
    for ap, lp, p in zip(ai, l_prime, prime_list):
        x *= pow(p, lp - ap, MOD)
        x %= MOD
    ans += x
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from fractions import gcd
  mod = 10**9 + 7
  N = int(input())
  A = list(map(int, input().split()))

  lcm = A[0]
  for i in A:
    lcm = (lcm*i) // gcd(lcm,i)

  ans = 0
  for i in A:
    ans += lcm // i
  print(ans%mod)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        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 prime_list(n,ls):
    i = 0
    table = defaultdict(int)
    while ls[i]**2<=n:
        while n%ls[i]==0:
            n //= ls[i]
            table[ls[i]] += 1
        i += 1
    if n>1:
        table[n] += 1
    return table
    

def main():
    mod = 10**9 + 7
    N = int(input())
    A = [int(x) for x in input().split()]
    dic = defaultdict(int)
    eranes = eratosthenes(10**6)
    
    for i in A:
        prime = prime_list(i,eranes)
        for j,k in prime.items():
            if dic[j]<=k:
                dic[j] = k
            else:
                pass
    sub = 1
    for i,j in dic.items():
        sub *= i**j
    ans = 0
    for i in A:
        ans += sub//i
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

read = sys.stdin.read


def sieve_of_eratosthenes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def prime_factorize(n, p):
    a = []
    for i in p:
        if n % i != 0:
            continue
        while n % i == 0:
            a.append(i)
            n //= i
        if n == 1:
            return a


N, *A = map(int, read().split())
mod = 10 ** 9 + 7

primes = sieve_of_eratosthenes(10 ** 6)
dic = {i: 0 for i in primes}

n = len(primes)
p = [0] * n
for i in A:
    if i == 1:
        continue
    if dic.get(i):
        dic[i] = max(1, dic[i])
        continue

    tmp = Counter(prime_factorize(i, primes))

    for key, value in tmp.items():
        # print(key, value)
        if dic[key] < value:
            dic[key] = value

lcm = 1
for i, j in dic.items():
    if j == 0:
        continue
    lcm *= pow(i, j, mod)
    lcm %= mod

answer = 0
for i in A:
    answer += lcm * pow(i, mod - 2, mod)
    answer %= mod

print(answer)

Submission status: Time Limit Exceeded

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

from fractions import gcd
from functools import reduce

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

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

lcma = lcm_list(an)
ans = 0
for a in an:
    ans += lcma // a
mod=10**9+7
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

import fractions
from functools import reduce

from copy import deepcopy

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

big = 1000000007

def lcm(primes, num):
    facto = factorization(num)
    for key in facto:
        if key in primes:
            primes[key] = max(primes[key], facto[key])
        else:
            primes[key] = facto[key]
    return primes
        
def devide_facto(devided, deviding):
    devided = deepcopy(devided)
    for key in deviding:
        devided[key] -= deviding[key]
    return devided

def prod_facto(facto):
    prodv = 1
    for key in facto:
        if facto[key] == 0:
            continue
        prodv = prodv * key ** facto[key]
        prodv %= big
    return prodv
    
    
def factorization(num):
    i = 2
    facto = {}
    while i <= num ** (0.5):
        if num % i == 0:
            if i in facto.keys():
                facto[i] += 1
            else:
                facto[i] = 1
            num //= i
            continue
        i += 1
    if num in facto.keys():
        facto[num] += 1
    else:
        facto[num] = 1
    return facto
    

n = int(input())
a = list(map(int, input().split(' ')))
primes = {}
for num in a:
    primes = lcm(primes, num)

sumv = 0        
for num in a:
    facto_num = factorization(num)
    facto_devided = devide_facto(primes, facto_num)
    
    sumv += prod_facto(facto_devided)
    sumv %= big
    
print(sumv)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from fractions import gcd
  mod = 10**9 + 7
  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])

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


N = int(input())
A = list(map(int, input().split()))
lcm = lambda x, y: x*y//gcd(x, y)
l = 1
for a in A:
    l = lcm(l, a)
ans = 0
MOD = 10**9+7
for a in A:
    ans = (ans + l // a) % MOD 
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def gcd(a,b):
    x = max([a,b])
    y = min([a,b])
    while y:
        x, y = y, x % y
    return x

# x * y = lcm(x, y) // gcd(x, y)より
def lcm(x, y):
    return x * y // gcd(x, y)

def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    MOD = 10**9+7


    tmp = A[0]
    for a in A[1:]:
        tmp = lcm(tmp, a)

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

    ans = 0
    for b in B:
        ans += b
        ans %= MOD
        

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from fractions import gcd
  mod = 10**9 + 7
  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])

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

Submission status: Time Limit Exceeded

Solution code:

def gcd(a,b):
    x = max([a,b])
    y = min([a,b])
    while y:
        x, y = y, x % y
    return x

# x * y = lcm(x, y) // gcd(x, y)より
def lcm(x, y):
    return x * y // gcd(x, y)

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


    tmp = A[0]
    for a in A[1:]:
        tmp = lcm(tmp, a)

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

    ans = 0
    for b in B:
        ans += b
        ans %= MOD
        

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
from fractions import gcd
mod = 10**9+7
g = A[0]
for a in A[1::]:
  g = g*a//gcd(g,a)
  
ans = 0
b = g%mod
for a in A:
  ans += g%mod*pow(a,mod-2,mod)
  ans %= mod
  
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=list(map(int,input().split()))
    l=A[0]
    for x in A[1:]:
        l=l*x//gcd(l,x)
    ans=0
    for x in A:
        ans+=l//x
    print(ans%MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def gcd(a,b):
    x = max([a,b])
    y = min([a,b])
    while y:
        x, y = y, x % y
    return x

# x * y = lcm(x, y) // gcd(x, y)より
def lcm(x, y):
    return x * y // gcd(x, y)


tmp = A[0]
for a in A[1:]:
    tmp = lcm(tmp, a)

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

ans = 0
for b in B:
    ans += b
    ans %= MOD
    

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
from fractions import gcd
mod = 10**9+7
g = A[0]
for a in A[1::]:
  g = g*a//gcd(g,a)
  
ans = 0
b = g%mod
for a in A:
  ans += (g//a)%mod
  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

LCM=defaultdict(int)
def f(n):
    ret=defaultdict(int)
    p=2
    while n%p==0:
        ret[p]+=1
        n//=p
    LCM[p]=max(LCM[p],ret[p])
    p=3
    while p*p<=n:
        while n%p==0:
            ret[p]+=1
            n//=p
        LCM[p]=max(LCM[p],ret[p])
        p+=2
    if n>1:
        ret[n]=1
        LCM[n]=max(LCM[n],ret[n])
    return ret

F=[]
for a in A:
    F.append(f(a))

ans=0
for i in range(N):
    tmp=1
    f=F[i]
    for p,n in LCM.items():
        tmp=tmp*pow(p,n-f[p],MOD)%MOD
    ans=(ans+tmp)%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=list(map(int,input().split()))
    l=A[0]
    for x in A[1:]:
        l=l*x//gcd(l,x)
    ans=0
    for x in A:
        ans+=l//x
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

read = sys.stdin.read


def sieve_of_eratosthenes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def prime_factorize(n):
    a = []
    if n == 1:
        return [1]
    for i in primes:
        if n % i != 0:
            continue
        while n % i == 0:
            a.append(i)
            n //= i
        if n == 1:
            return a


N, *A = map(int, read().split())
mod = 10 ** 9 + 7

primes = sieve_of_eratosthenes(10 ** 6)
dic = {i: 0 for i in primes}

n = len(primes)
p = [0] * n
for i in A:
    if i == 1:
        continue
    tmp = Counter(prime_factorize(i))
    for key, value in tmp.items():
        # print(key, value)
        if dic[key] < value:
            dic[key] = value

lcm = 1
for i, j in dic.items():
    if j == 0:
        continue
    lcm *= pow(i, j, mod)
    lcm %= mod

answer = 0
for i in A:
    answer += lcm * pow(i, mod - 2, mod)
    answer %= mod

print(answer)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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


lcm=[0]*(10**6+5)



for i in range(N):
    a=A[i]
    b=int(math.sqrt(a))+1
    for j in range(2,b):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for j in range(2,len(lcm)):
    l*=pow(j,lcm[j])
    

ans=0
mod=10**9+7

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = reduce(lcm, A)

    ans = 0
    for a in A:
        ans = (ans + L // a) % mod

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
import numpy as np

MOD = 10**9+7

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


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

    lcm = reduce(lcm_base, a, 1)
    B = (lcm // A) % MOD

    print(np.sum(B) % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

lcm = lambda a, b: a * b // gcd(a, b)
mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

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

ans = 0
for a in A:
    ans = (ans + L // a) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

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

    ans = 0
    for a in A:
        ans = (ans + L // a) % mod

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
lcm = aaa[0]
for a in aaa[1:]:
    lcm = lcm * a // gcd(lcm, a)

ans = 0
for a in aaa:
    ans = (ans + lcm // a) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

read = sys.stdin.read


def sieve_of_eratosthenes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def prime_factorize(n):
    a = []
    for i in primes:
        if n % i != 0:
            continue
        while n % i == 0:
            a.append(i)
            n //= i
        if n == 1:
            return a


N, *A = map(int, read().split())
mod = 10 ** 9 + 7

primes = sieve_of_eratosthenes(10 ** 6)
dic = {i: 0 for i in primes}

n = len(primes)
p = [0] * n
for i in A:
    if i == 1:
        continue
    tmp = Counter(prime_factorize(i))
    for key, value in tmp.items():
        # print(key, value)
        if dic[key] < value:
            dic[key] = value

lcm = 1
for i, j in dic.items():
    if j == 0:
        continue
    lcm *= pow(i, j, mod)
    lcm %= mod

answer = 0
for i in A:
    answer += lcm * pow(i, mod - 2, mod)
    answer %= mod

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
# 素因数分解 (taple)
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

def main():
    mod = 10**9 + 7
    N = int(input())
    A = [int(x) for x in input().split()]
    dic = defaultdict(int)
    for i in A:
        prime = factorize(i)
        for j,k in prime:
            if dic[j]<=k:
                dic[j] = k
            else:
                pass
    sub = 1
    for i,j in dic.items():
        sub *= i**j
    ans = 0
    for i in A:
        ans += sub//i
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

lcm = lambda a, b: a * b // gcd(a, b)
mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

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

ans = 0
for a in A:
    ans = (ans + L // a) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import math
n = int(input())
lis = list(map(int,input().split()))
lis.sort()
nu = []
for i in range(1,math.floor(math.sqrt(lis[0]))+1):
    if lis[0] % i == 0:
        nu.append(lis[0]//i)
        nu.append(i)
nu.sort(reverse = True)
for num in nu:
    key = 1
    for i in range(n):
        if lis[i] % num != 0:
            key = 0
            break
    if key == 1:
        for i in range(n):
            lis[i] = lis[i] // num
        break
nn = 1
for i in range(n):
    nn = (nn * lis[i]) // fractions.gcd(nn,lis[i])
ans = 0
for i in range(n):
    ans += nn//lis[i]
    ans %= 10 ** 9 + 7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

input = sys.stdin.readline

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = Counter()
for a in A: lcm |= prime_factorization(a)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = Counter()
for a in A:
    lcm |= prime_factorization(a)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

read = sys.stdin.read


def sieve_of_eratosthenes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def prime_factorize(n):
    a = []
    for i in primes:
        while n % i == 0:
            a.append(i)
            n //= i
        if n == 1:
            return a


N, *A = map(int, read().split())
mod = 10 ** 9 + 7

primes = sieve_of_eratosthenes(10 ** 6)
dic = {i: 0 for i in primes}

n = len(primes)
p = [0] * n
for i in A:
    if i == 1:
        continue
    tmp = Counter(prime_factorize(i))
    for key, value in tmp.items():
        # print(key, value)
        if dic[key] < value:
            dic[key] = value

lcm = 1
for i, j in dic.items():
    if j == 0:
        continue
    lcm *= pow(i, j, mod)
    lcm %= mod

answer = 0
for i in A:
    answer += lcm * pow(i, mod - 2, mod)
    answer %= mod

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def prime_decomposition(n):
    i = 2
    table = defaultdict(int)
    while i * i <= n:
        while n % i == 0:
            n //= i
            table[i] += 1
        i += 1
    if n > 1:
        table[n] += 1
    return table

def main():
    mod = 10**9 + 7
    N = int(input())
    A = [int(x) for x in input().split()]
    dic = defaultdict(int)
    for i in A:
        prime = prime_decomposition(i)
        for j,k in prime.items():
            if dic[j]<=k:
                dic[j] = k
            else:
                pass
    sub = 1
    for i,j in dic.items():
        sub *= i**j
    ans = 0
    for i in A:
        ans += sub//i
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
import sys

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


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


n = int(sys.stdin.readline())
l = [int(_) for _ in sys.stdin.readline().split()]
x = lcm_list(l)
ans = 0
for i in range(n):
    ans += x // l[i]
    ans %= (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from functools import reduce

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n //= p
            app(p)
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = reduce(lambda x,y: x | y, [prime_factorization(a) for a in A])
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

#arr：最小公倍数の対象とする配列
MOD = 10**9 + 7
def lcm(arr):
    primes = {}
    for val in arr:
        p = 2
        while p * p <= val:
            if val % p == 0:
                cnt = 0
                while val % p == 0:
                    cnt += 1
                    val //= p
                if p not in primes:
                    primes[p] = cnt
                else:
                    primes[p] = max(cnt, primes[p])
            p += 1
     
        if val != 1:
            if val not in primes:
                primes[val] = 1
    lcma = 1
    for p in primes:
        lcma = lcma * pow(p, primes[p], MOD) 
    return lcma

b = lcm(arr)

ans=0
for i in range(n):
    ans+=(b//arr[i])%MOD

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
input = sys.stdin.readline
 
ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]
 
import sys
import numpy as np
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):
    ans = 1
    for num in numbers:
        ans = ans * num // fractions.gcd(ans,num)
    return ans
 
def LI():
  return [int(s) for s in input().split()]
 
input = sys.stdin.readline
ri = lambda: int(input())
ril = lambda: list(map(int, input().split()))
 
N = ri()
A_s = ril()
mod = 10**9 + 7
 
#l = lcm_list(A_s)
l = 1
for num in A_s:
    l = l * num // fractions.gcd(l,num)

print(sum(map(lambda x : l//x, A_s)) % mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
 
 
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
 
 
def lcm(a, b):
    return a * b // gcd(a, b)
 
 
tmp = A[0]
for i in range(1, N):
    tmp = lcm(tmp, A[i])
 
B = [0] * N
for i in range(N):
    B[i] = tmp // A[i]
 
print(sum(B) % mod)

Submission status: Time Limit Exceeded

Solution code:
import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

    lcm_of_all_a = functools.reduce(lambda x, y: lcm(x, y), a, 1)
    # lcm_of_all_a %= mode   # THIS LINE IS KEY POINT

    b = map(lambda x: lcm_of_all_a * inverse(x, mode) % mode, a)
    return sum(b) % mode


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


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

Submission status: Time Limit Exceeded

Solution code:
import sys
 
input = sys.stdin.readline
 
ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

import sys
import numpy as np
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):
    ans = 1
    for num in numbers:
        ans = ans * num // fractions.gcd(ans,num)
    return ans
 
def LI():
  return [int(s) for s in input().split()]
 
 
input = sys.stdin.readline
ri = lambda: int(input())
ril = lambda: list(map(int, input().split()))
 
N = ri()
A_s = ril()
mod = 10**9 + 7
 
l = lcm_list(A_s)
 
print(sum(map(lambda x : l//x, A_s)) % mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
m=int(input())
a=list(map(int,input().split()))
a.sort()
def lcm_base(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm_list(numbers):
    return reduce(lcm_base,numbers,1)
mod=10**9+7
n=lcm_list(a)
ans=0
for i in range(m):
    ans+=(n//a[i])
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from functools import reduce

def modular_inverse(a, mod):
    return pow(a, mod-2, mod)

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = Counter()
    if n < 2:
        return result
    while n % 2 == 0:
        result[2] += 1
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n //= p
            result[p] += 1
        p += 2
    if n > 1:
        result[n] += 1
    return result

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = reduce(lambda x,y: x | y, [prime_factorization(a) for a in A])
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
mod =M
import sys
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

from collections import defaultdict
N=input()
xs = map(int, input().split())
ys = []
d = defaultdict(int)
for x in xs:
    ps = prime_decomposition(x)
    psd = defaultdict(int)
    for p, c in ps:
        psd[p] = c
        d[p] = max(d[p], c)
    ys.append(psd)
r = 0
for ps in ys:
    t = 1
    for p in d:
        t = t*p**(d[p]-ps[p])
    r = (r+t)
print(r%M)