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 collections import Counter
from fractions import gcd


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

if N >= 10 ** 3:
    lcm = A[0]

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

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

    print(ans)
else:
    def factorization(n):
        arr = Counter()
        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 len(arr.keys()) == 0:
            arr[n] = 1

        return arr

    lcm = factorization(A[0])

    for a in A:
        b = factorization(a)
        lcm = lcm | b

    ans = 0
    L = 1
    for key in list(lcm.keys()):
        L *= key ** lcm[key]

    for a in A:
        ans += L // a
        ans %= MOD

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def factorization(n):
    arr = Counter()
    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 len(arr.keys()) == 0:
        arr[n] = 1

    return arr


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

lcm = factorization(A[0])

for a in A:
    b = factorization(a)
    lcm = lcm | b

ans = 0
L = 1
for key in list(lcm.keys()):
    L *= key ** lcm[key]

for a in A:
    ans += L // a
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [-1] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i] == -1:
            p.append(i)
            t[i] = i
            for j in range(2*i, n, i):
                if t[j] == -1:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == -1:
            p.append(j)
            t[j] = j

    return p, t

P, T = eratosthenes(10**6+1)

class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@lru_cache(maxsize=None)
def factor(a):

    ps = Counter()
    k = set()
    while a != 1:
        f = T[a]
        if a % f == 0:
            k.add(f)
        while a % f == 0:
            ps[f] += 1
            a //= f
    return ps, k

@mt
def slv(N, A):
    lcm = Counter()
    K = set()
    for a in A:
        ps, k = factor(a)
        K |= k
        for k in K:
            lcm[k] = max(lcm[k], ps[k])

    M = Mod(10**9+7)
    l = 1
    for k, v in lcm.items():
        l = M.mul(l, M.pow(k, v))

    ans = 0
    for a in A:
        ans = M.add(ans, M.div(l, a))
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 10000
    # A = [random.randint(1, 10**6) for _ in range(N)]
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
l = [0]*(max(A)+1)
l[1]=1
for a in A:
  if a==1:
    continue
  x=0
  while a%2==0:
    a//=2
    x+=1

  l[2]=max(l[2],x)
  
  f = 3
  while f**2<=a:
    x = 0
    while a%f==0:
      a//=f
      x+=1
    l[f]=max(l[f],x)
    f+=2
    
  if a!=1:
    l[a]=max(l[a],1)
    
b = 1
for i,x in enumerate(l):
  b*=pow(i,x,mod)
  b%=mod
  
ans = 0
for a in A:
  ans+=(b*pow(a,mod-2,mod))%mod
  ans%=mod
  
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p

P = eratosthenes(10**6)

class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@lru_cache(maxsize=None)
def e(a):
    ps = Counter()
    k = set()
    for p in P:
        if a % p == 0:
            k.add(p)
        while a % p == 0:
            ps[p] += 1
            a //= p

        if a == 1:
            break
    return ps, k

@mt
def slv(N, A):
    lcm = Counter()
    K = set()
    for a in A:
        ps, k = e(a)
        K |= k
        for k in K:
            lcm[k] = max(lcm[k], ps[k])

    M = Mod(10**9+7)
    l = 1
    for k, v in lcm.items():
        l = M.mul(l, M.pow(k, v))

    ans = 0
    for a in A:
        ans = M.add(ans, M.div(l, a))
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 10000
    # A = [random.randint(1, 10**6) for _ in range(N)]
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p

P = eratosthenes(10**6)

class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@lru_cache(maxsize=None)
def e(a):
    ps = Counter()
    k = set()
    for p in P:
        if a % p == 0:
            k.add(p)
        while a % p == 0:
            ps[p] += 1
            a //= p

        if a == 1:
            break
    return ps, k

@mt
def slv(N, A):
    lcm = Counter()
    K = set()
    for a in A:
        ps, k = e(a)
        K |= k
        for k in K:
            lcm[k] = max(lcm[k], ps[k])
    M = Mod(10**9+7)
    ans = 0
    for a in A:
        ps, _ = e(a)
        n = 1
        for k in K:
            n = M.mul(n, M.pow(k, lcm[k] - ps[k]))
        ans = M.add(ans, n)
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 10000
    # A = [random.randint(1, 10**6) for _ in range(N)]
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
P=1000000007
def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
N=int(input())
A=list(map(int,input().split()))
l=1
for a in A:
  l=a*l//gcd(a,l)
ans=0
for a in A:
  ans+=l//a
print(ans%P)

Submission status: Time Limit Exceeded

Solution code:
P=1000000007
def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
def lcd(x,y):
  return x*y//gcd(x,y)
N=int(input())
A=list(map(int,input().split()))
l=1
for a in A:
  l=lcd(a,l)
