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 copy
n=int(input())
a=list(map(int,input().split()))
b=copy.copy(a)
mod=10**9+7
lcm=[0]*max(a)
for i in range(n):
	for j in range(2,int(a[i]**0.5)+1):
		cnt=0
		while a[i]%j==0:
			a[i]//=j
			cnt+=1
		lcm[j-1]=max(lcm[j-1],cnt)
	if a[i]!=1:
		lcm[a[i]-1]=max(lcm[a[i]-1],1)
an=1
for i in range(len(lcm)):
	an*=pow(i+1,lcm[i],mod)
	an%=mod
ans=0
for i in range(n):
	ans+=an*pow(b[i],mod-2,mod)
	ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

primes = [
  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
 71, 73, 79, 83, 89, 97,101,103,107,109,113,127,131,137,139,149,151,157,163,
167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,
271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,
389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,
503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,
631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,
757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,
883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,
1009
]

def prime_factorize(n):
    res = []
    i = 0
    while primes[i] * primes[i] <= n:
        if n % primes[i] == 0:
            res.append(primes[i])
            n //= primes[i]
        else:
            i += 1
    if n != 1:
        res.append(n)
    return res


lcm_factors = Counter()
for ai in a:
    lcm_factors |= Counter(prime_factorize(ai))

lcm = 1
for k, v in lcm_factors.items():
    lcm *= pow(k, v, MOD)
    lcm %= MOD

ans = 0
for ai in a:
    ans += lcm * pow(ai, MOD - 2, MOD)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

def prime_factorize(n):
    res = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            res.append(i)
            n //= i
        else:
            i += 1 + (i != 2)
    if n != 1:
        res.append(n)
    return res


lcm_factors = Counter()
for ai in a:
    lcm_factors |= Counter(prime_factorize(ai))

lcm = 1
for k, v in lcm_factors.items():
    lcm *= pow(k, v, MOD)
    lcm %= MOD

ans = 0
for ai in a:
    ans += lcm * pow(ai, MOD - 2, MOD)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

from collections import Counter

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

def prime_factorize(n):
    res = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            res.append(i)
            n //= i
        else:
            i += 1 + (i != 2)
    if n != 1:
        res.append(n)
    return res


lcm_factors = Counter()
for ai in a:
    lcm_factors |= Counter(prime_factorize(ai))

lcm = 1
for k, v in lcm_factors.items():
    lcm *= k ** v
    lcm %= MOD

ans = 0
for ai in a:
    ans += lcm * pow(ai, MOD - 2, MOD)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

def prime_factorize(n):
    res = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            res.append(i)
            n //= i
        else:
            i += 1 + (i != 2)
    if n != 1:
        res.append(n)
    return res


lcm_factors = Counter()
for ai in a:
    lcm_factors |= Counter(prime_factorize(ai))

lcm = 1
for k, v in lcm_factors.items():
    lcm *= k ** v
    lcm %= MOD

ans = 0
for ai in a:
    ans += lcm * pow(ai, MOD - 2, MOD)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b): 
    if a == 0: 
        return b 
    return gcd(b % a, a) 
  
def lcm(a,b): 
    return (a*b) // gcd(a,b) 
  
n = int(input())
arr = input()   # takes the whole line of n numbers
a = list(map(int,arr.split(' ')))
l = a[0]
ans = 0
for i in range(n):
    l = lcm(l, a[i])
for i in range(n):
    ans = ans + l//a[i]
print(ans%1000000007)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7

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

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

l = 1
for i in range(len(A)):
    l = lcm(A[i], l)

B = 0
for i in range(len(A)):
    B += l // A[i]

print(B % mod)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7

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

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

B = 0
for i in range(len(A)):
    B += lcm // A[i]

print(B % mod)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b): 
    if a == 0: 
        return b 
    return gcd(b % a, a) 
  
def lcm(a,b): 
    return (a*b) // gcd(a,b) 
  
n = int(input())
arr = input()   # takes the whole line of n numbers
a = list(map(int,arr.split(' ')))
l = a[0]
ans = 0
for i in range(n):
    l = lcm(l, a[i])
