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
from functools import reduce
from copy import deepcopy


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

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

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

def resolve():
    N=int(input())
    A=map(int,input().split())
    B=deepcopy(A)
    lcm=lcm_list(A)
    B=[(lcm//i)%1000000007 for i in B]
    sm=0 

    for i in B:
        sm=(sm+i)%1000000007
    print(sm)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#ふるい
def primes(max_number):
    pr = list(range(3, max_number + 1,2))
    npr = len(pr)
    for i, n in enumerate(pr):
        if n:
            if n*n > max_number:
                break
            for j in range(i+n, npr,n):
                pr[j] = 0
    if max_number >= 2:
        yield 2
    yield from [i for i in pr if i]

#ある素因数が何個含まれるか
def get_coef_num(a,pr):
    num = 0
    while True:
        if((a%pr)==0):
            a = a//pr
            num+=1
        else:
            break
    return num


N = int(input())
A = list(map(int, input().split()))
#B = A.copy()
pr_list = list(primes(10**6))
#print(f'#ofPR:{len(pr_list)}')

coef_list = [0]*(len(pr_list))

for a in A:
    for i,pr in enumerate(pr_list):
        if a < pr:
            break
        temp = get_coef_num(a,pr)
        if coef_list[i]<temp :
            coef_list[i] = temp
#print(coef_list)

LCM = 1
for pr,num in zip(pr_list,coef_list):
    if num!=0:
        LCM*=(pr**num)
#print(LCM)

sum_B = 0
for a in A:
    #B[i] = (LCM//a)
    sum_B += (LCM//a)%(10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
#ふるい
def primes(max_number):
    pr = list(range(3, max_number + 1,2))
    npr = len(pr)
    for i, n in enumerate(pr):
        if n:
            if n*n > max_number:
                break
            for j in range(i+n, npr,n):
                pr[j] = 0
    if max_number >= 2:
        yield 2
    yield from [i for i in pr if i]

#ある素因数が何個含まれるか
def get_coef_num(a,pr):
    num = 0
    while True:
        if((a%pr)==0):
            a = a//pr
            num+=1
        else:
            break
    return num


N = int(input())
A = list(map(int, input().split()))
#B = A.copy()
pr_list = list(primes(10**6))
#print(f'#ofPR:{len(pr_list)}')

coef_list = [0]*(len(pr_list))

for a in A:
    for j,pr in enumerate(pr_list):
        temp = get_coef_num(a,pr)
        if coef_list[j]<temp :
            coef_list[j] = temp
#print(coef_list)

LCM = 1
for pr,num in zip(pr_list,coef_list):
    if num!=0:
        LCM*=(pr**num)
#print(LCM)

sum_B = 0
for a in A:
    #B[i] = (LCM//a)
    sum_B += (LCM//a)%(10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
#ふるい
def primes(max_number):
    pr = list(range(3, max_number + 1,2))
    npr = len(pr)
    for i, n in enumerate(pr):
        if n:
            if n*n > max_number:
                break
            for j in range(i+n, npr,n):
                pr[j] = 0
    if max_number >= 2:
        yield 2
    yield from [i for i in pr if i]

#ある素因数が何個含まれるか
def get_coef_num(a,pr):
    num = 0
    while True:
        if((a%pr)==0):
            a = a//pr
            num+=1
        else:
            break
    return num


N = int(input())
A = list(map(int, input().split()))
B = A.copy()
pr_list = list(primes(10**6))
#print(f'#ofPR:{len(pr_list)}')

coef_list = [[0]*N for i in range(len(pr_list))]

for i,a in enumerate(A):
    for j,pr in enumerate(pr_list):
        coef_list[j][i] = get_coef_num(a,pr)
#print(coef_list)

LCM = 1
for i,pr in enumerate(pr_list):
        LCM*=(pr**max(coef_list[i]))
#print(LCM)

for i,a in enumerate(A):
    B[i] = (LCM//a)
#print(B)

print(sum(B)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)
def lcm(x, y):
    return (x * y) // gcd(x, y)

MOD = int(1e9 + 7)

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

LCM = 1

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

Submission status: Time Limit Exceeded

Solution code:
from  fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

MOD = int(1e9 + 7)

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

LCM = 1

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

Submission status: Time Limit Exceeded

Solution code:
from  fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

MOD = int(1e9 + 7)

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

LCM = 1

for i in range(N):
    LCM = lcm(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:
from  fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

MOD = int(1e9 + 7)

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

LCM = 1

for i in range(N):
    LCM = lcm(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:
from functools import reduce

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

N = int(input())
*A, = map(int, input().split())
mod = 10**9 + 7
lcm = reduce(lambda a,b: a*b//gcd(a,b), A)

print(sum(map(lambda x: lcm//x, A))%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

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

lcm = reduce(lambda a,b: a*b//gcd(a,b), A)
print(sum(map(lambda x: lcm//x, A))%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

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

lcm = reduce(lambda a,b: a*b//gcd(a,b), A)
ans = 0

for n in map(lambda x: lcm//x, A):
    ans += n
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

LARGE_INT = 10 ** 9 + 7

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

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

input()
A = list(map(int, input().split()))
lcm = lcm_list(A)

total = 0
for a in A:
    total += lcm // a % LARGE_INT
    total %= LARGE_INT
print(total)

Submission status: Time Limit Exceeded

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

LARGE_INT = 10 ** 9 + 7

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

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

input()
A = list(map(int, input().split()))
lcm = lcm_list(A)

total = 0
for a in A:
    total += lcm // a % LARGE_INT
    total %= LARGE_INT
print(total)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

def lcm_pair(a, b):
    return int((a * b) // gcd(a, b))

def lcm(nums):
    if len(nums) > 1:
        l = lcm_pair(nums[0], nums[1])
        for num in nums[2:]:
            l = lcm_pair(l, num)
        return l
    else:
        return nums[0]

def gcd_list(nums):
    g = gcd(nums[0], nums[1])
    for num in nums[2:]:
        g = gcd(g, num)
    return g

def solve(n, a):
    if n == 1:
        return [1]
    elif n == 2:
        return a
    elif len(set(a)) == 1:
        return [1] * n
    else:
        b = [a[1]] + [lcm_pair(a[i-1], a[i+1]) for i in range(1, n-1)] + [a[-2]]
        gcd_b = gcd_list(b)
        b = [int(x // gcd_b) for x in b]
        c = lcm(list(map(lambda x, y: x * y, a, b)))
        b = [int(c // x) for x in a]
        gcd_b = gcd_list(b)
        return [int(x // gcd_b) for x in b]

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

print(sum(solve(n, a)) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

def lcm_pair(a, b):
    return int((a * b) // gcd(a, b))

def lcm(nums):
    if len(nums) > 1:
        l = lcm_pair(nums[0], nums[1])
        for num in nums[2:]:
            l = lcm_pair(l, num)
        return l
    else:
        return nums[0]

def solve(n, a):
    if n == 1:
        return [1]
    elif n == 2:
        return a
    elif len(set(a)) == 1:
        return [1] * n
    else:
        b = [a[1]] + [lcm_pair(a[i-1], a[i+1]) for i in range(1, n-1)] + [a[-2]]
        gcd_b = reduce(lambda x, y: gcd(x, y), b)
        b = [int(x // gcd_b) for x in b]
        c = lcm(list(map(lambda x, y: x * y, a, b)))
        b = [int(c // x) for x in a]
        gcd_b = reduce(lambda x, y: gcd(x, y), b)
        return [int(x // gcd_b) for x in b]

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

print(sum(solve(n, a)) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/abc145/tasks/abc145_e
# E - All-you-can-eat
"""

"""


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


N = gi()
A = [0] * N

for i in range(N):
    A[i] = gi()

lcm = A[0]

for i in range(1, N):
    d = gcd(A[i], lcm)
    lcm = (lcm // d) * (A[i] // d) * d

ans = 0

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

Submission status: Time Limit Exceeded

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/abc145/tasks/abc145_e
# E - All-you-can-eat
"""

"""


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


N = gi()
A = [0] * N

for i in range(N):
    A[i] = gi()

lcm = A[0]

for i in range(1, N):
    d = gcd(A[i], lcm)
    lcm = (lcm // d) * (A[i] // d) * d

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
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
lcm = 1
for a in A:
    lcm *= a / gcd(lcm, a)
print(int(np.sum(1/A * lcm) % (1e9 + 7)))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


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


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


# N個最小公倍数
def lcm_n(A, N):
    # A = sorted(A)
    ans = A[0]
    # for i in range(1, N):
    #     ans = fractions.gcd(A[i], ans)
    for i in range(1, N):
        ans = lcm(ans, A[i])
    return ans

# 逆元
def modinv(a):
    return pow(a, MOD-2, MOD)


def main():
    N = I()
    A = LI()
    ans = 0

    a = lcm_n(A, N)

    for i in range(N):
        ans += (a * modinv(A[i])) % MOD

    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


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


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

# N個最小公倍数


def lcm_n(A, N):
    # A = sorted(A)
    ans = A[0]
    # for i in range(1, N):
    #     ans = fractions.gcd(A[i], ans)
    for i in range(1, N):
        ans = lcm(ans, A[i])
    return ans


def main():
    N = I()
    A = LI()
    ans = 0

    a = lcm_n(A, N)

    for i in range(N):
        ans += (a // A[i]) % MOD

    print(ans % MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
from fractions import gcd
from functools import reduce
 
n,*alst = list(map(int, read().split()))

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

g = reduce(lcm, alst)
mod=10**9+7
res=0
for a in alst:
  res+=pow(a,mod-2,mod)*g
  res%=mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
#E - Flatten
import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = [int(i) for i in input().split()]
from fractions import gcd
def lcm(a):
    x = a[0]
    x = float(x)
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return float(x)
A_lcm = lcm(A)
cnt = 0
cnt = float(cnt)
for i in range(N):
    cnt += A_lcm/A[i]
print(int(cnt%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
#E - Flatten
import sys
sys.setrecursionlimit(10**6)
N = int(input())
A = [int(i) for i in input().split()]
from fractions import gcd
def lcm(a):
    x = a[0]
    x = float(x)
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return float(x)
A_lcm = lcm(A)
cnt = 0
cnt = float(cnt)
for i in range(N):
    cnt += A_lcm/A[i]
print(int(cnt%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]
MOD = 10**9 + 7


def gcd(a, b):
    """ Greatest Common Divisor(最大公約数) """
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    """ Least Common Multiple(最小公倍数) """
    return a * (b // gcd(a, b))


N = _i()
a_list = _li()

a_lcm = 1
for a in a_list:
    a_lcm = lcm(a_lcm, a)

ans = 0
for a in a_list:
    ans = (ans + a_lcm // a) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
#リストの最小公倍数
def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort()
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) #B[0]
answer = x%MOD

for i in range(1, N):
    answer += first * x // A[i]

print(answer%MOD)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
# import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]
MOD = 10**9 + 7


def gcd(a, b):
    """ Greatest Common Divisor(最大公約数) """
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    """ Least Common Multiple(最小公倍数) """
    return a * b // gcd(a, b)


N = _i()
a_list = _li()

a_lcm = 1
for a in a_list:
    a_lcm = lcm(a_lcm, a)

ans = 0
for a in a_list:
    ans = (ans + a_lcm // a) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys

MOD = 1000000007
N = int(input())
A = [int(x) for x in input().split()]
L = A[0]
for i in range(1,len(A)):
    L = L*A[i] // fractions.gcd(L,A[i])
res = 0
for i in range(len(A)):
    res += L // A[i] % MOD
    res %= MOD
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def fastio():
    import sys
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    def input(): return sys.stdin.readline().rstrip()
    sys.stdout = StringIO()
    register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))


fastio()
M = 10**9+7

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


def modexp(a, b, m):
    a %= m
    res = 1
    while b > 0:
        if b & 1:
            res = res*a % m

        a = a*a % m
        b >>= 1
    return res


def primeFactors(n):
    factors = defaultdict(int)
    while not n & 1:
        factors[2] += 1
        n //= 2

    for i in range(3, int(n**0.5)+1, 2):
        while n % i == 0:
            factors[i] += 1
            n //= i
    if n > 2:
        factors[n] += 1

    return factors


for i in a:
    p = primeFactors(i)
    for f in p:
        L[f] = max(L[f], p[f])

ans = 0
for i in a:
    p = primeFactors(i)
    b = 1
    for f in L:
        b *= modexp(f, L[f]-p[f], M)
        b %= M
    ans += b
    ans %= M

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
M = 10**9+7

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


def modexp(a, b, m):
    a %= m
    res = 1
    while b > 0:
        if b & 1:
            res = res*a % m

        a = a*a % m
        b >>= 1
    return res


def primeFactors(n):
    factors = defaultdict(int)
    while not n & 1:
        factors[2] += 1
        n //= 2

    for i in range(3, int(n**0.5)+1, 2):
        while n % i == 0:
            factors[i] += 1
            n //= i
    if n > 2:
        factors[n] += 1

    return factors


for i in a:
    p = primeFactors(i)
    for f in p:
        L[f] = max(L[f], p[f])

ans = 0
for i in a:
    p = primeFactors(i)
    b = 1
    for f in L:
        b *= modexp(f, L[f]-p[f], M)
        b %= M
    ans += b
    ans %= M

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
M = 10**9+7

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


def primeFactors(n):
    factors = defaultdict(int)
    while not n & 1:
        factors[2] += 1
        n //= 2

    for i in range(3, int(n**0.5)+1, 2):
        while n % i == 0:
            factors[i] += 1
            n //= i
    if n > 2:
        factors[n] += 1

    return factors


for i in a:
    p = primeFactors(i)
    for f in p:
        L[f] = max(L[f], p[f])

ans = 0
for i in a:
    p = primeFactors(i)
    b = 1
    for f in L:
        b *= f**(L[f]-p[f])
        b %= M
    ans += b
    ans %= M

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted(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))

now = a[0]
for i in range(1, n):
    now = lcm(max(now, a[i]), min(now, a[i]))
result = 0
for i in range(n):
    result =(result + now // a[i])%mod
print(result)

Submission status: Time Limit Exceeded

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

mod = 10**9+7
inmax = max(a)

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

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

now = a[0]
for i in range(1, n):
    now = lcm(max(now, a[i]), min(now, a[i]))
result = 0
for i in range(n):
    result =(result + now // a[i])%mod
print(result)

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])
    
b = [lcm // ai  for ai in a]
s = 0
for bi in b:
  	s = (s+bi) % mod
print(s % mod)

Submission status: Time Limit Exceeded

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

from fractions import gcd
from functools import reduce

# functions
def lcm(x, y):
    if x % y == 0:
        return x
    elif y % x == 0:
        return y
    else:
        return (x * y) // gcd(x, y)

# const
THRESHOLED = 10**9+7

# input
N = int(input())
nums = list(map(int, input().split()))

# calculate lcm_num
lcm_num = reduce(lcm, nums)

# make answer
ans = 0
for n in nums:
    ans += lcm_num//n
    if ans >= THRESHOLED:
        ans = ans%THRESHOLED

print(ans)

Submission status: Time Limit Exceeded

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

from fractions import gcd
from functools import reduce

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

# const
THRESHOLED = 10**9+7

# input
N = int(input())
nums = list(map(int, input().split()))

# calculate lcm_num
nums.sort()
#nums.sort(reverse=True)
lcm_num = reduce(lcm, list(set(nums)))

# make answer

ans = 0
for n in nums:
    ans += lcm_num//n
    if ans >= THRESHOLED:
        ans = ans%THRESHOLED

print(ans)

Submission status: Time Limit Exceeded

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

from fractions import gcd
from functools import reduce

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

# const
THRESHOLED = 10**9+7

# input
N = int(input())
nums = list(map(int, input().split()))

# calculate lcm_num
nums.sort()
#nums.sort(reverse=True)
lcm_num = reduce(lcm, nums)

# make answer

ans = 0
for n in nums:
    ans += lcm_num//n
    if ans >= THRESHOLED:
        ans = ans%THRESHOLED

print(ans)

Submission status: Time Limit Exceeded

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

from fractions import gcd
from functools import reduce

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

# const
THRESHOLED = 10**9+7

# input
N = int(input())
nums = list(map(int, input().split()))

# calculate lcm_num
lcm_num = reduce(lcm, nums)

# make answer

ans = 0
for n in nums:
    ans += lcm_num//n
    if ans >= THRESHOLED:
        ans = ans%THRESHOLED

print(ans)

Submission status: Time Limit Exceeded

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

MAXN = 10**6+10
facts = [-1,-1] + [0]*MAXN
p = 2
while p*p <= MAXN:
    if facts[p] == 0:
        for q in range(p*p,MAXN+1,p):
            if facts[q]==0:
                facts[q] = p
    p += 1

from collections import Counter
ctr = Counter()
for a in A:
    c = Counter()
    while facts[a] > 0:
        c[facts[a]] += 1
        a //= facts[a]
    c[a] += 1
    ctr |= c

ans = 0
for a in A:
    c = Counter()
    while facts[a] > 0:
        c[facts[a]] += 1
        a //= facts[a]
    c[a] += 1
    t = 1
    for k,v in (ctr - c).items():
        t *= k**v
    ans += t
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

MAXN = 10**6+10
facts = [-1,-1] + [0]*MAXN
p = 2
while p*p <= MAXN:
    if facts[p] == 0:
        for q in range(p*p,MAXN+1,p):
            if facts[q]==0:
                facts[q] = p
    p += 1

from collections import Counter
ctr = Counter()
cs = [Counter() for i in range(N)]
for i,a in enumerate(A):
    while facts[a] > 0:
        cs[i][facts[a]] += 1
        a //= facts[a]
    cs[i][a] += 1
    ctr |= cs[i]

ans = 0
for c in cs:
    t = 1
    for k,v in (ctr - c).items():
        t *= k**v
    ans += t
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

MAXN = 10**6+10
facts = [-1,-1] + [0]*MAXN
p = 2
while p*p <= MAXN:
    if facts[p] == 0:
        for q in range(p*p,MAXN+1,p):
            if facts[q]==0:
                facts[q] = p
    p += 1

from collections import Counter
ctr = Counter()
for a in A:
    c = Counter()
    while facts[a] > 0:
        c[facts[a]] += 1
        a //= facts[a]
    c[a] += 1
    ctr |= c
l = 1
for k,v in ctr.items():
    l *= k**v
ans = 0
for a in A:
    ans += l//a
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

MAXN = 10**6+10
facts = [-1,-1] + [0]*MAXN
p = 2
while p*p <= MAXN:
    if facts[p] == 0:
        for q in range(p*p,MAXN+1,p):
            if facts[q]==0:
                facts[q] = p
    p += 1

from collections import Counter
ctr = Counter()
for a in A:
    c = Counter()
    while facts[a] > 0:
        c[facts[a]] += 1
        a //= facts[a]
    c[a] += 1
    ctr |= c
l = 1
for k,v in ctr.items():
    l *= k**v
ans = 0
for a in A:
    ans += l//a
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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


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


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

LCM = A[0]

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

ans = 0
for i in range(N):
    ans += LCM // A[i]
    ans %= MOD

# print(LCM)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#GCD, LCM
def gcd_base(a, b):
    while b!=0:
        a, b = b, a%b
    return a

def lcm(num_list):
    ans = 1
    for i in num_list:
        ans = ans * i // gcd_base(ans, i)
    return ans

n = int(input())
a = list(map(int, input().split()))
l = lcm(a)
mod = 10**9+7
total = 0
for i in a:
    total += l//i
    total %= mod
print(total)

Submission status: Time Limit Exceeded

Solution code:
#GCD, LCM
def gcd_base(a, b):
    while b!=0:
        a, b = b, a%b
    return a

def lcm(num_list):
    ans = 1
    for i in num_list:
        ans = ans * i // gcd_base(ans, i)
    return ans

n = int(input())
a = list(map(int, input().split()))
b = list(set(a))
l = lcm(b)
mod = 10**9+7
total = 0
for i in a:
    total += l//i
    if total > mod:
        total %= mod
print(total)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout
 
ii = lambda: int(stdin.readline())
mi = lambda: map(int, stdin.readline().strip().split())
li = lambda: list(mi())

mod = int(1e9) + 7

def GCD(x, y): 
  
   while(y): 
       x, y = y, x % y 
  
   return x 

N = ii()
A = li()
lcm = A[0]
for i in range(1, len(A)):
	lcm = (lcm // GCD(lcm, A[i])) * A[i]

ans = 0
for i in range(0, len(A)):
	ans = (ans + (lcm // A[i])) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = defaultdict(int)
ans = 0

for i in range(N):
    tmp = 1
    a = A[i]
    g_tmp = defaultdict(int)
    while tmp <= A[i] ** 0.5:
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            if tmp not in g_tmp:
                g_tmp[tmp] = 1
            else:
                g_tmp[tmp] += 1
        tmp += 1
    if a > 1:
        if a not in g_tmp:
            g_tmp[a] = 1
        else:
            g_tmp[a] += 1

    for j in g_tmp:
        if j not in g:
            g[j] = g_tmp[j]
        else:
            g[j] = max(g[j], g_tmp[j])

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod)
    l % mod
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]

mod = 10 ** 9 + 7
g = defaultdict(int)
ans = 0

for i in range(N):
    tmp = 1
    a = A[i]
    g_tmp = defaultdict(int)
    while tmp <= A[i] ** 0.5:
        while tmp > 1 and a % tmp == 0:
            a //= tmp
            if tmp not in g_tmp:
                g_tmp[tmp] = 1
            else:
                g_tmp[tmp] += 1
        tmp += 1
    if a > 1:
        if a not in g_tmp:
            g_tmp[a] = 1
        else:
            g_tmp[a] += 1

    for j in g_tmp:
        if j not in g:
            g[j] = g_tmp[j]
        else:
            g[j] = max(g[j], g_tmp[j])

l = 1
ans = 0
for i in g:
    l *= pow(i, g[i], mod) % mod
for a in A:
    ans += l * pow(a, mod - 2, mod)
    ans %= mod

print(ans)