ans=0
for a in A:
  ans+=l//a
print(ans%P)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def eratosthenes(n):
    p = []
    t = [True] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i]:
            p.append(i)
            for j in range(2*i, n, i):
                t[j] = False

    for j in range(i+1, n):
        if t[j]:
            p.append(j)

    return p

P = eratosthenes(10**6)

class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@lru_cache(maxsize=None)
def e(a):
    ps = Counter()
    for p in P:
        while a % p == 0:
            ps[p] += 1
            a //= p
        if a == 1:
            break
    return ps

@mt
def slv(N, A):
    lcm = Counter()
    for a in A:
        ps = e(a)
        for k in set(ps.keys()) | set(lcm.keys()):
            lcm[k] = max(lcm[k], ps[k])
    M = Mod(10**9+7)
    ans = 0
    for a in A:
        ps = e(a)
        n = 1
        for k, v in lcm.items():
            n = M.mul(n, M.pow(k, lcm[k] - ps[k]))
        ans = M.add(ans, n)
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # N = 10000
    # A = [random.randint(1, 10**6) for _ in range(N)]
    # print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import math

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

MOD = 10 ** 9 + 7

primes = defaultdict(int)

for a in A:
    x = a
    p = 2
    for p in range(2, int(math.sqrt(a)) + 1):
        cnt = 0
        while x % p == 0:
            x //= p
            cnt += 1
        primes[p] = max(primes[p], cnt)
    if x > 1:
        primes[x] = max(primes[x], 1)

l = 1
for p in primes:
    l = (l * pow(p, primes[p], MOD)) % MOD

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import math

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

MOD = 10 ** 9 + 7

primes = defaultdict(int)

for a in A:
    x = a
    p = 2
    for p in range(2, int(math.sqrt(a)) + 1):
        cnt = 0
        while x % p == 0:
            x //= p
            cnt += 1
        primes[p] = max(primes[p], cnt)
    if x > 1:
        primes[x] = max(primes[x], 1)

l = 1
for p in primes:
    l = (l * pow(p, primes[p], MOD)) % MOD

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

print(res)

Submission status: Time Limit Exceeded

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

#最小公倍数でよいか？
#全てのjについてAiBiはAjで割り切れる
#計算時間は？
from fractions import gcd
mod =10**9+7
#これが邪魔だったらしい
"""
def lcd(x,y):
    g = gcd(x,y)
    return x*y//g
"""
ag = 1
for i in range(n):
    ag = ag*a[i]//gcd(ag,a[i])

ans = 0

for i in range(n):
    ans += ag//a[i]

ans %=mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

N = int(input())

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

mod = 10**9 + 7

s = [2]
now = 3
dic = {}

while now ** 2 <= 10 ** 6:

    flag = True
    for i in s:
        if now % i == 0:
            flag = False
            break

    if flag:
        s.append(now)
    now += 2

for i in s:
    dic[i] = 0

for i in range(N):
    if i > 0 and A[i] == A[i-1]:
        continue
    a = A[i]

    for j in s:
        cnt = 0
        while a % j == 0:
            cnt += 1
            a //= j

        dic[j] = max(dic[j],cnt)

    if a != 1:
        s.append(a)
        dic[a] = 1

lcm = 1

for i in s:
    for j in range(dic[i]):
        lcm *= i

ans = 0
g = 0
for i in A:
    g += inverse(i,mod)
    g %= mod

ans += lcm * g
ans %= mod
print (ans)

Submission status: Time Limit Exceeded

Solution code:
def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

N = int(input())

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

mod = 10**9 + 7

s = [2]
now = 3
dic = {}

while now ** 2 <= 10 ** 6:

    flag = True
    for i in s:
        if now % i == 0:
            flag = False
            break

    if flag:
        s.append(now)
    now += 2

for i in s:
    dic[i] = 0

for i in range(N):
    if i > 0 and A[i] == A[i-1]:
        continue
    a = A[i]

    for j in s:
        cnt = 0
        while a % j == 0:
            cnt += 1
            a //= j

        dic[j] = max(dic[j],cnt)

    if a != 1:
        s.append(a)
        dic[a] = 1

lcm = 1

for i in s:
    for j in range(dic[i]):
        lcm *= i

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter

