Problem:


Score : 500 points

Problem Statement

Given are N positive integers A_1,...,A_N.

Consider positive integers B_1, ..., B_N that satisfy the following condition.

Condition: For any i, j such that 1 \leq i < j \leq N, A_i B_i = A_j B_j holds.

Find the minimum possible value of B_1 + ... + B_N for such B_1,...,B_N.

Since the answer can be enormous, print the sum modulo (10^9 +7).

Constraints

1 \leq N \leq 10^4

1 \leq A_i \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the minimum possible value of B_1 + ... + B_N for B_1,...,B_N that satisfy the condition, modulo (10^9 +7).

Sample Input 1

3
2 3 4

Sample Output 1

13

Let B_1=6, B_2=4, and B_3=3, and the condition will be satisfied.

Sample Input 2

5
12 12 12 12 12

Sample Output 2

5

We can let all B_i be 1.

Sample Input 3

3
1000000 999999 999998

Sample Output 3

996989508

Print the sum modulo (10^9+7).



Sample input:
3
2 3 4


Sample output:
13

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

count = 0

for i in a:
  count += l//i
  count %= (10**9+7)

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 6) 
mod=10**9+7
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)



def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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

def div(a, b):
    return mul(a, power(b, mod-2))

n=input()
hoge=list(map(int,input().split()))
#hoge=[i for i in range(1,10**4)]
ans=0

