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 fractions import gcd

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

l = A[0]
for i in range(N-1):
    l = l*A[i+1]//gcd(l,A[i+1])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007        

import fractions

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

n=int(input())

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

max_gcm = 1

for i in t:
    max_gcm = lcm(i,max_gcm)

ans = 0

for i in t:
    ans += max_gcm//i
    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())
a = list(map(int, input().split()))
l = lcm_list(a)
ans = sum([l // x for x in a]) % (10**9+7)
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())
a = list(map(int, input().split()))
l = lcm_list(a)
ans = sum([l // x for x in a]) % int(1e9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))
from collections import *
cmn = defaultdict(int)

def prime_factorization(n):
    d = defaultdict(int)
    k = 2
    def check(k):
        nonlocal d, n
        while n % k == 0:
            d[k] += 1
            n //= k
    check(2)
    k = 3
    while (n != 1):
        check(k)
        k += 2
    return d
P = [prime_factorization(a) for a in A]

for p in P:
    for k in p.keys():
        cmn[k] = max(cmn[k], p[k])

ans = 0

for p in P:
    t = 1
    for k in cmn.keys():
        t *= pow(k, max(cmn[k] - p[k], 0), 10 ** 9 + 7)

    ans += t
    ans %= 10 ** 9 + 7

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

LCM = A[0]
for i in range(0,N-1,1):
    LCM = LCM*A[i+1]//fractions.gcd(A[i+1],LCM)
B = [0 for i in range(0,N,1)]
for i in range(0,N,1):
    B[i]= (LCM%MOD)*pow(A[i],MOD-2,MOD)%MOD

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

MOD = 1000000007
N = int(input())
A = list(map(int,input().split()))
#print(math.gcd(5,4))

LCM = A[0]
for i in range(0,N-1,1):
    LCM = LCM*A[i+1]//fractions.gcd(A[i+1],LCM)
B = [0 for i in range(0,N,1)]
for i in range(0,N,1):
    B[i]= (LCM//A[i])%MOD

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import math
import fractions

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

mod = 10 ** 9 + 7

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

answer = 0
for x in a:
  answer = (answer + lcm // x) % mod
print(answer)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


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


def lcm_list(S):
    return reduce(lcm, S)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    L = lcm_list(A)
    ans = 0
    for a in A:
        ans += L // a
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    def gen_primes2(upper_bound):
        upper_bound += 1
        P = [True] * upper_bound
        P[0] = P[1] = False
        for i in range(4,upper_bound,2):
            P[i] = False
        for i in range(3,int(upper_bound**0.5),2):
            if P[i]:
                for j in range(i**2,upper_bound,i):
                    P[j] = False
        res = []
        for i in range(upper_bound):
            if P[i]:
                res.append(i)
        return res

    N = II()
    A = LMIIS()
    upper_bound = max(A)
    primes = gen_primes2(upper_bound)
    LCMP = [0]*len(primes)
    for i in range(N):
        a = A[i]
        for j in range(len(primes)):
            t = 0
            while a % primes[j] == 0:
                a //= primes[j]
                t += 1
            LCMP[j] = max(t, LCMP[j])
            if a == 1:
                break
    lcm = 1
    for i in range(len(primes)):
        lcm = lcm * pow(primes[i],LCMP[i],MOD) % MOD



    inv = [0, 1]
    for i in range(2, upper_bound+1):
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)

    ans = 0
    for a in A:
        # ans += lcm * pow(a, MOD-2, MOD)
        ans += lcm * inv[a]
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    def gen_primes2(upper_bound):
        upper_bound += 1
        P = [True] * upper_bound
        P[0] = P[1] = False
        for i in range(4,upper_bound,2):
            P[i] = False
        for i in range(3,int(upper_bound**0.5),2):
            if P[i]:
                for j in range(i**2,upper_bound,i):
                    P[j] = False
        res = []
        for i in range(upper_bound):
            if P[i]:
                res.append(i)
        return res

    N = II()
    A = LMIIS()
    primes = gen_primes2(max(A))
    LCMP = [0]*len(primes)
    for i in range(N):
        a = A[i]
        for j in range(len(primes)):
            t = 0
            while a % primes[j] == 0:
                a //= primes[j]
                t += 1
            LCMP[j] = max(t, LCMP[j])
            if a == 1:
                break
    lcm = 1
    for i in range(len(primes)):
        lcm = lcm * pow(primes[i],LCMP[i],MOD) % MOD

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    
    def gen_primes(upper_bound):
        from collections import deque
        if upper_bound <= 1:
            return []
        target = range(3,upper_bound+1,2)
        top = 2
        primes = [2]
        while top <= int(upper_bound**0.5):
            primes.append(top)
            tmp = deque()
            for num in target:
                if num % top != 0:
                    tmp.append(num)
            target = tmp
            top = target[0]
        
        return primes + list(target)


    N = II()
    A = LMIIS()
    a = max(A)
    primes = gen_primes(a)
    LCMP = [0]*len(primes)
    for i in range(N):
        a = A[i]
        for j in range(len(primes)):
            t = 0
            while a % primes[j] == 0:
                a //= primes[j]
                t += 1
            LCMP[j] = max(t, LCMP[j])
            if a == 1:
                break
    lcm = 1
    for i in range(len(primes)):
        lcm = lcm * pow(primes[i],LCMP[i],MOD) % MOD

    # print(lcm)

    # from fractions import gcd
    # lcm = 1
    # for a in A:
    #     g = gcd(lcm,a)
    #     lcm = lcm * a * pow(g, MOD-2, MOD) % MOD
    # print(lcm)



    ans = 0
    # for i in range(N):
    #     t = 1
    #     for j in range(len(primes)):
    #         t = t*pow(primes[j],LCMP[j] - dp[i][j],MOD)%MOD
    #     ans = (ans + t) % MOD
    for a in A:
        ans += lcm * pow(a, MOD-2, MOD)
        ans %= MOD
    print(ans)



    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#from math import gcd
from fractions import gcd
n=int(input())
A=list(map(int,input().split()))
MOD=10**9+7

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

def lcm_mlt(L):
    a=L[0]
    for i in range(len(L)-1):
        a=lcm(a,L[i+1])
    return a

LCM=lcm_mlt(A)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#from math import gcd
from fractions import gcd
n=int(input())
A=list(map(int,input().split()))
MOD=10**9+7

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

def lcm_mlt(L):
    a=L[0]
    for i in range(len(L)-1):
        a=lcm(a,L[i+1])
    return a

LCM=lcm_mlt(A)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import functools

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

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

def multiple(a, b):
    return a*b // euclid(a, b)

def lcm(nums):
        return functools.reduce(multiple, nums)

x=lcm(a)
ans=0

for i in range(n):
    ans+=(x//a[i])%m
    ans%=m

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import functools

n=int(input())
a=list(map(int,input().split()))
m=10**9+7
def euclid(a, b):
    while b:
        a, b = b, a%b
    return a

def multiple(a, b):
    return a*b // euclid(a, b)

def lcm(nums):
        return functools.reduce(multiple, nums)

def main():
  x=lcm(a)
  ans=0

  for i in range(n):
    ans+=(x//a[i])%m
    ans%=m

  print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import functools

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

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

def multiple(a, b):
    return a*b // euclid(a, b)

def lcm(nums):
        return functools.reduce(multiple, nums)

x=lcm(a)
ans=0

for i in range(n):
    ans+=(x//a[i])%m
    ans%=m

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    
    def gen_primes(upper_bound):
        from collections import deque
        target = deque(range(2,upper_bound+1))
        primes = []
        while target[0] <= upper_bound**0.5:
            top = target.popleft()
            primes.append(top)
            tmp = deque()
            for num in target:
                if num % top != 0:
                    tmp.append(num)
            target = tmp
        return primes + list(target)


    N = II()
    A = LMIIS()
    primes = gen_primes(10**6)
    LCMP = [0]*len(primes)
    dp = [[0]*len(primes) for _ in range(N)]
    from math import log
    for i in range(N):
        a = A[i]
        for j in range(len(primes)):
            while a % primes[j] == 0:
                a //= primes[j]
                dp[i][j] += 1
            LCMP[j] = max(dp[i][j],LCMP[j])
            if a == 1:
                break
    lcm = 1
    for i in range(len(primes)):
        lcm = lcm * pow(primes[i],LCMP[i],MOD) % MOD

    # print(lcm)

    # from fractions import gcd
    # lcm = 1
    # for a in A:
    #     g = gcd(lcm,a)
    #     lcm = lcm * a * pow(g, MOD-2, MOD) % MOD
    # print(lcm)



    ans = 0
    # for i in range(N):
    #     t = 1
    #     for j in range(len(primes)):
    #         t = t*pow(primes[j],LCMP[j] - dp[i][j],MOD)%MOD
    #     ans = (ans + t) % MOD
    for a in A:
        ans += lcm * pow(a, MOD-2, MOD)
        ans %= MOD
    print(ans)




    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    
    def gen_primes(upper_bound):
        from collections import deque
        target = deque(range(2,upper_bound+1))
        primes = []
        while target[0] <= upper_bound**0.5:
            top = target.popleft()
            primes.append(top)
            tmp = deque()
            for num in target:
                if num % top != 0:
                    tmp.append(num)
            target = tmp
        return primes + list(target)


    N = II()
    A = LMIIS()
    primes = gen_primes(10**6)
    LCM = [0]*len(primes)
    dp = [[0]*len(primes) for _ in range(N)]
    for i in range(N):
        a = A[i]
        for j in range(len(primes)):
            while a % primes[j] == 0:
                a //= primes[j]
                dp[i][j] += 1
            LCM[j] = max(dp[i][j],LCM[j])
    ans = 0
    for i in range(N):
        t = 1
        for j in range(len(primes)):
            t = t*pow(primes[j],LCM[j] - dp[i][j],MOD)%MOD
        ans = (ans + t) % MOD
    print(ans)




    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import numpy as np

from sys import stdin


def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    sa = set(a)

    lcm = 1

    for ai in sa:
        lcm = (ai * lcm) // fractions.gcd(ai, lcm)

    ans = 0

    ans = np.sum([lcm // ai for ai in a])

    ans %= 10 ** 9 + 7

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import numpy

from sys import stdin


def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    sa = set(a)

    lcm = 1

    for ai in sa:
        lcm = (ai * lcm) // fractions.gcd(ai, lcm)

    ans = 0

    ans = numpy.sum([lcm // ai for ai in a])

    ans %= 10 ** 9 + 7

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

from sys import stdin


def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))
    sa = set(a)

    lcm = 1

    for ai in sa:
        lcm = (ai * lcm) // fractions.gcd(ai, lcm)

    ans = 0

    for ai in a:
        ans += lcm // ai
        ans %= 10 ** 9 + 7

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

from sys import stdin


def main():
    n = int(stdin.readline())
    a = list(map(int, stdin.readline().split()))

    lcm = a[0]

    for i in range(1, n):
        lcm = (a[i] * lcm) // fractions.gcd(a[i], lcm)

    ans = 0

    for ai in a:
        ans += lcm // ai
        ans %= 10 ** 9 + 7

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import gcd
MOD=10**9+7
N,*A=map(int,open(0).read().split())
def lcm(a,b):
  return a*b//gcd(a,b)
s=A[0]
for i in A:
  s=lcm(s,i)
A=np.array(A,dtype=int)
B=s//A
ans=0
for i in B:
  ans=(ans+i)%MOD
print(ans)

Submission status: Time Limit Exceeded

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

def get_prime(n):
    prime = Counter()
    
    while not n % 2:
        prime[2] += 1
        n //= 2
        
    i = 3
    
    while i <= n**0.5:
        while not n % i:
            prime[i] += 1
            n //= i
        i += 2
        
    if n > 1: prime[n] += 1
        
    return prime
    
def main():
    MOD = 10**9+7
        
    N = int(input())
    A = list(map(int, input().split()))
    
    prime = Counter()
    
    for a in A:
        p = get_prime(a)
        for x, n in p.items():
            prime[x] = max(prime[x], n)
            
    X = 1
    for x, n in prime.items():
        X = X * pow(x, n, MOD)
        
    ans = 0
    
    for a in A:
        ans += X // a
        ans %= MOD
        
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def get_prime(n):
    prime = Counter()
    
    while not n % 2:
        prime[2] += 1
        n //= 2
        
    i = 3
    
    while i <= n**0.5:
        while not n % i:
            prime[i] += 1
            n //= i
        i += 2
        
    if n > 1: prime[n] += 1
        
    return prime
    
    
MOD = 10**9+7
    
N = int(input())
A = list(map(int, input().split()))

prime = Counter()

for a in A:
    p = get_prime(a
                  )
    for x, n in p.items():
        prime[x] = max(prime[x], n)
        
X = 1
for x, n in prime.items():
    X = X * pow(x, n, MOD)
    
print(sum([X//a for a in A]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def ti(): return tuple(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

from functools import reduce

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

def gcd_list(numbers):
    return reduce(gcd, numbers)

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

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

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

def main():
    N = ii()
    A = ti()
    inf = 10**9+7
    lcm_a = lcm(A)

    ans = 0
    for num in A:
        ans =  (ans + (lcm_a // num)% inf) % inf
        #ans %= inf
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def ti(): return tuple(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

from functools import reduce

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

def gcd_list(numbers):
    return reduce(gcd, numbers)

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

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

def main():
    N = ii()
    A = ti()
    inf = 10**9+7
    lcm_a = lcm_list(A)

    ans = 0
    for num in A:
        ans =  (ans + lcm_a // num) % inf
        #ans %= inf
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

from functools import reduce

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

def gcd_list(numbers):
    return reduce(gcd, numbers)

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

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

N = ii()
A = li()
inf = 10**9+7
lcm_a = lcm_list(A)

ans = 0
for num in A:
    ans += lcm_a // num
    ans %= inf
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import *
n = int(input())
a = list(map(int, input().split()))

mod = 1000000007

l = 1

for i in range(n):
    l = l * a[i] // gcd(l, a[i])

ans = 0
for i in range(n):
    ans += l // a[i]
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

mod = 1000000007

l = 1

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

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

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

ans = 0
for i in range(n):
    ans += l // a[i]
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce, lru_cache

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

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

B = [1 for i in range(N)]
global_lcm = reduce(lcm, A)
ans = 0
for i in range(N):
    B[i] = int(global_lcm//A[i])
    ans += B[i] % MOD
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

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

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

B = [1 for i in range(N)]
global_lcm = reduce(lcm, A)
ans = 0
for i in range(N):
    B[i] = int(global_lcm//A[i])
    ans += B[i] % MOD
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

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

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

B = [1 for i in range(N)]
global_lcm = reduce(lambda a, b : lcm(a, b), A)
ans = 0
for i in range(N):
    B[i] = int(global_lcm//A[i])
    ans += B[i] % MOD
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

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

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

B = [1 for i in range(N)]
global_lcm = reduce(lambda a, b : lcm(a, b), A)
for i in range(N):
    B[i] = int(global_lcm//A[i])
ans = 0
for i, b in enumerate(B):
    ans += b % MOD
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    mod = 10**9 + 7

    # 素因数分解
    def prime_decomp(n):
        i = 2
        res = []
        while i ** 2 <= n:
            while n % i==0:
                n //= i
                res.append(i)
            i += 1
        if n > 1:
            res.append(n)
        return res
        # 素因数のリストを返す(0, 1は空)

    # aの逆元を求める
    def inv(a, mod=mod):
        return pow(a, mod-2, mod)

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


    lcm = [0]*(max(a)+1)
    for i in a:
        l = prime_decomp(i)
        c = Counter(l)
        for k, v in c.items():
            if lcm[k] < v:
                lcm[k] = v
    
    b = 1
    for i in range(len(lcm)):
        if lcm[i] != 0:
            b *= pow(i, lcm[i], mod)
            b %= mod
    
    if n == 1:
        print(1)
    else:
        res = 0
        for i in a:
            res += inv(i)
        print(res*b%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    mod = 10**9 + 7

    # 素因数分解
    def prime_decomp(n):
        i = 2
        res = []
        while i ** 2 <= n:
            while n % i==0:
                n //= i
                res.append(i)
            i += 1
        if n > 1:
            res.append(n)
        return res
        # 素因数のリストを返す(0, 1は空)

    # aの逆元を求める
    def inv(a, mod=mod):
        return pow(a, mod-2, mod)

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


    lcm = [0]*(max(a)+1)
    for i in a:
        l = prime_decomp(i)
        c = Counter(l)
        for k, v in c.items():
            if lcm[k] < v:
                lcm[k] = v
    
    b = 1
    for i in range(len(lcm)):
        if lcm[i] != 0:
            b *= pow(i, lcm[i], mod)
    
    if n == 1:
        print(1)
    else:
        res = 0
        for i in a:
            res += inv(i)
        print(res*b%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    mod = 10**9 + 7

    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    
    # groupは要素1つでエラー

    n = int(input())
    a = list(map(int, input().split()))
    if n == 1:
        print(1)
    else:
        l = lcm_group(a)
        res = 0
        for i in a:
            res += (l // i) % mod
        print(res%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import gcd

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

p=10**9+7
n = 10 ** 6  # N は必要分だけ用意する
#fact = [1, 1]  # fact[n] = (n! mod p)
#factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用 逆元

for i in range(2, n + 1):
    #fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    #factinv.append((factinv[-1] * inv[-1]) % p)
#a//gcd(a,b)*b

def lcm(a,b):
    g=gcd(a,b)
    #return ((a*b)*pow(g,p-2,p))%p
    return a//gcd(a,b)*b

LCM=1
for x in A:
    LCM=lcm(LCM,x)



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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import gcd

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

p=10**9+7
n = 10 ** 6  # N は必要分だけ用意する
#fact = [1, 1]  # fact[n] = (n! mod p)
#factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用 逆元
 
for i in range(2, n + 1):
    #fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    #factinv.append((factinv[-1] * inv[-1]) % p)
#a//gcd(a,b)*b
def lcm(a,b):
    g=gcd(a,b)
    #return ((a*b)*pow(g,p-2,p))%p
    return a//gcd(a,b)*b

LCM=1
for x in A:
    LCM=lcm(LCM,x)



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