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 sys
from fractions import gcd
input=sys.stdin.readline

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
a=lmp()
g=1
for i in range(n):
    g=(g*a[i])//fractions.gcd(g,a[i])
ans=0
for i in range(n):
    ans+=(g//a[i])%(10**9+7)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
#for i in range(N):#最大公倍数
#    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

lcm = reduce(lambda x,y: x//fractions.gcd(x,y)*y, A)
 
#for i in range(N):
#    ans+=lcm//A[i]

ans = sum(lcm//x for x in A)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
#for i in range(N):#最大公倍数
#    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

lcm = reduce(lambda x,y: x//fractions.gcd(x,y)*y, A)
 
for i in range(N):
    ans+=lcm//A[i]


print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
ans=0
min_bai=1
for i in range(N):#最大公倍数
    min_bai=min_bai*A[i]//fractions.gcd(min_bai,A[i])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
input = lambda: sys.stdin.readline().rstrip()

mod = 10**9 + 7


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

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

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

    ans = 0
    for i in range(N):
        ans += B[i]
        ans %= mod

    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    def prime_pair(n):
        pairs = {}
        tmp = n
        for i in range(2, n):
            if i * i > n:
                break
            if tmp % i != 0:
                continue
            ex = 0
            while tmp % i == 0:
                ex += 1
                tmp /= i
            pairs[i] = ex
        if tmp != 1:
            pairs[int(tmp)] = 1
        return pairs

    N = int(input())
    a_list = list(map(int, input().split()))
    a_pp_list = []
    MOD = 10**9 + 7

    a_lcm = {}
    key_set = set()
    for a in a_list:
        a_pp = prime_pair(a)
        a_pp_list.append(a_pp)
        for k in a_pp.keys():
            if k not in key_set:
                key_set.add(k)
                a_lcm[k] = a_pp[k]
            else:
                a_lcm[k] = max(a_lcm[k], a_pp[k])

    a_l = 1
    for k in a_lcm.keys():
        a_l *= k ** a_lcm[k]

    res = 0
    for a in a_list:
        res +=  a_l // a
    print(res%MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def main():

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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a,a_lcm)

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

from fractions import gcd
def main():

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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a_lcm, a)

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    def prime_pair(n):
        pairs = {}
        tmp = n
        for i in range(2, n):
            if i * i > n:
                break
            if tmp % i != 0:
                continue
            ex = 0
            while tmp % i == 0:
                ex += 1
                tmp /= i
            pairs[i] = ex
        if tmp != 1:
            pairs[int(tmp)] = 1
        return pairs

    N = int(input())
    a_list = list(map(int, input().split()))
    a_pp_list = []
    MOD = 10**9 + 7

    a_lcm = {}
    key_set = set()
    for a in a_list:
        a_pp = prime_pair(a)
        a_pp_list.append(a_pp)
        for k in a_pp.keys():
            if k not in key_set:
                key_set.add(k)
                a_lcm[k] = a_pp[k]
            else:
                a_lcm[k] = max(a_lcm[k], a_pp[k])

    a_l = 1
    for k in a_lcm.keys():
        a_l *= k ** a_lcm[k]

    res = 0
    for a in a_list:
        res = (res + a_l // a) % MOD
    print(res)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    def gcd(v1, v2):
        while v2 > 0:
            v1,v2 = v2, v1%v2
        return v1

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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a_lcm, a)

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    def gcd(v1, v2):
        # if v2 == 0:
        #     return v1
        # return gcd(v2, v1%v2)
        
        while v2 > 0:
            tmp = v1
            v1 = v2
            v2 = tmp%v1
        return v1


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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a_lcm, a)

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    def gcd(v1, v2):
        if v2 == 0:
            return v1
        return gcd(v2, v1%v2)

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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a_lcm, a)

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1%v2)

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

MOD = 10**9 + 7