def resolve():
    # 方針
    # LCMを求めたい
    #  Aを素因数分解して、素因数ごとに肩のmaxを取りに行く
    #  max同士を掛け合わせる
    # B = X / A : 逆元
    #  B = A^(p-2) , p: 素数 prime

    # たくさんの数の素因数分解
    #     (1こだけの場合。Xに対し、sqrt(X)まで順に見て割り切れなければ素数として判定)
    #  (1) 素数列挙
    #    エラトステネスの篩
    #     素数と決まった数の倍数を消していく(最初は2)
    #     次の数にいく。消されてなければ素数。その数の倍数を消していく。(2乗となる倍数から開始すれば良い)　-> O(NloglogN)
    #     
    #  (2) 素因数分解
    #     上記の操作の時、何で割られたかメモしていく。すでに書かれているものは上書きしない。
    #     例:36. 36 ->2-> 18 ->2-> 9 ->3-> 3(prime) = 2x2x3x3 (sorted)
    #    => 素因数分解の完了
    # 
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split()))

    # 素数列挙 & 割った数の計算
    MX = int(10**6)
    L = np.zeros(MX+1)
    L[0] = -1
    L[1] = -1
    primes = []

    for i in range(2, MX+1):
        if L[i]:
            continue
        primes.append(i)
        L[i] = i
        for j in range(i*i, MX+1, i):
            if L[j] == 0:
                L[j] = i

    def factor(x: int):
        res = []
        while x != 1:
            prime = L[x] if L[x] != 0 else x
            res.append(prime)
            x /= prime
        return res

    max_e = {}
    for a in A:
        a = Counter(factor(a))
        for key, v in a.items():
            if not key in max_e:
                max_e[key] = v
            else:
                if v > max_e[key]:
                    max_e[key] = v
    # print(max_e)

    def modinv(a, mod=10**9+7):
        return pow(a, mod-2, mod)

    lcm = 1
    for key, v in max_e.items():
        lcm *= key ** v

    # print(max_e)
    # print(lcm)
    lcm %= MOD
    # print(lcm)

    ans = 0
    for i in range(N):
        b = lcm * modinv(A[i]) 
        ans += b

    print(int(ans % MOD))


def resolve_ref():
    from fractions import gcd
    
    mod = 10 ** 9 + 7
    
    N = int(input())
    A = list(map(int, input().split()))
    
    L = 1
    for a in A:
        L *= a // gcd(L, a)
    
    print(L)
    L %= mod
    print(L)
    
    print(sum(L * pow(a, mod - 2, mod) for a in A) % mod)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

def lcm(x, y):
    return x // gcd(x, y) * y
n = int(input())
a = list(map(int, input().split(' ')))
l = 1
for ai in a:
    l = lcm(l, ai)
mod = 1000000007
ans = 0
for ai in a:
    ans += l // ai
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter

def resolve():
    # 方針
    # LCMを求めたい
    #  Aを素因数分解して、素因数ごとに肩のmaxを取りに行く
    #  max同士を掛け合わせる
    # B = X / A : 逆元
    #  B = A^(p-2) , p: 素数 prime

    # たくさんの数の素因数分解
    #     (1こだけの場合。Xに対し、sqrt(X)まで順に見て割り切れなければ素数として判定)
    #  (1) 素数列挙
    #    エラトステネスの篩
    #     素数と決まった数の倍数を消していく(最初は2)
    #     次の数にいく。消されてなければ素数。その数の倍数を消していく。(2乗となる倍数から開始すれば良い)　-> O(NloglogN)
    #     
    #  (2) 素因数分解
    #     上記の操作の時、何で割られたかメモしていく。すでに書かれているものは上書きしない。
    #     例:36. 36 ->2-> 18 ->2-> 9 ->3-> 3(prime) = 2x2x3x3 (sorted)
    #    => 素因数分解の完了
    # 
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split()))

    # 素数列挙 & 割った数の計算
    MX = int(10**6 + 5)
    L = np.zeros(MX+1)
    L[0] = -1
    L[1] = -1
    primes = []

    for i in range(2, MX+1):
        if L[i]:
            continue
        primes.append(i)
        for j in range(i+i, MX, i):
            if L[j] == 0:
                L[j] = i

    def factor(x: int):
        res = []
        while x != 1:
            prime = L[x] if L[x] != 0 else x
            res.append(prime)
            x /= prime
        return res

    max_e = {}
    for a in A:
        a = Counter(factor(a))
        for key, v in a.items():
            if not key in max_e:
                max_e[key] = v
            else:
                if v > max_e[key]:
                    max_e[key] = v
    # print(max_e)

    def modinv(a, mod=10**9+7):
        return pow(a, mod-2, mod)

    lcm = 1
    for key, v in max_e.items():
        lcm *= key ** v

    # print(max_e)
    # print(lcm)
    lcm %= MOD
    # print(lcm)

    ans = 0
    for i in range(N):
        b = lcm * modinv(A[i]) 
        ans += b

    print(int(ans % MOD))


