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()))
def primelist(N):
    prime = [2]
    for i in range(3, N+1):
        flag = 1
        for j in prime:
            if i % j == 0:
                flag = 0
                break
        if flag == 1:
            prime.append(i)
    return prime
prime = primelist(1001)

def factorization(n):
    arr = []
    temp = n
    for i in prime:
        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


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

fact = [0] * (1000001)
pri = []
for i in range(n):
    f = factorization(a[i])
    for fac, c in f:
        fact[fac] = max(fact[fac], c)

fact_list = []
for i in range(1000001):
    if fact[i] > 0:
        fact_list.append((i, fact[i]))

def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res


ans = 0
for i in range(n):
    m = modinv(a[i])
    for fac, c in fact_list:
        m *= power_func(fac, c, mod)
        m %= mod

    ans += m
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd #直して
n = int(input())
a = list(map(int, input().split()))
def primelist(N):
    prime = [2]
    for i in range(3, N+1):
        flag = 1
        for j in prime:
            if i % j == 0:
                flag = 0
                break
        if flag == 1:
            prime.append(i)
    return prime
prime = primelist(1001)

def factorization(n):
    arr = []
    temp = n
    for i in prime:
        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


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

fact = [0] * (1000001)
pri = []
for i in range(n):
    f = factorization(a[i])
    for fac, c in f:
        fact[fac] = max(fact[fac], c)

fact_list = []
for i in range(1000001):
    if fact[i] > 0:
        fact_list.append((i, fact[i]))




ans = 0
for i in range(n):
    m = modinv(a[i])
    for fac, c in fact_list:
        m *= pow(fac, c, mod)
        m %= mod

    ans += m
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 最小公倍数を目指す？
n = int(input())
arr = list(map(int, input().split()))


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


def lcm(a, b):
    ret = (a * b) // gcd(a, b)
    # ret = ret % (10 ** 9 + 7)  # これがめっちゃ怖い TLEなりそう.. でもどうすんだ...
    return ret


a = arr[0]
for i in range(1, n):
    a = lcm(a, arr[i])
ans = 0
for av in arr:
    z = a // av  # % (10 ** 9 + 7)
    ans += z
    # ans %= 10 ** 9 + 7