a_lcm = a_list[0]
for a in a_list[1:]:
    a_lcm *= a // gcd(a_lcm, a)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import gcd
from functools import reduce
def input(): return sys.stdin.readline().rstrip()
# ----------------------------------------------------------- #

n = int(input())
A = list(int(x) for x in input().split())
MOD = 10 ** 9 + 7


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


l = reduce(lcm, A)
ans = 0
for a in A:
    ans += l // a
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from fractions import gcd
 
mod = 10**9+7
 
n = int(input())
a = list(map(int,input().split()))
d = 1
for i in range(n):
  d *= a[i] // gcd(a[i],d)
ans = 0
for i in range(n):
  ans += d//a[i]
 
print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

mod = 10**9+7

n = int(input())
a = list(map(int,input().split()))
d = 1
for i in range(n):
  d = d * a[i] // gcd(a[i],d)
ans = 0
for i in range(n):
  ans += d//a[i]
  ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy 
from fractions import gcd

mod = 10**9+7

n = int(input())
a = list(map(int,input().split()))
d = 1
for i in range(n):
  d = d * a[i] // gcd(a[i],d)
ans = 0
for i in range(n):
  ans += d//a[i]
  ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10**18
mod = 10**9+7

dic = {}

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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

n = int(input())
a = list(map(int, input().split()))
j = []
for num in a:
    tmp = factorization(num)
    j.append(tmp)
    for p,x in tmp:
        if p in dic:
            dic[p] = max(dic[p],x)
        else:
            dic[p] = x
pow = {k:[k**i for i in range(v+1)] for k,v in dic.items()}
ans = 0
for i in range(n):
    preans = 1
    dicans = {k:v for k,v in dic.items()}
    for p,x in j[i]:
        dicans[p] -= x
    for k,v in dicans.items():
        preans = preans*pow[k][v]%mod
    ans = (ans+preans)%mod
print(ans)

Submission status: Time Limit Exceeded

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

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

mod = int(1e9+7)

n = int(input())
vs = list(map(int, input().split()))
l = 1
for x in vs:
    l = lcm(l, x)