for i in range(n):
    ans = ans + l//a[i]
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

v = 1
for x in a:
    v = lcm(v, x)

sum = 0
for x in a:
    sum += v / x

print(int(sum % 1000000007))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

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

def solve(n, a):
    a = sorted(a, reverse=True)
    p = a[0]
    for i in range(1, n):
        p = p * a[i] // gcd(p, a[i])
    q = sum(p // a[i] for i in range(n))
    return q % MOD

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

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

def solve(n, a):
    p = a[0]
    for i in range(1, n):
        p = p * a[i] // gcd(p, a[i])
    q = sum(p // a[i] for i in range(n))
    return q % MOD

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

Submission status: Time Limit Exceeded

Solution code:
# E - Flatten

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

modulus = 10 ** 9 + 7
MAX = 10 ** 6

primefact = [0 for i in range(MAX + 1)]

def sieve():
    # cf. https://www.geeksforgeeks.org/lcm-of-n-numbers-modulo-m/
    for i in range(2, MAX + 1):
        if primefact[i] == 0:
            for j in range(i, MAX + 1, i):
                if primefact[j] == 0:
                    primefact[j] = i

def factorize(x):
    if primefact[2] == 0:
        sieve()

    vec = {}
    while x >= 2:
        d = primefact[x]
        if d not in vec:
            vec[d] = 0
        vec[d] += 1
        x //= d
    return vec

def value_div(x, y):
    p = 1
    for i in x:
        p = (p * (i ** (x[i] - (y[i] if i in y else 0)))) % modulus
    return p

fact = [factorize(x) for x in a]
fset = set()
for f in fact:
    fset.update(f.keys())

l = {}
for k in fset:
    l[k] = max(f[k] if k in f else 0 for f in fact)

s = sum(value_div(l, f) for f in fact) % modulus
print(s)

Submission status: Time Limit Exceeded

Solution code:
# E - Flatten

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

modulus = 10 ** 9 + 7
MAX = 10 ** 6

primefact = [0 for i in range(MAX + 1)]

def sieve():
    # cf. https://www.geeksforgeeks.org/lcm-of-n-numbers-modulo-m/
    for i in range(2, MAX + 1):
        if primefact[i] == 0:
            for j in range(i, MAX + 1, i):
                if primefact[j] == 0:
                    primefact[j] = i

def factorize(x):
    if primefact[2] == 0:
        sieve()

    vec = {}
    while x >= 2:
        d = primefact[x]
        if d not in vec:
            vec[d] = 0
        vec[d] += 1
        x //= d
    return vec

def lcm(x, y):
    vec = {i: x[i] for i in x}
    for i in y:
        vec[i] = max(x[i] if i in x else 0, y[i])
    return vec

def div(x, y):
    vec = {i: x[i] for i in x}
    for i in y:
        vec[i] -= y[i]
    return vec

def value(x):
    p = 1
    for i in x:
        p = (p * (i ** x[i])) % modulus
    return p

fact = [factorize(x) for x in a]

l = {}
for f in fact:
    l = lcm(l, f)

s = sum(value(div(l, f)) for f in fact) % modulus
print(s)

Submission status: Time Limit Exceeded

Solution code:
# E - Flatten

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

modulus = 10 ** 9 + 7
MAX = 10 ** 6

primefact = [0 for i in range(MAX + 1)]

def sieve():
    # cf. https://www.geeksforgeeks.org/lcm-of-n-numbers-modulo-m/
    for i in range(2, MAX + 1):
        if primefact[i] == 0:
            for j in range(i, MAX + 1, i):
                if primefact[j] == 0:
                    primefact[j] = i

def factorize(x):
    if primefact[2] == 0:
        sieve()

    vec = {}
    while x >= 2:
        d = primefact[x]
        if d not in vec:
            vec[d] = 0
        vec[d] += 1
        x //= d
    return vec

def lcm(x, y):
    vec = {i: x[i] for i in x}
    for i in y:
        vec[i] = max(x[i] if i in x else 0, y[i])
    return vec

def div(x, y):
    vec = {i: x[i] for i in x}
    for i in y:
        vec[i] -= y[i]
    return vec

def value(x):
    p = 1
    for i in x:
        p *= (i ** x[i]) % modulus
    return p

fact = [factorize(x) for x in a]

l = {}
for f in fact:
    l = lcm(l, f)

s = sum(value(div(l, f)) for f in fact) % modulus
print(s)

Submission status: Time Limit Exceeded

Solution code:
# E - Flatten

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

modulus = 10 ** 9 + 7

class factorization:
    def __init__(self, x=1):
        self.vec = {}
        d = 2
        while d <= x:
            if x % d == 0:
                if d not in self.vec:
                    self.vec[d] = 0
                self.vec[d] += 1
                x //= d
            else:
                d += 1

    def add(self, x):
        for i in x.vec:
            self.vec[i] = max(self.vec[i] if i in self.vec else 0, x.vec[i])
        return self

    def subtract(self, x):
        for i in x.vec:
            self.vec[i] -= x.vec[i]
        return self

    def clone(self):
        x = factorization()
        for i in self.vec:
            x.vec[i] = self.vec[i]
        return x

    def value(self):
        p = 1
        for i in self.vec:
            p *= (i ** self.vec[i]) % modulus
        return p

fact = [factorization(x) for x in a]

lcm = factorization()
for f in fact:
    lcm.add(f)

difffact = [lcm.clone().subtract(f) for f in fact]

b = [f.value() for f in difffact]
s = sum(x % modulus for x in b) % modulus
print(s)

Submission status: Time Limit Exceeded

Solution code:
# E - Flatten

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

modulus = 10 ** 9 + 7

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

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

l = 1
for x in a:
    l = lcm(l, x)

s = sum((l // x) % modulus for x in a)
print(s % modulus)

Submission status: Time Limit Exceeded

Solution code:
# E - Flatten

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

modulus = 10 ** 9 + 7

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

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

l = 1
for x in a:
    l = lcm(l, x)

s = sum(l // x for x in a)
print(s % modulus)

Submission status: Time Limit Exceeded

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

import fractions


g = a[0]
for i in range(1,N):
    g = g * a[i] // fractions.gcd(g,a[i])

r = 0
for i in range(N):
    r = r + (g//a[i])%(10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce, partial
import sys


def input():
    return sys.stdin.readline()[:-1]

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

def func(a, b, l):
	mod = 10**9 + 7
	return (a +  l*modinv(b, mod)) % mod

def func1(a, b, l):
	mod = 10**9 + 7
	return (a + l//b) % mod

def modinv(a, b):
	return pow(a,b-2,b)

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

	l = reduce(lcm, A) #% mod
	A = (0,) + A
	
	ans = reduce(partial(func1, l=l), A)
	print(ans)
	

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import sys


def input():
    return sys.stdin.readline()[:-1]

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

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

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

	ans = reduce(lcm, A) 
	
	B = (ans//i for i in A)
	print(sum(B) % mod)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
import sys


def input():
    return sys.stdin.readline()[:-1]


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

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

	ans = reduce(lcm, A) 
	
	B = (ans//i for i in A)
	print(sum(B) % mod)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
#from math import gcd
from fractions import gcd
from functools import reduce
import sys
#import time


def input():
    return sys.stdin.readline()[:-1]


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

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

	ans = reduce(lcm, A)
	"""
	a = 1
	for i in A:
		a = lcm(a, i)
	"""
	#print(a, ans)
	B = [ans//i for i in A]
	print(sum(B) % mod)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
#from math import gcd
from fractions import gcd
from functools import reduce
import sys


def input():
    return sys.stdin.readline()[:-1]


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

def main():
	mod = 10**9 + 7
	N = int(input())
	A = [i for i in map(int, input().split())]
	
	ans = reduce(lcm, A)
	"""
	a = 1
	for i in A:
		a = lcm(a, i)
	"""
	#print(a, ans)
	B = [ans//i for i in A]
	print(sum(B) % mod)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
#from math import gcd
from fractions import gcd
from functools import reduce


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

def main():
	mod = 10**9 + 7
	N = int(input())
	A = [i for i in map(int, input().split())]
	
	ans = reduce(lcm, A)
	"""
	a = 1
	for i in A:
		a = lcm(a, i)
	"""
	#print(a, ans)
	B = [ans//i for i in A]
	print(sum(B) % mod)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
#from math import gcd
from fractions import gcd
#from functools import reduce


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

def main():
	mod = 10**9 + 7
	N = int(input())
	A = [i for i in map(int, input().split())]
	
	#ans = reduce(lcm, A)
	
	a = 1
	for i in A:
		a = lcm(a, i)

	#print(a, ans)
	B = [a//i for i in A]
	print(sum(B) % mod)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
#from math import gcd
from fractions import gcd
from functools import reduce


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

def main():
	mod = 10**9 + 7
	N = int(input())
	A = [i for i in map(int, input().split())]
	
	ans = reduce(lcm, A)
	
	a = 1
	for i in A:
		a = lcm(a, i)

	#print(a, ans)
	B = [a//i for i in A]
	print(sum(B) % mod)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
#from math import gcd
from fractions import gcd
#from functools import reduce

mod = 10**9 + 7

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


N = int(input())
A = [i for i in map(int, input().split())]

#ans = reduce(lcm, A)

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

#print(a, ans)
B = [a//i for i in A]

print(sum(B) % mod)

Submission status: Time Limit Exceeded

Solution code:
#from math import gcd
from fractions import gcd
from functools import reduce

mod = 10**9 + 7

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


N = int(input())
A = [i for i in map(int, input().split())]

ans = reduce(lcm, A)

#print(ans)
B = [ans//i for i in A]

print(sum(B) % mod)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
from sys import stdin
from copy import deepcopy
from functools import reduce
from fractions import gcd
import math
import itertools
from collections import Counter
from itertools import chain  ##list(chain.from_iterable(l)) ##flatten
from heapq import heappush, heappop
import bisect

"""
N = int(input())
A, B = map(int,input().split())
A = list(map(int,input().split())) ## 横一列
A = [int(input()) for _ in range(N)] ## 縦一列
lst = [list(map(int,input().split())) for i in range(M)] ## 二次元
"""

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
N = int(input())
A = list(map(int,input().split()))

mod = int(1e9) + 7
lcm = lcm_list(A)

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

Submission status: Time Limit Exceeded

Solution code:

MOD = 1000000007
def mod_multiple(a, b):
    return ( (a % MOD) * (b % MOD) ) % MOD

def mod_add(a, b):
    return ( (a % MOD) + (b % MOD) ) % MOD

def common_multiple(a,b):
    residual = [a, b]
    common_factor = []
    i = 2
    while min(residual) >= i:
        if (residual[0] % i == 0) and (residual[1] % i == 0):
            common_factor += [i]
            residual[0] //= i
            residual[1] //= i
        else:
            i += 1
    return residual
    
N = int(input())
A = list(map(int, input().split()))

B_sum = 1
B_prod = A[0]
for i in range(1, N):
    a, b = common_multiple(B_prod, A[i])
#    B_sum = B_sum * b + a
    B_sum = mod_add(mod_multiple(B_sum, b), a)
    B_prod = B_prod * b 
    
print(B_sum)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

mod = 10 ** 9 + 7

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

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

# ans = lcm * sum([pow(s, mod - 2, mod) for s in A]) % mod
ans = sum([lcm//s % mod for s in A]) % mod

print(int(ans % mod))

Submission status: Time Limit Exceeded

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

from fractions import gcd


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


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

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

l %= MOD

ans = 0
for a in A:
    ans += l * pow(a, MOD-2, MOD) % MOD
    ans %= MOD

print(int(ans))

Submission status: Time Limit Exceeded

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


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


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

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

l %= MOD

ans = 0
for a in A:
    ans += l * pow(a, MOD-2, MOD)
    ans %= MOD

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


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


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

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

l %= MOD

ans = 0
for a in A:
    ans += l * pow(a, MOD-2, MOD)
    ans %= MOD

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def mod_inv(a, m):
    return pow(a, m-2, m)


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


P = defaultdict(int)

for a in set(A):
    e = defaultdict(int)
    rest = a
    for i in range(2, a + 1):
        while rest % i == 0:
            e[i] += 1
            rest //= i
    for k, v in e.items():
        P[k] = max(P[k], v)

lcm = 1
for k, v in P.items():
    lcm *= k ** v
    lcm %= MOD

ans = 0
for a in A:
    ans += lcm * mod_inv(a, MOD)
    ans %= MOD

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


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


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

B = sorted(set(A))

l = 1
for b in B:
    if l % b == 0:
        continue
    l = lcm(l, b)

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

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


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


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

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

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

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


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


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

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

B = [l // a for a in A]

print(int(sum(B)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#from fractions import gcd
#from math import gcd
import numpy as np
#import sys
#input = sys.stdin.readline
mod = 10**9+7

def obtain_ps(n):
    ps={}
    while(n>1):
        if int(n**0.5)+1<=2:
            ps[n]=1
            n=1
        for i in range(2, int(n**0.5)+1):
            if not n%i==0:
                continue
            i_primary=True
            for j in range(2, int(i**0.5)+1):
                if j %i:
                    i_primary=False
                    break
            if not i_primary:
                continue
            count=1
            r=i
            while(not n%r):
                count +=1
                r*=i
                if count > 10:
                    return -1
            count-=1
            ps[i]=count
            n=n/(i**count)

    return ps

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

ps={}
ps_s=[]
for s in A:
    ps_tmp=obtain_ps(s)
    ps_s.append(ps_tmp)
    for k,v in ps_tmp.items():
        if k in ps.keys():
            ps[k]=max(v, ps_tmp[k])
        else:
            ps[k]=v

ans=0
for ps_tmp in ps_s:
    plus=1
    for k,v in ps.items():
        if k in ps_tmp.keys():
            plus*=k**(v-ps_tmp[k])
        else:
            plus*=k**v

    ans+=plus%mod
#lcm=np.product([k**v for k,v in ps.items()])

#ans = np.sum([lcm // s %mod for s in A]) % mod

print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:
#from fractions import gcd
#from math import gcd
import numpy as np
#import sys
#input = sys.stdin.readline
mod = 10**9+7

def obtain_ps(n):
    ps={}
    while(n>1):
        for i in range(2, int(n**0.5)+1):
            if not n%i==0:
                continue
            i_primary=True
            for j in range(2, int(i**0.5)+1):
                if j %i:
                    i_primary=False
                    break
            if not i_primary:
                continue
            count=1
            r=i
            while(not n%r):
                count +=1
                r*=i
                if count > 10:
                    return -1
            count-=1
            ps[i]=count
            n=n/(i**count)
        if int(n**0.5)+1<=2:
            ps[n]=1
            n=1
    return ps

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

ps={}
for s in A:
    ps_tmp=obtain_ps(s)
    for k,v in ps_tmp.items():
        if k in ps.keys():
            ps[k]=max(v, ps[k])
        else:
            ps[k]=v

lcm=np.product([k**v for k,v in ps.items()])

ans = np.sum([lcm // s %mod for s in A]) % mod

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
#from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

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

lcm=1
for s in A:
    lcm=s*lcm//my_gcd(lcm, s)

ans = np.sum([lcm // s %mod for s in A]) % mod

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

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

ans = np.sum([lcm // s % mod for s in A]) % mod

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

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

ans = np.sum([lcm*pow(s, mod-2, mod) % mod for s in A]) % mod

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

lcms = [A[0]]
[lcms.append(s*lcms[-1]//gcd(lcms[-1], s)) for s in A]
lcm = lcms[-1]

ans = np.sum([lcm*pow(s, mod-2, mod) % mod for s in A]) % mod

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
#from math import gcd
#import numpy as np
import sys
input = sys.stdin.readline
mod=10**9+7

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

lcms=[A[0]]
[lcms.append(s*lcms[-1]//gcd(lcms[-1], s)) for s in A]
lcm=lcms[-1]
sums=[0]
[sums.append( (sums[-1]+lcm*pow(s, mod-2, mod)) %mod )  for s in A]

print(int(sums[-1]))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
#from math import gcd
#import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

lcms=[A[0]]
[lcms.append(s*lcms[-1]//gcd(lcms[-1], s)) for s in A]
lcm=lcms[-1]
sums=[0]
[sums.append( (sums[-1]+lcm//s) %(10**9+7) )  for s in A]

print(int(sums[-1]))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
#from math import gcd
#import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

lcms=[A[0]]
[lcms.append(s*lcms[-1]//gcd(lcms[-1], s)) for s in A]

sums=[0]
[sums.append( (sums[-1]+lcms[-1]//s) %(10**9+7) )  for s in A]

print(int(sums[-1]))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
#from math import gcd
#import numpy as np

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

lcms=[A[0]]
[lcms.append(s*lcms[-1]//gcd(lcms[-1], s)) for s in A]

sums=[0]
[sums.append( (sums[-1]+lcms[-1]//s) %(10**9+7) )  for s in A]

print(int(sums[-1]))

Submission status: Time Limit Exceeded

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

n,*a=map(int,open(0).read().split())
mod=10**9+7
lcm=1
for x in a:
    lcm=lcm*x//gcd(lcm,x)
ans=0
for x in a:
    ans+=(lcm//x)%mod
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys

input = sys.stdin.readline

mp = 1000000###max prime
mod = 10 ** 9 + 7
def prime_factorize(n):
    a = [0] * mp
    while n % 2 == 0:
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] += 1
    return a

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

def fact_mul(x,y):
    ret = [0] * mp
    for i in range(mp):
        ret[i] = x[i] + y[i]
    return ret

def fact_div(x,y):
    ret = [0] * mp
    for i in range(mp):
        ret[i] = x[i] - y[i]
    return ret

def cal_mod(x):
    ret = 1
    for i in range(mp):
        ret *= (i**x[i]) % mod
        ret %= mod
    return ret


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

A_fact = [0] * N###Aの各要素の素因数分解
for i in range(N):
    A_fact[i] = prime_factorize(A[i])
#print(A_fact[0][0:12])

l_fact = A_fact[0][:]

for i in range(1,N):
    for j in range(1,mp):
        l_fact[j] = max(A_fact[i][j],l_fact[j])

B0_fact = [0] * mp


for i in range(mp):
    B0_fact[i] = max(0,l_fact[i]-A_fact[0][i])

ans = cal_mod(B0_fact)
#print(A_fact[0][0:12])
#print(B0_fact[0:12])
#print(cal_mod(l_fact))
#print(ans)
#print(A_fact)
#print(B0_fact)
for i in range(1,N):
    Bi = fact_div(fact_mul(A_fact[0],B0_fact),A_fact[i])
    ans += cal_mod(Bi)
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def sieve_advance(n):  #n未満の整数iについてi以下でiを割り切る最小の素数を求める。
    minfactor=[-1]*n
    minfactor[0],minfactor[1]=0,1
    isprime=[True]*n
    isprime[0],isprime[1]=False,False
    limit=int((math.sqrt(n)+2)//1)
    
    for i in range(2,limit):
        if isprime[i]:
            minfactor[i]=i
            for j in range(i**2,n,i):
                isprime[j]=False
                if minfactor[j]==-1:
                    minfactor[j]=i
    
    return minfactor

minfactor=sieve_advance(10**6+1)
def prime_factor(n): #nをminfactorを利用して素因数分解する
    res={}
    while n!=1:
        prime=minfactor[n]
        exp=0
        while minfactor[n]==prime:
            exp+=1
            n//=prime
        res[prime]=exp

    return res

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

factor=[[] for _ in range(n)]
lcm={}
for i in range(n):
  num=nums[i]
  factor[i]=prime_factor(num)
  for p in factor[i].keys():
    e=factor[i][p]
    if p in lcm:
      lcm[p]=max(lcm[p],e)
    else:
      lcm[p]=e
#print(lcm)

b=[1]*n
for p in lcm.keys():
  e_lcm=lcm[p]
  for i in range(n):
    if p in factor[i]:
      e_a=factor[i][p]
    else:
      e_a=0
    b[i]*=p**(e_lcm-e_a) 
    b[i]%=mod
    
#print(b)
print(sum(b)%mod)