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:
#!/usr/bin/python3
# import bisect
# from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n=int(input())
    A=list(map(int,input().split()))

    from functools import reduce
    from math import gcd
    
    def lcm(A, B):
        return A * B // gcd(A, B)
    
    
    # リストを引数にとる
    val=reduce(lcm, A)
    ans=0
    MOD=10**9+7
    for i in A:
        ans+=val//i
        ans%=MOD
    print(ans%MOD)
    
resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))




    n = 10 ** 6
    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
    prime_list = [i for i in range(n + 1) if is_prime[i]]




    lcm_dic = {}
    Alist = []

    for a in A:
        a_dic = {}
        for num in prime_list:
            if num > a ** 0.5 + 1:
                if a in a_dic:
                    a_dic[a] += 1
                    break
                else:
                    a_dic[a] = 1
                    break
            while a % num == 0:
                if num in a_dic:
                    a //= num
                    a_dic[num] += 1
                else:
                    a //= num
                    a_dic[num] = 1
        Alist.append(a_dic)
        for k, v in a_dic.items():
            if k not in lcm_dic:
                lcm_dic[k] = v
            else:
                lcm_dic[k] = max(lcm_dic[k], v)

    ans = 0
    for ad in Alist:
        tmpnum = 1
        for k, v in lcm_dic.items():
            if k in ad:
                tmpnum *= k ** (v - ad[k])
            else:
                tmpnum *= k ** v
        ans += tmpnum
    ans %= mod
    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

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

    def lcm(x, y):
        return (x * y) // gcd(x, y)
    for a in A:
        lcmnum = lcm(lcmnum, a)

    ans = 0
    for a in A:
        a = lcmnum // a
        a %= mod
        ans += a
        ans %= mod

    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))




    n = 10 ** 6
    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
    prime_list = [i for i in range(n + 1) if is_prime[i]]




    lcm_dic = {}
    Alist = []

    for a in A:
        a_dic = {}
        for num in prime_list:
            if num > a ** 0.5 + 1:
                if a in a_dic:
                    a_dic[a] += 1
                    break
                else:
                    a_dic[a] = 1
                    break
            while a % num == 0:
                if num in a_dic:
                    a //= num
                    a_dic[num] += 1
                else:
                    a //= num
                    a_dic[num] = 1
        Alist.append(a_dic)
        for k, v in a_dic.items():
            if k not in lcm_dic:
                lcm_dic[k] = v
            else:
                lcm_dic[k] = max(lcm_dic[k], v)

    ans = 0
    for ad in Alist:
        tmpnum = 1
        for k, v in lcm_dic.items():
            if k in ad:
                tmpnum *= pow(k, (v - ad[k]), mod)
                tmpnum %= mod
            else:
                tmpnum *= pow(k, v, mod)
                tmpnum %= mod
        ans += tmpnum
        ans %= mod
    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))




    n = 10 ** 6
    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
    prime_list = [i for i in range(n + 1) if is_prime[i]]




    lcm_dic = {}
    Alist = []

    for a in A:
        a_dic = {}
        for num in prime_list:
            if num > a ** 0.5 + 1:
                if a in a_dic:
                    a_dic[a] += 1
                    break
                else:
                    a_dic[a] = 1
                    break
            while a % num == 0:
                if num in a_dic:
                    a //= num
                    a_dic[num] += 1
                else:
                    a //= num
                    a_dic[num] = 1
        Alist.append(a_dic)
        for k, v in a_dic.items():
            if k not in lcm_dic:
                lcm_dic[k] = v
            else:
                lcm_dic[k] = max(lcm_dic[k], v)

    ans = 0
    for ad in Alist:
        tmpnum = 1
        for k, v in lcm_dic.items():
            if k in ad:
                tmpnum *= pow(k, (v - ad[k]), mod)
            else:
                tmpnum *= pow(k, v, mod)
        ans += tmpnum
        ans %= mod
    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    n = 10 ** 6
    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
    prime_list = [i for i in range(n + 1) if is_prime[i]]

    lcm_dic = {}
    Alist = []

    for a in A:
        a_dic = {}
        for num in prime_list:
            if num > a ** 0.5 + 1:
                if a in a_dic:
                    a_dic[a] += 1
                    break
                else:
                    a_dic[a] = 1
                    break
            while a % num == 0:
                if num in a_dic:
                    a //= num
                    a_dic[num] += 1
                else:
                    a //= num
                    a_dic[num] = 1
        Alist.append(a_dic)
        for k, v in a_dic.items():
            if k not in lcm_dic:
                lcm_dic[k] = v
            else:
                lcm_dic[k] = max(lcm_dic[k], v)

    ans = 0
    for ad in Alist:
        tmpnum = 1
        for k, v in lcm_dic.items():
            if k in ad:
                tmpnum *= k ** (v - ad[k])
                tmpnum %= mod
            else:
                tmpnum *= k ** v
                tmpnum %= mod
        ans += tmpnum
        ans %= mod
    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    def primes(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]]

    prime_list = primes(max(A)+1)

    lcm_dic = {}
    Alist = []

    for a in A:
        a_dic = {}
        for num in prime_list:
            if num > a ** 0.5 + 1:
                if a in a_dic:
                    a_dic[a] += 1
                    break
                else:
                    a_dic[a] = 1
                    break
            while a % num == 0:
                if num in a_dic:
                    a //= num
                    a_dic[num] += 1
                else:
                    a //= num
                    a_dic[num] = 1
        Alist.append(a_dic)
        for k, v in a_dic.items():
            if k not in lcm_dic:
                lcm_dic[k] = v
            else:
                lcm_dic[k] = max(lcm_dic[k], v)

    ans = 0
    for ad in Alist:
        tmpnum = 1
        for k, v in lcm_dic.items():
            if k in ad:
                tmpnum *= k ** (v - ad[k])
                tmpnum %= mod
            else:
                tmpnum *= k ** v
                tmpnum %= mod
        ans += tmpnum
        ans %= mod
    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    def primes(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]]

    prime_list = primes(10**6)

    lcm_dic = {}
    Alist = []

    for a in A:
        a_dic = {}
        for num in prime_list:
            if num > a ** 0.5 + 1:
                if a in a_dic:
                    a_dic[a] += 1
                    break
                else:
                    a_dic[a] = 1
                    break
            while a % num == 0:
                if num in a_dic:
                    a //= num
                    a_dic[num] += 1
                else:
                    a //= num
                    a_dic[num] = 1
        Alist.append(a_dic)
        for k, v in a_dic.items():
            if k not in lcm_dic:
                lcm_dic[k] = v
            else:
                lcm_dic[k] = max(lcm_dic[k], v)

    ans = 0
    for ad in Alist:
        tmpnum = 1
        for k, v in lcm_dic.items():
            if k in ad:
                tmpnum *= k ** (v - ad[k])
                tmpnum %= mod
            else:
                tmpnum *= k ** v
                tmpnum %= mod
        ans += tmpnum
        ans %= mod
    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    def primes(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]]

    prime_list = primes(10**6)

    lcm_dic = {}
    Alist = []
    for a in A:
        a_dic = {}
        for num in prime_list:
            while a % num == 0:
                if num in a_dic:
                    a //= num
                    a_dic[num] += 1
                else:
                    a //= num
                    a_dic[num] = 1
        Alist.append(a_dic)
        for k, v in a_dic.items():
            if k not in lcm_dic:
                lcm_dic[k] = v
            else:
                lcm_dic[k] = max(lcm_dic[k], v)

    ans = 0
    for ad in Alist:
        tmpnum = 1
        for k, v in lcm_dic.items():
            if k in ad:
                tmpnum *= k ** (v - ad[k])
                tmpnum %= mod
            else:
                tmpnum *= k ** v
                tmpnum %= mod
        ans += tmpnum
        ans %= mod
    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