print(ans % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def solve():
    n = int(input())
    a = list(map(int,input().split()))
    x = 1
    for ai in a:
        x = (x * ai) // gcd(x, ai)
    ans = sum([x // ai for ai in a])
    print(ans % 1000000007)

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
LCM = 1
for i in A:
    GCD = gcd(LCM,i)
    LCM = LCM*i//GCD
ans = 0
for i in A:
    ans = (ans+LCM//i)%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
LCM = 1
for i in A:
    GCD = gcd(LCM,i)
    LCM = LCM*i//GCD
ans = 0
for i in A:
    ans += LCM//i
print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


def solve():
    N, *A = map(int, open(0).read().split())
    MOD = 10 ** 9 + 7

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

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


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


def solve():
    N, *A = map(int, open(0).read().split())
    MOD = 10 ** 9 + 7

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

    ans = [lcm // a for a in A]
    print(sum(ans) % MOD)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10 ** 9 + 7

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

C = Counter()
for a in A:
    if a in C:
        continue

    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
    L %= mod

print(sum(L * pow(a, mod - 2, mod) for a in A) % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10 ** 9 + 7

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

C = Counter()
for a in A:
    if a in C:
        continue

    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
L %= mod

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

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

if n == 1:
    print(1)
    exit()

MOD = 10 ** 9 + 7

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

c = p[0]
for x in p[1:]:
    c = c * x // gcd(c, x)

ans = 0
for x in p:
    ans = (ans + c // x) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

from fractions import gcd

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

if n == 1:
    print(1)
    exit()

MOD = 10 ** 9 + 7

c = p[0]
for x in p[1:]:
    c = c * x // gcd(c, x)

ans = 0
for x in p:
    ans = (ans + c // x) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10 ** 9 + 7

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

C = Counter()
for a in A:
    if a in C:
        continue

    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
L %= mod

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
from fractions import gcd
import fractions
import statistics
import collections
from functools import reduce
import itertools
from collections import defaultdict
import bisect
from fractions import Fraction
 
 
N = int(input())
A=list(map(int, input().split()))
 
num = A[0]
for i in range(1, N):
    num = num * A[i] // fractions.gcd(num, A[i])
 
ans = 0
 
for i in range(N):
    ans += (num // A[i])
 
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

from fractions import gcd

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

if n == 1:
    print(1)
    exit()

MOD = 10 ** 9 + 7

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

c = p[0]
for x in p[1:]:
    c = lcm(c, x)

ans = 0
for x in p:
    ans = (ans + c // x) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10 ** 9 + 7

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

C = Counter()
for a in A:
    if a in C:
        continue
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
    L %= mod

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions as math
from functools import reduce
 
 
N = int(input())
A=list(map(int, input().split()))
 
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
num = lcm_list(A)
 
ans = 0
 
for i in range(N):
    ans += (num // A[i])
    ans %= 10**9+7
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

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

if n == 1:
    print(1)
    exit()

MOD = 10 ** 9 + 7

MAX = max(p) + 1

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

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

c = p[0]
for x in p[1:]:
    c = lcm(c, x)

ans = 0
for x in p:
    ans = (ans + c // x) % MOD

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
from fractions import gcd
import fractions as math
import statistics
import collections
from functools import reduce
import itertools
from collections import defaultdict
import bisect
from fractions import Fraction
 
 
N = int(input())
A=list(map(int, input().split()))
 
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
num = lcm_list(A)
 
ans = 0
 
for i in range(N):
    ans += (num // A[i])
    ans %= 10**9+7

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10 ** 9 + 7

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

C = Counter()
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            if C[i] < cnt:
                C[i] = cnt
        i += 1
    if a > 1:
        if C[a] < 1:
            C[a] = 1

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
    L %= mod

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10 ** 9 + 7

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

C = Counter()
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
    L %= mod

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10 ** 9 + 7

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

C = Counter()
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
    L %= mod

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

print(L * ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10 ** 9 + 7

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

C = Counter()
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    if c == 0:
        continue
    L *= pow(i, c, mod)
    L %= mod

print(L * sum(pow(a, mod - 2, mod) for a in A) % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

mod = 10 ** 9 + 7

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

C = Counter()
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in C.items():
    L *= pow(i, c, mod)
    L %= mod

print(L * sum(pow(a, mod - 2, mod) for a in A) % 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):
  while y: x, y = y, x % y
  return x

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

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

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

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

C = [0] * (max(A) + 1)
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in enumerate(C):
    L *= pow(i, c, mod)
    L %= mod

print(L * sum(pow(a, mod - 2, mod) for a in A) % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

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

C = [0] * (max(A) + 1)
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in enumerate(C):
    L *= pow(i, c, mod)
L %= mod

print(L * sum(pow(a, mod - 2, mod) for a in A) % mod)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
 
def gcd(n, m):
    if(m): return gcd(m, n%m)
    else: return n
 
def lcm(n, m):
    return n // gcd(n, m) * m
 
LCM = a[0]
for i in range(1, n):
    LCM = lcm(a[i], LCM)
 
res = 0
MOD = 1000000007
for i in range(n):
    res += LCM//a[i]
    
print(res % MOD)

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

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

C = [0] * (max(A) + 1)
for a in A:
    i = 2
    while i * i <= a:
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                a //= i
                cnt += 1
            C[i] = max(C[i], cnt)
        i += 1
    if a > 1:
        C[a] = max(C[a], 1)

L = 1
for i, c in enumerate(C):
    L *= pow(i, c)
    L %= mod

print(L * sum(pow(a, mod - 2, mod) for a in A) % mod)

Submission status: Time Limit Exceeded

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

def lcm(n, m):
    return n // fractions.gcd(n, m) * m

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

res = 0
MOD = 1000000007
for i in range(n):
    res = (res + LCM//a[i]) % MOD
print(res)

Submission status: Time Limit Exceeded

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

def gcd(n, m):
    if(m): return gcd(m, n%m)
    else: return n

def lcm(n, m):
    return n // gcd(n, m) * m

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

res = 0
MOD = 1000000007
for i in range(n):
    res = (res + LCM//a[i]) % MOD
print(res)

Submission status: Time Limit Exceeded

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

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

x = lcm_list(l)
ans = 0
for i in range(n):
  ans += x//l[i]
  ans %= 10**9+7
  
print(ans)

Submission status: Time Limit Exceeded

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

def fctr1(n): 
    f=[]
    c=0
    r=int(n**0.5)
    for i in range(2,r+2):
        while n%i==0:
            c+=1
            n=n//i
        if c!=0:
            f.append([i,c])
            c=0
    if n!=1:
        f.append([n,1])
    return f


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    C = defaultdict(int)
    for a in A:
        tmp = fctr1(a)
        for i, j in tmp:
            C[i] = max(C[i],j)

    D = 1
    for i, j in C.items():
        D *= i ** j

    ans = 0
    for a in A:
        ans += D // a
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

MOD = 10 ** 9 + 7

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

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

def lcmArr(a):
    return reduce(getLcm, a)

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

lcm = lcmArr(a)
ret = 0
for val in a:
    ret += lcm // val
    ret %= MOD
print(ret)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N=int(input())
a = list(map(int, input().split()))
lcm = 1
for i in range(N):
    lcm = lcm * a[i] // gcd(lcm, a[i])
import numpy as np
aa = np.array(a)
print(sum(lcm//aa)%(10**9+7))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a = list(map(int, input().split()))
import fractions
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
import numpy as np
aa = np.array(a)
print(sum(ans//aa)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import math
sieve=[1]*10001
i=2
while i*i<=10001:
    if sieve[i]:
        for j in range(i+i,10001,i):
            sieve[j]=0
        
    i+=1    
lol=[]
for i in range(2,10001):
    if sieve[i]:
        lol.append(i)
mod=10**9+7
def gcd(x,y):
    if x==0:
        return y
    return gcd(y%x,x)    
x=int(input())
a=list(map(int,input().split()))
d=defaultdict(int)
for i in a:
    k=0

    while lol[k]*lol[k]<=i:
        c=0
        #print("AScasc",i)
        j=lol[k]
        if i%j==0:    
            while i%j==0:
                i//=j
                c+=1
            d[j]=max(c,d[j])    
        k+=1    
    if i>=2:
        c=1
        d[i]=max(c,d[i])
        
y=0
s=d.keys()
#print(s,d)
for i in a:
    d0=d.copy()
    k=0
    while lol[k]*lol[k]<=i:
        j=lol[k]
        if i%j==0:    
            while i%j==0:
                i//=j
                d0[j]-=1
        k+=1
    if i>=2:
        d0[i]-=1
    z=1
    for j in d0.keys():
        z*=pow(j,d0[j],mod)
    y+=z%mod    
print(y%mod)

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)
 
n = int(input())
av = list(map(int, input().split(' ')))
alcm = 1
for i in av:
  alcm = lcm(alcm, i)
 
tot = 0
for i in range(n):
  tot += alcm // av[i]
 
print(tot % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


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


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

# print(lcm(12, 8))
# print(lcm(20, 6))
# print(lcm(2, 2))
# print(lcm(100, 200))
# print(lcm(100, 240))


def main():
    n = int(sys.stdin.readline().strip())
    a = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    cur = 1
    for ai in a:
        cur = lcm(cur, ai)

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

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


def main():
    n = int(sys.stdin.readline().strip())
    a = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    def do_it(num):
        if num == 1:
            return {}
        cur = num
        dic = defaultdict(int)

        while cur % 2 == 0:
            cur //= 2
            dic[2] += 1

        i = 3
        while i * i <= num:
            while cur % i == 0:
                dic[i] += 1
                cur //= i
            i += 1
        if cur != 1:
            dic[cur] += 1
        return dic

    d = defaultdict(int)
    d_list = []
    for ai in a:
        di = do_it(ai)
        d_list.append(di)
        keys = di.keys()
        for key in keys:
            d[key] = max(d[key], di[key])

    ans = 0
    for i in range(n):
        cur = 1
        keys = d.keys()
        d_i = d_list[i]
        for key in keys:
            diff = d[key] - d_i[key]
            for j in range(diff):
                cur *= key
                cur %= 10 ** 9 + 7
        ans += cur
        ans %= 10 ** 9 + 7
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N=int(input())
a = list(map(int, input().split()))
import fractions
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
import numpy as np
aa = np.array(a)
print(sum(ans//aa)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict


def main():
    n = int(sys.stdin.readline().strip())
    a = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    def do_it(num):
        if num == 1:
            return {}
        cur = num
        dic = defaultdict(int)
        for i in range(2, num+1):
            if cur == 1:
                break
            while cur % i == 0:
                dic[i] += 1
                cur //= i
        return dic

    d = defaultdict(int)
    d_list = []
    for ai in a:
        di = do_it(ai)
        d_list.append(di)
        keys = di.keys()
        for key in keys:
            d[key] = max(d[key], di[key])

    ans = 0
    for i in range(n):
        cur = 1
        keys = d.keys()
        d_i = d_list[i]
        for key in keys:
            diff = d[key] - d_i[key]
            for j in range(diff):
                cur *= key
                cur %= 10 ** 9 + 7
        ans += cur
        ans %= 10 ** 9 + 7
    print(ans)


main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 

def NWD(A, B):
    if A < B:
        A, B = B, A 
    if B == 0: 
        return A
    return NWD(A%B, B)

    
def NWW(A,B):
    return A*B//NWD(A,B)
    
def flatten():
    N = wczytaj_liste()[0]
    A = wczytaj_liste()
    B = []
    najwieksza_wielokrotnosc = A[0]
    for i in range(N): 
        najwieksza_wielokrotnosc = NWW(najwieksza_wielokrotnosc, A[i])
    for i in range(N):
        B.append(najwieksza_wielokrotnosc//A[i])
    print(sum(B)%(10**9+7))

flatten()

Submission status: Time Limit Exceeded

Solution code:
LARGE = 10 ** 9 + 7
 
 
def solve(n, a_list):
 
    # inverse
    res = 0
    for i in range(n):
        res += pow(a_list[i], LARGE - 2, LARGE)
        res %= LARGE
 
    # primes
    p_candidate_list = [1] * 10 ** 6
    p_candidate_list[0] = 0
    p_candidate_list[1] = 0
    for p in range(2, 10 ** 6):
        if p_candidate_list[p]:
            for q in range(p * p, 10 ** 6, p):
                p_candidate_list[q] = 0
    primes_1000000 = [p for p in range(1000000) if p_candidate_list[p]]

    lcm = 1
    for p in primes_1000000:
        r_max = 0
        for i in range(n):
            r = 0
            while a_list[i] % p == 0:
                r += 1
                a_list[i] = a_list[i] // p
            r_max = max(r_max, r)
        lcm *= pow(int(p), r_max, LARGE)
        lcm %= LARGE
 
    # for q in set(a_list):
    #     lcm *= q
    #     lcm %= LARGE
 
    return res * lcm % LARGE
 
 
def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)
 
 
def test():
    assert solve(3, [2, 3, 4]) == 13
    # assert solve(5, [12, 12, 12, 12, 12]) == 5
    # assert solve(3, [1000000, 999999, 999998]) == 996989508
 
 
if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline

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

from fractions import gcd
from functools import reduce

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

ans = 0

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

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:

def main():
  import sys
  input = sys.stdin.readline

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

  from fractions import gcd
  from functools import reduce

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

  L = reduce(lcm, A)

  ans = 0

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

  print(ans % mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


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


def prime_factor_table(n):
    table = [0] * (n + 1)

    for i in range(2, n + 1):
        if table[i] == 0:
            for j in range(i + i, n + 1, i):
                table[j] = i

    return table


def prime_factor(n, prime_factor_table):
    prime_count = Counter()

    while prime_factor_table[n] != 0:
        prime_count[prime_factor_table[n]] += 1
        n //= prime_factor_table[n]
    prime_count[n] += 1

    return prime_count


primes = prime_factor_table(max(A))


lcm = prime_factor(A[0], primes)

for a in A:
    b = prime_factor(a, primes)
    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)