l=lcm_list(hoge)#%mod
for i in hoge:
    tmp=(l//i)%mod
    ans+=tmp
    ans%=mod
ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from time import time
from fractions import gcd
start=time()
M=10**9+7
lcm=lambda x,y:x//gcd(x,y)*y
n,*a=map(int,open(0).read().split())
if n==1:
    print(1)
    exit()
s=a[0]
for t in a[1:]:
    s=lcm(s,t)
    if time()-start>.6:
        break
c=0
for i in a:
    c+=s//i
    c%=M
print(c)

Submission status: Time Limit Exceeded

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

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

GCD = {}


def gcd(x, y):
    if x < y:
        x, y = y, x

    if (x, y) in GCD:
        return GCD[(x, y)]

    if y == 0:
        return x
    else:
        res = gcd(y, x % y)
        GCD[(x, y)] = res
        return res


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


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

wa = 0
for i in range(N):
    wa += (saidaikoubaisuu // A[i])

print(wa % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys, math
def input():
    return sys.stdin.readline()[:-1]
from itertools import permutations, combinations
from collections import defaultdict, Counter
from math import factorial
from fractions import gcd
div = 10**9 + 7

sys.setrecursionlimit(10**7)
N = int(input())
A = list(map(int, input().split()))
sA = list(set(A))

val = 1
def lcm(a, b):
    ret = gcd(a, b)
    ret = a*b//ret
    return ret

val = sA[0]
for a in sA[1:]:
    val = lcm(val, a)

sumB = 0
B = [val//a for a in A]
sumB = sum(B)
sumB %= div

print(sumB)

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
        lcm %= mod

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
mod = 10**9+7

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


def main():
    N = I()
    A = LI()

    LLCM = [0]*N
    LLCM[0] = A[0]

    for i in range(1,N):
        LLCM[i] = LLCM[i-1]*A[i] // gcm(LLCM[i-1],A[i])

    B = [0]*N
    for i in range(N):
        B[i] = LLCM[N-1] * pow(A[i],mod-2,mod)
        B[i] %= mod

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

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

def lcms(a):
    ans = a[0]
    for i in range(1, N):
        ans = ans * a[i] // fractions.gcd(ans, a[i])
    return ans


N = int(input())
A = [int(x) for x in input().split()]

lcm_a = lcms(A)

B = [lcm_a // a for a in A]
sum_b = 0
for b in B:
    sum_b = (sum_b + b) % (10**9+7)

print(sum_b)

Submission status: Time Limit Exceeded

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

    N = int(input())
    A = tuple(map(int, input().split()))
    import fractions
    from functools import reduce

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

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

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

    print(ans%(10**9+7))
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import numpy as np

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

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

a_lcm = lcm(a)
aa = np.array(a)
aa = a_lcm // aa
aa = aa.tolist()
ans = 0
for i in aa:
    ans += i
    ans %= 10**9+7

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def prime_decomposition(n):
    table = defaultdict(int)
    # table = [0] * (n + 1)

    i = 2
    while n % i == 0:
        n //= i
        table[i] += 1

    i = 3
    while i * i <= n:
        while n % i == 0:
            n //= i
            table[i] += 1
        i += 2

    if n > 1:
        table[n] += 1

    return table


def main():
    mod = 10 ** 9 + 7

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

    t = [prime_decomposition(x) for x in a]

    lcm_d = defaultdict(int)
    for pd in t:
        for prime, power in pd.items():
            lcm_d[prime] = max(lcm_d[prime], power)

    gcd_d = defaultdict(lambda: mod - 1)
    for pd in t:
        for prime, power in lcm_d.items():
            pd[prime] = power - pd[prime]
            gcd_d[prime] = min(pd[prime], gcd_d[prime])

    gcd_ = 1
    for prime, power in gcd_d.items():
        gcd_ = (gcd_ * pow(prime, power, mod)) % mod

    ret = 0
    for pd in t:
        curr = 1
        for prime, power in pd.items():
            curr = (curr * pow(prime, power - gcd_d[prime], mod)) % mod
        ret = (ret + curr) % mod

    ret = ret * gcd_ % mod

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import fractions 
from functools import reduce
arr = list(map(int,input().split()))

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

def lcma(numbers):
    return reduce(lcm_base, numbers, 1)
  
a = lcma(arr)

ans = [(a//i)%1000000007 for i in arr]

print(sum(ans)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

A.sort()

l = 1
for i in A:
  if l % i != 0:
    l = lcm(l, i)

num = [0] * (10 ** 6 + 1)

ans = 0
for i in A:
  if num[i] == 0:
    v = l // i
    num[i] = v
  else:
    v = num[i]
  ans = (ans + v) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import fractions
    import sys
    input = sys.stdin.readline
    N = int(input())
    a = tuple(map(int,input().split()))
    MOD = 10**9+7
    g1 = 1
    for i,t in enumerate(a[:N//2]):
        g1 = divmod(g1*t,fractions.gcd(g1,t))[0]

    g2 = 1
    for i,t in enumerate(a[N//2:]):
        g2 = divmod(g2*t,fractions.gcd(g2,t))[0]
    res = 0
    g = fractions.gcd(g1,g2)

    r1 = (g2//g)%MOD
    for t in a[:N//2]:
        res += r1*divmod(g1,t)[0]%MOD
    r2 = (g1//g)%MOD
    for t in a[N//2:]:
        res += r2*divmod(g2,t)[0]%MOD
    print(res%MOD)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

readline = sys.stdin.buffer.readline


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

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

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

    return arr


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    C = 10**9 + 7

    d = collections.defaultdict(list)

    for a in A:
        B = factorization(a)
        for b in B:
            d[b[0]].append(b[1])
    e = 1
    for k, v in d.items():
        e *= k**max(v)

    ans = 0
    for a in A:
        ans += (e // a)
        ans %= C
    print(ans)


main()

Submission status: Time Limit Exceeded

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

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

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

def list_lcm(l):
    return functools.reduce(lcm,l)

g = list_lcm(A)

B = [g // a for a in A]
print(sum(B) % MOD)

Submission status: Time Limit Exceeded

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

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

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

if N == 1:
    res = 1
else:
    l = lcm(A[0], A[1])
    for i in range(2, N):
        l = lcm(l, A[i])

    for i in range(N):
        res += l//A[i]

print(res % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
def primes(n):
  is_prime = [True] * (n + 1)
  is_prime[0] = False
  is_prime[1] = False
  for i in range(2, int(n**0.5) + 1):
    if not is_prime[i]:
      continue
    for j in range(i * 2, n + 1, i):
      is_prime[j] = False
  return [i for i in range(n + 1) if is_prime[i]]
table = primes(int((max(a))**(1/2))+1)
l = len(table)
r = []
for j,p in enumerate(table):
  x = [0 for _ in range(n)]
  flag = False
  for i in range(n):
    if a[i]%p == 0:
      flag = True
      a[i] //= p
      cnt = 1
      while a[i]%p == 0:
        cnt += 1
        a[i] //= p
      x[i] += cnt
  if flag == True:
    r.append([p,x])    
ex = {}
for i in range(n):
  if a[i] != 1:
    if a[i] in ex.keys():
      ex[a[i]].append(i)
    else:
      ex[a[i]] = [i]
for k in ex.keys():
  x = [0 for _ in range(n)]
  for el in ex[k]:
    x[el] = 1
  r.append([k,x]) 
l = len(r)
for i in range(l):
  mx = max(r[i][1])
  for j in range(n):
    r[i][1][j] = mx - r[i][1][j]
ans = 0
def fc(x, n):
  if n == 0:
    return 1
  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (K * x)%(10**9+7)
      x = (x*x)%(10**9+7)
      n = (n - 1) // 2
    else:
      x = (x*x)%(10**9+7)
      n = n // 2
  return (K * x)%(10**9+7)
for i in range(n):
  tmp = 1
  for j in range(l):
    tmp = (tmp*fc(r[j][0],r[j][1][i]))%(10**9+7)
  ans = (ans+tmp)%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
import fractions

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
a = LI()
lcmall = a[0]
for i in range(1, N):
    lcmall = lcmall * a[i] // fractions.gcd(lcmall, a[i])
# print(lcmall%DVSR)

# N=II()
# INL = LI()
# gcdall=INL[0]
# lcmall=INL[0]
# for i in INL:
#     gcdall = gcd(gcdall, i)%DVSR
#     lcmall = (((lcmall*i)%DVSR)*INV(gcd(lcmall, i)))%DVSR
# # print(lcmall)

res = 0
for i in a:
    # print(((lcmall*INV(i))%DVSR * i)%DVSR)
    res += (lcmall*INV(i))%DVSR
print(res%DVSR)

Submission status: Time Limit Exceeded

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

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

N = int(input())
A = [int(l) for l in input().split()]


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

l = int(l)
MOD = 1000000007

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

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
N = int(input().split()[0])
a = np.array([int(i) for i in input().split()])

def lcm(a, b):
    x = a * b
    if a < b:
        tmp = a
        a = b
        b = tmp
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return x / b

l = a[0]
for i in range(1, N):
    l = lcm(l, a[i])

MOD = 1000000007

ans = np.sum(l / a)

print(int(ans) % MOD)

Submission status: Time Limit Exceeded

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

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


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

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

b=[ans // a[i] for i in range(n)]

sum = 0
for i in range(n):
  sum += b[i]
  if sum >= 10**9+7:
    sum = sum %(10**9+7)
    
print(sum)

Submission status: Time Limit Exceeded

Solution code:

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

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


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

MOD = 10**9+7
ans = 0
t = 1
for i in l:
    t = lcm(t,i)

for i in l:
    ans +=t//i
    ans %=MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
MOD = 1000000007
def g(a, b):
 while b:a,b=b,a%b
 return a
def h(a,b):return(a*b)//g(a,b)
n=int(stdin.readline())
a=list(map(int,stdin.readline().split()))
l=1
for i in a:l=h(l,i)
s=0
for i in a:s=(s+l//i)%MOD
print(s)

Submission status: Time Limit Exceeded

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


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


MOD = 10**9 + 7
N = int(input())
A = list(map(int, input().split()))
A.sort()
A = A[::-1]

l = A[0]
for a in A:
  if l%a != 0:
    l = lcm(l, a)

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

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

def saisho_ko_baisu(A,B):
    # A < B
    if B < A:
        A,B = B,A
    x = A*B
    r = B%A
    while r!=0:
        B = A
        A = r
        r = B%A
    return x//A

A.sort()
tmp = saisho_ko_baisu(A[0], A[1])
for i in range(2,N):
    if tmp % A[i] != 0:
        tmp = saisho_ko_baisu(tmp, A[i])
res = 0
for a in A:
    res += tmp//a

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

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

#from math import gcd
from fractions import gcd

def main():
	n=int(input())
	A=list(map(int,input().split()))
	B=set(A)
	A=list(A)
	A.sort(reverse=True)
	a=1
	for i in A:
		a=a*i//gcd(a, i)
	ans=0
	for i in A:
		ans+=(a//i)
		ans%=mod
	print(ans)
	
	
	
	
	
	


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7

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

def power(a,p):
    T=[a]
    while 2**(len(T))<p:
        T.append(T[-1]**2%p)
    b=bin(p-2)
    ans=1
    for i in range(len(b)-2):
        if int(b[-i-1])==1:
            ans=ans*T[i]%p
    return ans   

l=A[0]
for i in range(n-1):
    l=lcm(l,A[i+1])
s=0
for i in range(n):
    s+=l*power(A[i],mod)%mod
    s%=mod
print(s)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

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

l = 1
for i in range(len(a)):
    if(l>a[i]):
        l = lcm(l,a[i])
    else:
        l = lcm(a[i],l)

count = 0
for i in range(len(a)):
    count += int(l/a[i])
    count = count % (1000000007)
print(count)

Submission status: Time Limit Exceeded

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

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



n = int(input())

ans =1
res=0
arr = input().strip().split()


for i in range(n):
    arr[i] = int(arr[i])
    ans = lcm(ans,arr[i])
            
for i in range(n):
    res += ans // arr[i]
    res%=1000000007
            
print(res)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

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

n = int(input())
A = list(map(int, input().split()))
k = lcm_list(A)
r = 0
ln = list(range(n))
t = 10**9+7
for i in ln:
    r += k//A[i]
    r %= t
print(r)

Submission status: Time Limit Exceeded

Solution code:
from time import time
from fractions import gcd
start=time()
M=10**9+7
lcm=lambda x,y:x//gcd(x,y)*y
n,*a=map(int,open(0).read().split())
if n==1:
    print(1)
    exit()
s=a[0]
for t in a[1:]:
    s=lcm(s,t)
    if time()-start>.6:
        s=lcm(s,max(a))
        break
c=0
for i in a:
    c+=s//i
    c%=M
print(c)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd


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


MOD = 10**9 + 7

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

x = reduce(lcm, A)

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    ans+=(f//iu)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()

Submission status: Time Limit Exceeded

Solution code:
import math
mod=10**9+7
N=10**6+1
inv_t=[0]+[1]
for i in range(2,N):
    inv_t+=[inv_t[mod%i]*(mod-int(mod/i))%mod]
n=int(input())
A=list(map(int,input().split()))
l=[0]*10**6
for a in A:
    for i in [2]+list(range(3,int(math.sqrt(a))+1,2)):
        c=0
        while a%i==0:
            c+=1
            a//=i
        l[i]=max(l[i],c)
    if a!=1:
        l[a]=max(l[a],1)
lcm=1
for i in range(10**6):
    if l[i]!=0:
        lcm=(lcm*(i**l[i]))%mod
ans=0
for a in A:
    ans=(ans+lcm*inv_t[a])%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:


def gcd(x, y): 
      
    while(y): 
        x, y = y, x % y 
      
    return x 

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
mod = 1000000007

def add(a, b):
    return (a + b) % mod

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

def cal(n):
  return ans // n
b = list(map(cal,a))
for j in range(0, n):
  ans_ans = add(ans_ans,b[j])
print(ans_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()))

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 a in A:

    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
        lcm %= mod

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from fractions import gcd
import math
n = int(input())
a = list(map(int, input().split()))
def lcm(a, b):
    return (a * b) // gcd(a, b)
m = 1
for x in a:
    m = lcm(m, x)
# print(m)
MOD = 1000000007
ans = 0
for x in a:
    b = m // x
    ans = (ans + b) % MOD
print(math.floor(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd #直して
n = int(input())
a = list(map(int, input().split()))

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

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

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

    return arr


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

def lcms(a):
    ans = a[0]
    for i in range(1, N):
        ans = ans * a[i] // fractions.gcd(ans, a[i])
    return ans


N = int(input())
A = [int(x) for x in input().split()]

lcm_a = lcms(A)

B = [lcm_a // a for a in A]
print(sum(B) % (10**9+7))

Submission status: Time Limit Exceeded

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

div = 10**9+7

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

import fractions
ans = A[0]
for a in A[1:]:
    ans = ans * a // fractions.gcd(ans, a)

# sum_b = 0
# for a in A:
B = [ans // a % div for a in A]

print(sum(B) % div)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import functools
# import collections
import fractions
N = int(input())
A = [int(i) for i in input().split()]
S = set(A)


mod = 10**9 + 7


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


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


lcm = lcm(S)

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

Submission status: Time Limit Exceeded

Solution code:
#import math
#from functools import reduce
from fractions import gcd
#from functools import lru_cache

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

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

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


n = int(input())
A = [int(x) for x in input().split()]

t_lcm = lcm(A)
count = 0
for i in A:
    count += t_lcm//i
    
print(count%(10**9+7))

Submission status: Time Limit Exceeded

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


def lcm(a, b):
    h, l = max(a, b), min(a, b)
    while l != 0:
        h, l = l, h % l
    return a * b // h


for i in range(N):
    c = lcm(c, A[i])
M = 10 ** 9 + 7
ans = 0
for a in A:
    ans += (c // a) % M
print(ans % M)

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 range(N):
  lcm=(lcm*A[i])//gcd(lcm,A[i])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions

input = sys.stdin.readline

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


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

index = A[0]

for a in A[1:]:
    index = index * a // fractions.gcd(index, a)

MOD = 10**9 + 7

ans = 0

for a in A:
    ans += (index//a) % MOD

print(ans%MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

import fractions
def min_kou(a):
  ans = a[0]
  for i in range(1, len(a)):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
  return ans

def main():
  N = int(input())
  A = list(map(int, input().split()))
  min_res = min_kou(A)
  ans = 0
  for i in A:
    ans += min_res // i
  print(ans % 1000000007)
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
#a,b = map(int,input().split())
A = list(map(int,input().split()))
#A = [int(input()) for i in range(N)]
#A = [list(map(int,input().split())) for i in range(N)]
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b):
    gcda = gcd(a,b)
    return a*b//gcda
def lcmlist(lista):
    if len(lista) == 1:
        return lista[0]
    else:
        lista2 = []
        for i in range(1,len(lista),2):
            lista2.append(lcm(lista[i],lista[i-1]))
        if len(lista)%2 != 0:
            lista2.append(lista[-1])
        from functools import reduce
        return reduce(lcm,lista2)
mod = 10**9 + 7
lcml = lcmlist(A)
ans = 0
for i in A:
    ans = (ans + lcml//i)%mod
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

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

mod = 1000000007
n = int(input())
nums = list(map(int, input().split()))

print(sum([(reduce(lcm, nums) // x) % mod for x in nums]) % mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def main():
    mod= 10 ** 9 + 7
    nok = 1
    n = int(input())
    a = [int(i) for i in input().split()]
    for i in a:
        nok = nok * i // gcd(nok, i)
    ans = 0
    for i in a:
        ans = (ans + nok // i) % mod
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def prime_factor(n):
    c = Counter()
    i = 2
    while i * i <= n:
        while (n % i == 0):
            c[i] += 1
            n = n//i
        i += 1
    if n != 1:
        c[n] += 1

    return c

MOD = 10**9+7

N = int(input())
A = list(map(int, input().split()))
ans = 0
prime_list = []
max_list = Counter()
for a in A:
    c = prime_factor(a)
    prime_list.append(c)
    for key, val in c.items():
        max_list[key] = max(max_list[key], val)
pow_dict = {}
for c in prime_list:
    tmp = 1
    for key, val in max_list.items():
        if (key, val-c[key]) in pow_dict:
            tmp = (tmp * pow_dict[(key, val-c[key])])%MOD
        else:
            p_val = pow(key, (val-c[key]), MOD)
            tmp = (tmp * p_val)%MOD
            pow_dict[(key, val-c[key])]= p_val
    ans = (ans + tmp)%MOD
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
def main():
  _=input()
  a=tuple(map(int,input().split()))
  fgcd=fractions.gcd
  def lcm_base(x, y):
    return (x * y) // fgcd(x, y)
  def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
  q=lcm(a)
  x=[q//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()