def resolve_ref():
    from fractions import gcd
    
    mod = 10 ** 9 + 7
    
    N = int(input())
    A = list(map(int, input().split()))
    
    L = 1
    for a in A:
        L *= a // gcd(L, a)
    
    print(L)
    L %= mod
    print(L)
    
    print(sum(L * pow(a, mod - 2, mod) for a in A) % mod)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(j) for j in input().split()]
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

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

mod=10**9+7
t=a[0]
for i in a:
    t=lcm(t,i)

ans=0
for i in a:
    ans+=t//i
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[int(j) for j in input().split()]
t=1
mod=10**9+7
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
for i in a:
    t*=i//gcd(t,i)
print(sum(t//i for i in a)%mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import heapq

mod = 10**9+7

N = int(input())

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

q = []

for i in A:
    heapq.heappush(q,i)

for i in range(N-1):

    x = heapq.heappop(q)
    y = heapq.heappop(q)

    heapq.heappush(q , x * y // fractions.gcd(x,y))

s = q[0]
ans = 0

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

print (ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
res = 0
for x in a:
  l = x * l // gcd(x, l)
for x in a:
  res += l//x
  res %= mod
print(res)

Submission status: Time Limit Exceeded

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

import sys
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

N = INT()
A = LIST()

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

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

Submission status: Time Limit Exceeded

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

import sys
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

N = INT()
A = LIST()

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

B = [0] * N
for i, a in enumerate(A):
    B[i] = l // a

ans = 0
for b in B:
    ans += b
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

l = a[0]
for k in a:
  l = ( l * k ) // gcd(l, k)

mod = 10 ** 9 + 7
ans = 0
for k in a:
  ans += l // k

print( int(ans) % 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):
  return x if y == 0 else gcd(y, x % y)

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

tmp = A[0]
for i in range(1, N):
  tmp = lcm(A[i], tmp)
#print(tmp)

answer = 0
for a in A:
  answer += tmp // a
print(answer % MOD)

Submission status: Time Limit Exceeded

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

import sys
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

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

N = INT()
A = LIST()

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

B = [0] * N
for i, a in enumerate(A):
    B[i] = l // a

ans = 0
for b in B:
    ans += b
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import fractions

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

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

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

N = int(input().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]

cand = lcm_list(As)

ans = sum([cand // x for x in As]) % int(1e9+7)
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

from functools import reduce
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def lcmm(l):return reduce(lcm,l)

x = lcmm(A)

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

print(ans)

Submission status: Time Limit Exceeded

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

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

A.append(1)
a = A[0]
b = A[1]
lcm = a * b // GCD(a,b)
for i in range(2,N):
  a = lcm
  b = A[i]
  lcm = a * b // GCD(a,b)
ans = 0
for i in range(N):
  ans = (ans + (lcm // A[i]))
print(ans%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):
  return x if y == 0 else gcd(y, x % y)

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

tmp = A[0]
for i in range(1, N):
  tmp = lcm(A[i], tmp)
#print(tmp)

answer = 0
for a in A:
  answer = (answer + tmp // a) % MOD
print(answer)

Submission status: Time Limit Exceeded

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

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


for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for d in lcm.items():
    l*=pow(d[0],d[1])
    

ans=0
mod=10**9+7

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

N,*A = map(int,read().split())

MOD = 10 ** 9 + 7

B = A[:]

while len(A) > 1:
    n = (1+len(A))//2
    A = [y//gcd(x,y)*x for x,y in zip(A[:n], A[-n:])]

lcm = A[0]

answer = sum(lcm//x for x in B)
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def prime_factrize(n):
    b = defaultdict(int)
    while n % 2 == 0:
        b[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            b[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
        b[n] += 1
    return b

def lcm_prime(a, b):
    keys = list(set(list(a.keys()) + list(b.keys())))
    d = defaultdict(int)
    for k in keys:
        d[k] = max(a[k], b[k])
    return d

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
a_prime = []
l_prime = defaultdict(int)

for ai in a:
    a_prime.append(prime_factrize(ai))
    l_prime = lcm_prime(l_prime, a_prime[-1])

ans = 0
for ai in a_prime:
    x = 1
    for p, lp in l_prime.items():
        x *= pow(p, lp - ai[p], MOD)
        x %= MOD
    ans += x
    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()))
m = A[0]
for i in range(1, n):
  m = A[i] // gcd(m, A[i]) * m
ans = 0
for i in A:
  ans += m//i
print(ans%mod)

Submission status: Time Limit Exceeded

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

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


lcm=[0]*(10**6+5)





for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for j in range(2,len(lcm)):
    l*=pow(j,lcm[j])
    

ans=0
mod=10**9+7

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

mod = 10 ** 9 + 7

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

n = int(input())
lis = list(map(int,input().split()))
now = reduce(lcm,lis)

num = list(map(lambda x:now//x,lis))

print(sum(num) % mod)