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:
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)
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

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

mod = 10 ** 9 + 7
g = {}
ans = 0

for i in range(N):
    tmp = 1
    a = A[i]
    g_tmp = {}
    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)
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

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

mod = 10 ** 9 + 7
g = [0] * 10 ** 6
ans = 0

for i in range(N):
    tmp = 1
    a = A[i]
    g_tmp = {}
    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:
        g[j] = max(g[j], g_tmp[j])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

N = int(input())
A = [int(i) for i in input().split()]
mod = 10**9+7
ll = A[0]
for i in A:
    ll = lcm(ll, i)
ans = 0
for i in A:
    ans += ll // i
print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import fractions

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


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

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

ll = lcm_list(A)
ans = 0
for i in A:
    ans += ll // i
print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import fractions

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


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

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

ll = lcm_list(A)
ans = 0
for i in A:
    ans += ll // i
print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import fractions

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


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

N = int(input())
A = sorted(list(map(int, input().split())))
B = [0 for _ in range(N)]
mod = 10**9+7

ll = lcm_list(A)
ans = 0
for i in A:
    ans += ll // i
print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:
import fractions


def lcm_list(numbers):
    ans = numbers[0]
    for number in numbers[1:]:
        ans = (((number * ans)) //(fractions.gcd(number, ans)))
    return ans


MOD = 10 ** 9 + 7
N = input()
i = 0
arrs = list(map(int, input().split()))
lcms = lcm_list(arrs)
result = 0
for arr in arrs:
    result = (result + (lcms // arr)) % MOD
print(result)

Submission status: Time Limit Exceeded

Solution code:
import fractions


MOD = 10**9+7
N = input()
i = 0
arrs = list(map(int, input().split()))
result = 0
lcms =1
for number in arrs:
    lcms = (((number * lcms)) / (fractions.gcd(number, lcms)))
for arr in arrs:
    result += (lcms/arr)
result = result%MOD
ans = str(result).replace('.0','')
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

def lcm_list(numbers):
    ans = numbers[0]
    for number in numbers[1:]:
        ans = (((number * ans)) / (fractions.gcd(number, ans)))
    return ans

MOD = 10**9+7
N = input()
i = 0
arrs = list(map(int, input().split()))
lcms = lcm_list(arrs)
result = 0
for arr in arrs:
    result += (lcms/arr)
result = result%MOD
ans = str(result).replace('.0','')
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce


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


def lcm_list(numbers):
    ans = numbers[0]
    for number in numbers[1:]:
        ans = (((number * ans)) / (fractions.gcd(number, ans)))
    return ans

MOD = 10**9+7
N = input()
i = 0
arrs = list(map(int, input().split()))
lcms = lcm_list(arrs)
result = 0
for arr in arrs:
    result = (result+lcms/arr)
result = result%MOD
print(round(result))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import fractions

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

mod = 10 ** 9 + 7
g = 1
ans = 0

for i in range(N):
    d = fractions.gcd(A[i], g % A[i])
    g *= A[i]
    g //= d

for i in range(N):
    ans += (g * pow(A[i], mod - 2, mod)) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import fractions

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

mod = 10 ** 9 + 7
g = 1
ans = 0

for i in range(N):
    d = fractions.gcd(A[i], g)
    g *= A[i]
    g //= d

for i in range(N):
    ans += (g * pow(A[i], mod - 2, mod)) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
lists = list(map(int, input().split()))
g = lists[0]
for i in range(1,N):
    g = g*lists[i] // gcd(g, lists[i])
for i in range(0,N):
    lists[i] = g // lists[i]
ans = sum(lists) % (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
lists = list(map(int, input().split()))
g = lists[0]
for i in range(1,N):
    g = g*lists[i] // gcd(g, lists[i])
def div_g(x, g):
    y = g // x
    return y
glist = [g for i in range(0,N)]
lists = list(map(div_g, lists, glist))
ans = sum(lists) % (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
def lc(a, b):
    return a // gcd(a, b) * b
n = int(input())
a = [int(i) for i in input().split()]
lcm = a[0]
for i in range(1, n):
    lcm = lc(lcm, a[i])
ans = 0
for i in range(n):
    ans += lcm // a[i]
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
import fractions
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
L=ans
M=10**9+7
t=0
for i in range(N):
  t=t+(L//a[i])%M
print(t%M)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
mod=1000000000+7
n=int(input())
a=[int(i) for i in input().split()]
l=reduce(lambda x,y:x//gcd(x,y)*y,a)
ans=sum(map(lambda x:l//x,a))
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    ans%=mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys

if True:
    N, *A = map(int, sys.stdin.read().split())
else:
    N = int(input())
    A = list(map(int, input().split()))

a = 1
for v in A:
    a = a * v // gcd(a, v)

MOD = int(1e9) + 7
sum_ = 0
for v in A:
    sum_ += a // v
    sum_ %= MOD

print(sum_)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

MOD = int(1e9) + 7
sum_ = 0
for v in A:
    sum_ += a // v
    sum_ %= MOD

print(sum_)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
mod = 10**9 + 7
lcm = 1
a_map = list(map(int, input().split()))
for a in a_map:
  p, q = lcm, a
  r = p % q
  while r > 0:
    p, q = q, r
    r = p % q
  lcm = lcm * a // q
b_sum = 0
for a in a_map:
  b_sum += lcm // a
  b_sum %= mod
print(b_sum)

Submission status: Time Limit Exceeded

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

from collections import defaultdict

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

def prime_factors(d,N): #素因数 1を含まないことに注意
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            c = 0
            while tmp%i == 0:
                tmp //= i
                c += 1
            if d[i] < c:
                d[i] = c
    if tmp != 1:
        if d[tmp] == 0:
            d[tmp] = 1

Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    # d = defaultdict( int)
    # for a in A:
    #     prime_factors(d, a)
    s = 1
    for a in A:
        s = s*a//gcd(s,a)
    # for key, value in d.items():
    #     s *= pow( key, value)
    ans = 0
    for a in A:
        ans += s*pow(a,Q-2,Q)
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

from collections import defaultdict

def prime_factors(d,N): #素因数 1を含まないことに注意
    ret = []
    middle = int( N**(1/2))
    tmp = N
    for i in range(2, middle+1):
        if tmp%i == 0:
            c = 0
            while tmp%i == 0:
                tmp //= i
                c += 1
            if d[i] < c:
                d[i] = c
    if tmp != 1:
        if d[tmp] == 0:
            d[tmp] = 1

Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    d = defaultdict( int)
    for a in A:
        prime_factors(d, a)
    s = 1

    for key, value in d.items():
        s *= pow( key, value)
    ans = 0
    for a in A:
        ans += s//a
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    s = 1
    for a in A:
        s = s*a//gcd(a,s)
    ans = 0
    for a in A:
        ans += s//a
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
Q = 10**9+7
def main():
    N = int( input())
    A = list( map( int, input().split()))
    s = 1
    for a in A:
        s = s*a//gcd(a,s)
    ans = 0
    for a in A:
        ans += s//a
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def factorization(n):
    lst, temp = [], n
    for i in range(2, int(n**0.5//1+1)):
        if temp %i ==0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            lst.append([i, cnt])
    if temp != 1:
        lst.append([temp, 1])
    return lst

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

soinsu = {}
factrized_a = []
for i in range(n):
    lst = factorization(a[i])
    factrized_a.append(lst)
    for sosu, josu in lst:
        try:
            before_josu = soinsu[sosu]
        except KeyError:
            before_josu = 0
        soinsu[sosu] = max(before_josu, josu)

ans = 0
for i in range(n):
    lst = factrized_a[i]
    copied_soinsu = soinsu.copy()
    for sosu, josu in lst:
        copied_soinsu[sosu] -= josu
    bi = 1
    for sosu, josu in copied_soinsu.items():
        bi = bi * (sosu**josu) % mod
    ans = (ans + bi) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def factorization(n):
    lst, temp = [], n
    for i in range(2, int(n**0.5//1+1)):
        if temp %i ==0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            lst.append([i, cnt])
    if temp != 1:
        lst.append([temp, 1])
    if lst == []:
        lst.append([n, 1])
    return lst

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

soinsu = {}
factrized_a = []
for i in range(n):
    lst = factorization(a[i])
    factrized_a.append(lst)
    for sosu, josu in lst:
        try:
            before_josu = soinsu[sosu]
        except KeyError:
            before_josu = 0
        soinsu[sosu] = max(before_josu, josu)

ans = 0
for i in range(n):
    lst = factrized_a[i]
    copied_soinsu = soinsu.copy()
    for sosu, josu in lst:
        copied_soinsu[sosu] -= josu
    bi = 1
    for sosu, josu in copied_soinsu.items():
        bi = bi * (sosu**josu) % mod
    ans = (ans + bi) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def PrimeFactorization(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1:
        pf[m] = 1
    return pf


def lcmlist(l):
    from collections import defaultdict
    d = defaultdict(int)
    for i in set(l):
        for k, v in PrimeFactorization(i).items():
            d[k] = max(d[k], v)
    n = 1
    for k, v in d.items():
        n *= k ** v
    return n

n=int(input())
a=list(map(int,input().split()))
x=lcmlist(a)
ans=0
for i in a:
  ans+=x//i
  ans%=1000000007
print(ans)

Submission status: Time Limit Exceeded

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

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

#output
import fractions, functools

mod = 10**9 + 7

def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)

lcm = lcm_list(A)

answer = 0
for i in range(N):
    answer += lcm//A[i]

print(answer % mod)

Submission status: Time Limit Exceeded

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

#output
import fractions, functools

mod = 10**9 + 7

def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)

lcm = lcm_list(A)

#lcm = A[0]
#for i in range(1, N):
#    lcm = lcm * A[i]//fractions.gcd(lcm, A[i])

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

print(answer % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
#input
N = int(input())
A = list(map(int, input().split()))

#output
import fractions, functools
import numpy as np

mod = 10**9 + 7

def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)

lcm = lcm_list(A)

#lcm = A[0]
#for i in range(1, N):
#    lcm = lcm * A[i]//fractions.gcd(lcm, A[i])

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

print(answer % mod)

Submission status: Time Limit Exceeded

Solution code:
# E
from fractions import gcd

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

value = 1
for a in A:
    value = value * a // gcd(value, a)

mod = 10**9+7

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

print(ans)

Submission status: Time Limit Exceeded

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

#output
import fractions
import  functools
import numpy as np

mod = 10**9 + 7

gcd = functools.reduce(fractions.gcd, A)

#def lcm_base(x, y):
#    return (x*y) // fractions.gcd(x, y)
#def lcm_list(numbers):
#    return functools.reduce(lcm_base, numbers, 1)

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

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

print(answer % mod)

Submission status: Time Limit Exceeded

Solution code:
# E
import fractions

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

value = 1
for a in A:
    value = value * a // fractions.gcd(value, a)

mod = 10**9+7

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# E
import fractions
N = int(input()) 
A = list(map(int, input().split()))

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

mod = 10**9+7
ans = 0
for i in A:
    ans += value * pow(i, mod-2,mod)
    ans = ans % mod

print(ans)

Submission status: Time Limit Exceeded

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

#output
import fractions
import  functools
import numpy as np

mod = 10**9 + 7

gcd = functools.reduce(fractions.gcd, A)

def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)

lcm =  lcm_list(A)

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

print(answer % mod)

Submission status: Time Limit Exceeded

Solution code:
# sys.stdin.readline()
import sys
input = sys.stdin.readline

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

#output
import fractions
import  functools
import numpy as np

mod = 10**9 + 7

gcd = functools.reduce(fractions.gcd, A)

def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)

lcm =  lcm_list(A)

answer = 0
for i in range(N):
    answer += lcm//A[i]

print(answer % mod)

Submission status: Time Limit Exceeded

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

#output
import fractions
import  functools
import numpy as np

mod = 10**9 + 7

gcd = functools.reduce(fractions.gcd, A)

def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)

lcm =  lcm_list(A)

answer = 0
for i in range(N):
    answer += lcm//A[i]

print(answer % mod)

Submission status: Time Limit Exceeded

Solution code:
# E
import fractions
N = int(input()) 
A = list(map(int, input().split()))

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

z = 10**9+7
ans = 0
for i in A:
    ans += (value//i) % z

print(ans % z)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
    while b != 0:
        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()))
lcm_a = a[0]

for i in range(1, n):
    lcm_a = lcm(lcm_a, a[i])

ans = 0

for i in a:
    ans += lcm_a // i

print(ans%1000000007)

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)
def lcmlist(l):
  n=l[0]
  for i in l[1:]:
    n=lcm(n,i)
  return n

n=int(input())
a=list(map(int,input().split()))
x=lcmlist(a)
ans=0
for i in a:
  ans+=x//i
  ans%=1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#グローバル変数
pn_list = [2,3]

def next_pn(pn):
    npn = pn + 2
    pn_flg = 0
    while pn_flg == 0:
        for i in pn_list:
            if npn % i == 0:
                break
            if (i ** 2) > npn:
                pn_flg = 1
                break
        if pn_flg == 1:
            break # 素数が見つかったらbreak
        else:
            npn += 2
    pn_list.append(npn)
    return npn

def check_a(n,a):
    res = "ok"
    for i in range(n):
        if a[i] > 1:
            res = "notyet"
    return res

# 整数の入力
n = int(input())
s = input()
a = [int(x) for x in s.split()]
aa = [int(x) for x in s.split()]

#素数作成
sqr_max_a = int((1.0 * 10**6) ** 0.5) + 1
#sqr_max_a = int(1.0 * 10**6)
pn = 3
while pn < sqr_max_a:
    pn = next_pn(pn)

# a を素因数分解する
lcm = int(1)
for i in pn_list:
    wareta = 1
    while wareta == 1:
        wareta = 0
        for j in range(n):
            if a[j] % i == 0:
                a[j] = a[j] // i
                wareta = 1
        if wareta == 1:
            lcm = lcm * i
    if check_a(n,a) == "ok":
        break

pn_lcm = []
for i in a:
    if i > 1:
        if i not in pn_lcm:
            pn_lcm.append(i)
            lcm = lcm * i

min_bsum = int(0)
for i in aa:
    min_bsum = min_bsum + lcm // i

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#グローバル変数
pn_list = [2,3]

def next_pn(pn):
    npn = pn + 2
    pn_flg = 0
    while pn_flg == 0:
        for i in pn_list:
            if npn % i == 0:
                break
            if (i ** 2) > npn:
                pn_flg = 1
                break
        if pn_flg == 1:
            break # 素数が見つかったらbreak
        else:
            npn += 2
    pn_list.append(npn)
    return npn

def check_a(n,a):
    res = "ok"
    for i in range(n):
        if a[i] > 1:
            res = "notyet"
    return res

# 整数の入力
n = int(input())
s = input()
a = [int(x) for x in s.split()]
aa = [int(x) for x in s.split()]

#素数作成
sqr_max_a = int((1.0 * 10**6) ** 0.5) + 1
#sqr_max_a = int(1.0 * 10**6)
pn = 3
while pn < sqr_max_a:
    pn = next_pn(pn)

# a を素因数分解する
lcm = int(1)
for i in pn_list:
    wareta = 1
    while wareta == 1:
        wareta = 0
        for j in range(n):
            if a[j] % i == 0:
                a[j] = a[j] // i
                wareta = 1
        if wareta == 1:
            lcm = lcm * i
    if check_a(n,a) == "ok":
        break

pn_lcm = []
for i in a:
    if i > 1:
        if i not in pn_lcm:
            pn_lcm.append(i)

for j in pn_lcm:
    lcm = lcm * j

min_bsum = int(0)
for i in aa:
    min_bsum = min_bsum + lcm // i

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
#グローバル変数
pn_list = [2,3]

def next_pn(pn):
    npn = pn + 2
    pn_flg = 0
    while pn_flg == 0:
        for i in pn_list:
            if npn % i == 0:
                break
            if (i ** 2) > npn:
                pn_flg = 1
                break
        if pn_flg == 1:
            break # 素数が見つかったらbreak
        else:
            npn += 2
    pn_list.append(npn)
    return npn

def check_a(n,a):
    res = "ok"
    for i in range(n):
        if a[i] > 1:
            res = "notyet"
    return res

# 整数の入力
n = int(input())
s = input()
a = [int(x) for x in s.split()]
aa = [int(x) for x in s.split()]

#素数作成
sqr_max_a = int((1.0 * 10**6) ** 0.5) + 1
#sqr_max_a = int(1.0 * 10**6)
pn = 3
while pn < sqr_max_a:
    pn = next_pn(pn)

# a を素因数分解する
pn_lcm = []
for i in pn_list:
    wareta = 1
    while wareta == 1:
        wareta = 0
        for j in range(n):
            if a[j] % i == 0:
                a[j] = a[j] // i
                wareta = 1
        if wareta == 1:
            pn_lcm.append(i)
    if check_a(n,a) == "ok":
        break

for i in a:
    if i > 1:
        if i not in pn_lcm:
            pn_lcm.append(i)

lcm = int(1)
for j in pn_lcm:
    lcm = lcm * j

min_bsum = int(0)
for i in aa:
    min_bsum = min_bsum + lcm // i

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
 
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
 
    if temp != 1:
        arr.append([temp, 1])
 
    if arr == []:
        arr.append([n, 1])
 
    return arr
 
 
mat = [1]
divs_set = set()
divs_powers = {}
tmp=[0]*len(A)
for j,a in enumerate(A):
    tmp[j] = factorization(a)
    for div in tmp[j]:
        if div[0] not in divs_set:
            divs_set.add(div[0])
            divs_powers[div[0]] = div[1]
        else:
            if divs_powers[div[0]] < div[1]:
                divs_powers[div[0]] = div[1]
 
all_dict = []
all_set = []
for i,t in enumerate(tmp):
    each_dict = {}
    each_set = set()
    for tt in t:
        each_dict[tt[0]] = tt[1]
        each_set.add(tt[0])
    all_dict.append(each_dict)
    all_set.append(each_set)
 
B = [1] * N
for i, a in enumerate(A):
    for k in divs_set:
        if k in all_set[i]:
            B[i] = B[i]*(k**(divs_powers[k]-all_dict[i][k]))
        else:
            B[i] = B[i]*(k**divs_powers[k])
 
print(int(sum(B)) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(i) for i in input().split()]

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


mat = [1]
divs_set = set()
divs_powers = {}
tmp=[0]*len(A)
for j,a in enumerate(A):
    tmp[j] = factorization(a)
    for div in tmp[j]:
        if div[0] not in divs_set:
            divs_set.add(div[0])
            divs_powers[div[0]] = div[1]
        else:
            if divs_powers[div[0]] < div[1]:
                divs_powers[div[0]] = div[1]

all_dict = []
all_set = []
for i,t in enumerate(tmp):
    each_dict = {}
    each_set = set()
    for tt in t:
        each_dict[tt[0]] = tt[1]
        each_set.add(tt[0])
    all_dict.append(each_dict)
    all_set.append(each_set)

B = [1] * N
for i, a in enumerate(A):
    for k in divs_set:
        if k in all_set[i]:
            B[i] = B[i]*(k**(divs_powers[k]-all_dict[i][k]))
        else:
            B[i] = B[i]*(k**divs_powers[k])

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(i) for i in input().split()]

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


mat = [1]
divs_set = set()
divs_powers = {}
tmp=[0]*len(A)
for j,a in enumerate(A):
    tmp[j] = factorization(a)
    for div in tmp[j]:
        if div[0] not in divs_set:
            divs_set.add(div[0])
            divs_powers[div[0]] = div[1]
        else:
            if divs_powers[div[0]] < div[1]:
                divs_powers[div[0]] = div[1]

all_dict = []
all_set = []
for i,t in enumerate(tmp):
    each_dict = {}
    each_set = set()
    for tt in t:
        each_dict[tt[0]] = tt[1]
        each_set.add(tt[0])
    all_dict.append(each_dict)
    all_set.append(each_set)



Z = 1
for n in divs_set:
    Z = Z * (n ** divs_powers[n])

B = [1] * N
for i, a in enumerate(A):
    for k in divs_set:
        if k in all_set[i]:
            B[i] = B[i]*(k**(divs_powers[k]-all_dict[i][k]))
        else:
            B[i] = B[i]*(k**divs_powers[k])

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
n=int(input())
a=[int(x) for x in input().split()]
mod=10**9+7
lcm=1
from fractions import gcd
for ai in a:
    lcm=ai*lcm//gcd(ai,lcm)
ans=0
for ai in a:
    ans+=lcm//ai
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
n=int(input())
a=[int(x) for x in input().split()]
mod=10**9+7
lcm=1
from fractions import gcd
for ai in a:
    lcm=ai*lcm//gcd(ai,lcm)
ans=0
for ai in a:
    ans+=lcm//ai
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

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

def gcd(x, y):
    '''
    最大公約数の計算
    '''
    if y == 0:
        return x
    return gcd(y, x % y)

def lcm(x, y):
    '''
    最小公倍数の計算
    '''
    return (x * y) // fractions.gcd(x, y)

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

ret = 0
for a in A:
    ret += l // a

print(ret%MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
import math
MOD = 1000000007  # type: int


def factorial(n):
    prime_count = Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def solve(N: int, A: "List[int]"):

    C = [factorial(a) for a in A]  # N sqrt(A)

    K = Counter()
    for c in C:                 # 素因数の数*N
        for k in c:
            K[k] = max(K[k], c[k])

    tot = 0
    for i in range(N):          # 素因数の数*N
        a = 1
        for k in K:
            a *= power(k, K[k] - C[i][k])
            a %= MOD
        tot += a
        tot %= MOD
    print(tot)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()