ans = 0
for x in vs:
    ans = (ans + ((l//x)%mod))%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
from collections import defaultdict,Counter
import copy

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

dic = defaultdict(int)

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

for i in a:
    c = Counter(prime_factorize(i))
    for j,k in c.items():
        if dic[j] < k:
            dic[j] = k

l = 1

for i,j in dic.items():
    for k in range(j):
        l *= i

point = 0

for i in a:
    point += l//i
    point %= mod

print(point)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
from collections import defaultdict,Counter
import copy

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

dic = defaultdict(int)

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

for i in a:
    c = Counter(prime_factorize(i))
    for j,k in c.items():
        if dic[j] < k:
            dic[j] = k

point = 0

for i in a:
    dic2 = copy.deepcopy(dic)
    e = Counter(prime_factorize(i))
    for j,k in e.items():
        dic2[j] -= k
    now = 1
    for j,k in dic2.items():
        for l in range(k):
            now *= j
            now %= mod
    point += now%mod

print(point%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections

MOD = 1000000007  # type: int

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[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if arr==[]:
        arr[n] = 1

    return arr


def solve(N: int, A: "List[int]"):
    LCM = collections.defaultdict(int)

    for a in A:
        primes = factorization(a)
        for k, v in primes.items():
            LCM[k] = max(LCM[k], v)

    result = 0
    LCM_val = 1
    for k, v in LCM.items():
        LCM_val *= pow(k, v)

    for a in A:
        primes = factorization(a)
        result += (LCM_val // a) % MOD
    """
    for a in A:
        primes = factorization(a)
        tmp = 1
        for k, v in LCM.items():
            tmp *= pow(k, v-primes[k] if k in primes else v, MOD)
        result += tmp
    """
    print(result % MOD)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections

MOD = 1000000007  # type: int

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[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if arr==[]:
        arr[n] = 1

    return arr


def solve(N: int, A: "List[int]"):
    LCM = collections.defaultdict(int)

    for a in A:
        primes = factorization(a)
        for k, v in primes.items():
            LCM[k] = max(LCM[k], v)

    result = 0
    for a in A:
        primes = factorization(a)
        tmp = 1
        for k, v in LCM.items():
            tmp *= pow(k, v-primes[k] if k in primes else v, MOD)
        result += tmp
    print(result % MOD)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
MOD = 10 ** 9 + 7
def lcm(x, y):
    return (x * y) // gcd(x, y)
input()
A = list(map(int, input().split()))
l = 1
for a in A:
    l = lcm(l, a)
total = 0
for a in A:
    total += l // a % MOD
print(total % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, Counter, defaultdict

input = sys.stdin.readline
MOD = (10**9+7)

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


def pow_k1(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x


def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = defaultdict(int)
    # lcm_dic = {}
    # al_facs = []
    for a in al:
        fac = factorization(a)
        # a_fac_dic = {}
        for f in fac:
            # lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            # a_fac_dic[f[0]] = f[1]
        # al_facs.append(a_fac_dic)


    lcm = 1
    for prime, cnt in lcm_dic.items():
        lcm *= pow_k1(prime,cnt)

    
    ans = 0
    for a in al:
        ans += (lcm//a)%MOD
        # if ans >= MOD: ans%=MOD
    ans%=MOD


    # ans = 0
    # for al_f in al_facs:
    #     curr_val = 1
    #     for prime, cnt in lcm_dic.items():
    #         if prime in al_f:
    #             curr_val *= pow_k(prime,(cnt-al_f[prime]))
    #             curr_val%=MOD
    #         else:
    #             curr_val *= pow_k(prime,cnt)
    #             curr_val%=MOD
    #     ans += curr_val
    #     ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, Counter, defaultdict

input = sys.stdin.readline
MOD = (10**9+7)

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


def pow_k1(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x


def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = defaultdict(int)
    # lcm_dic = {}
    # al_facs = []
    for a in al:
        fac = factorization(a)
        # a_fac_dic = {}
        for f in fac:
            # lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            # a_fac_dic[f[0]] = f[1]
        # al_facs.append(a_fac_dic)


    lcm = 1
    for prime, cnt in lcm_dic.items():
        lcm *= pow_k1(prime,cnt)

    
    ans = 0
    for a in al:
        ans += lcm//a
        if ans >= MOD: ans%=MOD
    # ans%=MOD


    # ans = 0
    # for al_f in al_facs:
    #     curr_val = 1
    #     for prime, cnt in lcm_dic.items():
    #         if prime in al_f:
    #             curr_val *= pow_k(prime,(cnt-al_f[prime]))
    #             curr_val%=MOD
    #         else:
    #             curr_val *= pow_k(prime,cnt)
    #             curr_val%=MOD
    #     ans += curr_val
    #     ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
class SegmentTree(object):
    def __init__(self, sequence, function, identity):
        N = len(sequence)
        self.length = (1 << (N - 1)).bit_length()
        self.data = [identity] * (self.length << 1)
        self.function = function
        self.identity = identity
        for i in range(N):
            self.data[i + self.length - 1] = sequence[i]
        for i in range(self.length - 2, -1, -1) :
            self.data[i] = self.function(self.data[(i << 1) + 1], self.data[(i << 1) + 2])

    def query(self, p=None, q=None):
        if p == None:
            p = 0
        if q == None:
            q = self.length
        if q <= p:
            return self.identity
        p += self.length - 1
        q += self.length - 2
        res = self.identity
        while q - p > 1:
            if not p & 1:
                res = self.function(res, self.data[p])
            if q & 1:
                res = self.function(res, self.data[q])
                q -= 1
            p >>= 1
            q = (q - 1) >> 1
        return self.function(res, self.data[p]) if p == q else self.function(self.function(res, self.data[p]), self.data[q])

MOD = 10 ** 9 + 7
def lcm(x, y):
    return (x * y) // gcd(x, y)
input()
A = list(map(int, input().split()))
seg_tree = SegmentTree(A, lcm, 1)
l = seg_tree.query()
total = 0
for a in A:
    total = (total + l // a) % MOD
print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, Counter, defaultdict

input = sys.stdin.readline
MOD = (10**9+7)

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


def pow_k1(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x


def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = defaultdict(int)
    # lcm_dic = {}
    # al_facs = []
    for a in al:
        fac = factorization(a)
        # a_fac_dic = {}
        for f in fac:
            # lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            # a_fac_dic[f[0]] = f[1]
        # al_facs.append(a_fac_dic)


    lcm = 1
    for prime, cnt in lcm_dic.items():
        lcm *= pow_k1(prime,cnt)

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


    # ans = 0
    # for al_f in al_facs:
    #     curr_val = 1
    #     for prime, cnt in lcm_dic.items():
    #         if prime in al_f:
    #             curr_val *= pow_k(prime,(cnt-al_f[prime]))
    #             curr_val%=MOD
    #         else:
    #             curr_val *= pow_k(prime,cnt)
    #             curr_val%=MOD
    #     ans += curr_val
    #     ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
MOD = (10**9+7)

def 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


def pow_k1(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x


def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = {}
    # al_facs = []
    for a in al:
        fac = factorization(a)
        # a_fac_dic = {}
        for f in fac:
            lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            # a_fac_dic[f[0]] = f[1]
        # al_facs.append(a_fac_dic)


    lcm = 1
    for prime, cnt in lcm_dic.items():
        lcm *= pow_k1(prime,cnt)

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


    # ans = 0
    # for al_f in al_facs:
    #     curr_val = 1
    #     for prime, cnt in lcm_dic.items():
    #         if prime in al_f:
    #             curr_val *= pow_k(prime,(cnt-al_f[prime]))
    #             curr_val%=MOD
    #         else:
    #             curr_val *= pow_k(prime,cnt)
    #             curr_val%=MOD
    #     ans += curr_val
    #     ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = (10**9+7)
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


def pow_k1(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x


def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = {}
    # al_facs = []
    for a in al:
        fac = factorization(a)
        a_fac_dic = {}
        for f in fac:
            lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            # a_fac_dic[f[0]] = f[1]
        # al_facs.append(a_fac_dic)


    lcm = 1
    for prime, cnt in lcm_dic.items():
        lcm *= pow_k1(prime,cnt)

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


    # ans = 0
    # for al_f in al_facs:
    #     curr_val = 1
    #     for prime, cnt in lcm_dic.items():
    #         if prime in al_f:
    #             curr_val *= pow_k(prime,(cnt-al_f[prime]))
    #             curr_val%=MOD
    #         else:
    #             curr_val *= pow_k(prime,cnt)
    #             curr_val%=MOD
    #     ans += curr_val
    #     ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = (10**9+7)
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


def pow_k1(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x


def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = {}
    al_facs = []
    for a in al:
        fac = factorization(a)
        a_fac_dic = {}
        for f in fac:
            lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            a_fac_dic[f[0]] = f[1]
        al_facs.append(a_fac_dic)


    lcm = 1
    for prime, cnt in lcm_dic.items():
        lcm *= pow_k1(prime,cnt)

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


    # ans = 0
    # for al_f in al_facs:
    #     curr_val = 1
    #     for prime, cnt in lcm_dic.items():
    #         if prime in al_f:
    #             curr_val *= pow_k(prime,(cnt-al_f[prime]))
    #             curr_val%=MOD
    #         else:
    #             curr_val *= pow_k(prime,cnt)
    #             curr_val%=MOD
    #     ans += curr_val
    #     ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()