mod = pow(10,9)+7
ok = 1

import math

for a in A:
    ok = ok*a//math.gcd(a,ok)

LCM = ok



counter = 0
for a in A:
    counter += LCM//a
    counter %= mod 

print(counter)

Submission status: Time Limit Exceeded

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

mod = pow(10,9)+7

from functools import reduce
import math

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

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

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


LCM = lcm_list(A)



counter = 0
for a in A:
    counter += LCM//a
    counter %= mod 

print(counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    gcdnum = 1
    gcd = math.gcd

    for a in A:
        gcdnum = (gcdnum * a) // gcd(gcdnum, a)
    ans = 0
    for a in A:
        a = gcdnum // a
        a %= mod
        ans += a
    ans %= mod

    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))
    Aset = set(A)

    gcdnum = 1
    gcd = math.gcd

    for a in Aset:
        gcdnum = (gcdnum * a) // gcd(gcdnum, a)
    ans = 0
    for a in A:
        a = gcdnum // a
        ans += a
        ans %= mod

    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    gcdnum = 1
    gcd = math.gcd

    for a in A:
        gcdnum = (gcdnum * a) // gcd(gcdnum, a)
    ans = 0
    for a in A:
        a = gcdnum // a
        ans += a
        ans %= mod

    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    N = int(readline())
    A = list(map(int, readline().split()))

    gcdnum = 1
    gcd = math.gcd

    def lcm(x, y):
        return (x * y) // gcd(x, y)
    for a in A:
        gcdnum = lcm(gcdnum, a)
    ans = 0
    for a in A:
        a = gcdnum // a
        ans += a
        ans %= mod

    print(ans)




if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    from functools import reduce

    # 最小公倍数
    def lcm_base(x, y):
        return (x * y) // math.gcd(x, y)

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

    n = ni()
    a = na()
    # a.sort()

    lcm = lcm_list(a)

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    from functools import reduce

    # 最小公倍数
    def lcm_base(x, y):
        return (x * y) // math.gcd(x, y)

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

    n = ni()
    a = na()
    a.sort()

    lcm = lcm_list(a)

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    from functools import reduce

    tmp = [2, 4, 6, 8]
    gcdans = reduce(fractions.gcd, tmp)

    # 最小公倍数
    def lcm_base(x, y):
        return (x * y) // math.gcd(x, y)

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

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

    n = ni()
    a = na()

    lcm = lcm_list(a)

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import *

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

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

s = 1

for i in range(n):
    x = a[i]
    for z in range(2,int(sqrt(a[i])+1)):
        t = 1
        while(x%z==0):
            t *= z
            x /= z
        while(s%t != 0):
            s *= z
    if(x > 1 and s%x!=0):
        s *= x

k = 0
for i in a:
    k += s//i
    k %= (1000000000+7)

print(k%(1000000000+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
readlines = sys.stdin.readline
def main():
	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

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

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

	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):
	while b!=0:
		a,b=b,a%b
	return a

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

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

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math

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

A.sort()

lcm = A[0]
for i in range(1,n):
    lcm = (lcm*A[i])//math.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:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
from math import gcd
ans=a[0]
for i in range(1,n):
  ans=ans*a[i]//gcd(ans,a[i])
s=0
for j in range(n):
  s+=(ans//a[j])%mod
print(s%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys 
from functools import reduce
from math import gcd
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7
N = int(readline())
A = list(map(int,readline().split()))
lcm = reduce(lambda x,y:x*y//gcd(x,y),A)
ans = 0
for i in range(N):
    ans += lcm//A[i]%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from math import gcd
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    mod = 1000000007

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

    lcm = 1
    for i in A:
        lcm = lcm * i // gcd(lcm, i)

    ans = 0
    for i in A:
        ans += lcm // i
        ans %= mod

    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from math import gcd
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    mod = 1000000007

    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:
import sys 
from math import gcd
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7
N = int(readline())
A = list(map(int,readline().split()))
def lcm(N,a):
    x = a[0]
    for i in range(1, N):
        x = (x * a[i]) // gcd(x, a[i])
    ans = 0 
    for i in range(N):
        ans += x // a[i] % mod
    return ans%mod
ans = lcm(N,A)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys 
from math import gcd
# from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7
N = int(readline())
A = list(map(int,readline().split()))
# @jit(cache=True)
def lcm(N,a):
    x = a[0]
    for i in range(1, N):
        x = (x * a[i]) // gcd(x, a[i])
    ans = 0 
    for i in range(N):
        ans += x // a[i] % mod
    return ans%mod
ans = lcm(N,A)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#

import sys
input=sys.stdin.readline

MOD=10**9+7
kl = [0]*(10**6+1)

            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    for j in range(N):
        n=A[j]
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n//=i
                    cnt+=1
                if kl[i]<cnt:
                    kl[i]=cnt
        if n!=1:
            if kl[n]<1:
                kl[n]=1
                
    lcm=1
    for i in range(2,10**6+1):
        lcm*=pow(i, kl[i], MOD)

    modsum=0
    for i in range(N):
        modsum+=pow(A[i],MOD-2,MOD)

    ans = lcm*modsum%MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#

import sys
input=sys.stdin.readline

MOD=10**9+7
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    kl=set()
    p=[{} for i in range(N)]
    for j in range(N):
        n=A[j]
        ret={}
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n/=i
                    cnt+=1
                ret[i]=cnt
                kl.add(i)
        if n!=1:
            ret[int(n)]=1
            kl.add(int(n))
        p[j]=ret
    lcm=1
    for i in kl:
        maxipow=0
        for j in range(N):
            if maxipow < p[j].get(i,0):
                maxipow=p[j].get(i,0)
        lcm*=i**maxipow
        lcm%=MOD

    lcm%=MOD
    ans=0
    for i in range(N):
        ans+=lcm*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#

import sys
input=sys.stdin.readline

MOD=10**9+7
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    kl=set()
    p=[{} for i in range(N)]
    for j in range(N):
        n=A[j]
        ret={}
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n/=i
                    cnt+=1
                ret[i]=cnt
                kl.add(i)
        if n!=1:
            ret[int(n)]=1
            kl.add(int(n))
        p[j]=ret
    lcm=1
    for i in kl:
        maxipow=0
        for j in range(N):
            maxipow=max(maxipow,p[j].get(i,0))
        lcm*=i**maxipow
        lcm%=MOD

    lcm%=MOD
    ans=0
    for i in range(N):
        ans+=lcm*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#

import sys
input=sys.stdin.readline

kl=set()

            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    kl=set()
    p=[{} for i in range(N)]
    for j in range(N):
        n=A[j]
        ret={}
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n/=i
                    cnt+=1
                ret[i]=cnt
                kl.add(i)
        if n!=1:
            ret[int(n)]=1
            kl.add(int(n))
        p[j]=ret
    lcm=1
    for i in kl:
        maxipow=0
        for j in range(N):
            maxipow=max(maxipow,p[j].get(i,0))
        lcm*=i**maxipow
    MOD=10**9+7
    lcm%=MOD
    ans=0
    for i in range(N):
        ans+=lcm*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#

import sys
input=sys.stdin.readline

kl=set()

def pf(n):
    ret={}
    for i in range(2,int((n)**0.5)+1):
        if n%i==0:
            cnt=0
            while(n%i==0):
                n/=i
                cnt+=1
            ret[i]=cnt
            kl.add(i)
    if n!=1:
        ret[int(n)]=1
        kl.add(int(n))
    return ret
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    p=[{} for i in range(N)]
    for i in range(N):
        p[i]=(pf(A[i]))
    lcm=1
    for i in kl:
        maxipow=0
        for j in range(N):
            maxipow=max(maxipow,p[j].get(i,0))
        lcm*=i**maxipow
    MOD=10**9+7
    lcm%=MOD
    ans=0
    for i in range(N):
        ans+=lcm*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#

import sys
input=sys.stdin.readline

kl=set()

def pf(n):
    ret={}
    for i in range(2,int((n)**0.5)+1):
        if n%i==0:
            cnt=0
            while(n%i==0):
                n/=i
                cnt+=1
            ret[i]=cnt
            kl.add(i)
    if n!=1:
        ret[int(n)]=1
        kl.add(int(n))
    return ret
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    p=[{} for i in range(N)]
    for i in range(N):
        p[i]=(pf(A[i]))
    lcm=1
    for i in kl:
        maxipow=0
        for j in range(N):
            maxipow=max(maxipow,p[j].get(i,0))
        lcm*=i**maxipow
    ans=0
    for i in range(N):
        bi=lcm//A[i]
        ans+=bi
        ans%=10**9+7
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#

import sys
from fractions import gcd
input=sys.stdin.readline

def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    l=(A[0]*A[1])//gcd(A[0],A[1])
    
    for i in range(2,N):
        l=(l*A[i])//gcd(A[i],l-A[i])
    ans=0
    for i in range(N):
        bi=l//A[i]
        ans+=bi
        ans%=10**9+7
    print(ans)
    
    
    
if __name__=="__main__":
    main()