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 math
def sieve_advance(n):  #n未満の整数iについてi以下でiを割り切る最小の素数を求める。
    minfactor=[-1]*n
    minfactor[0],minfactor[1]=0,1
    isprime=[True]*n
    isprime[0],isprime[1]=False,False

    for i in range(2,n):
        if isprime[i]:
            minfactor[i]=i
            for j in range(i**2,n,i):
                isprime[j]=False
                if minfactor[j]==-1:
                    minfactor[j]=i
    
    return minfactor

minfactor=sieve_advance(10**6+1)
def prime_factor(n): #nをminfactorを利用して素因数分解する
    res={}
    while n!=1:
        prime=minfactor[n]
        exp=0
        while minfactor[n]==prime:
            exp+=1
            n//=prime
        res[prime]=exp

    return res

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

factor=[[] for _ in range(n)]
lcm={}
for i in range(n):
  num=nums[i]
  factor[i]=prime_factor(num)
  for p in factor[i].keys():
    e=factor[i][p]
    if p in lcm:
      lcm[p]=max(lcm[p],e)
    else:
      lcm[p]=e
#print(lcm)

b=[1]*n
for p in lcm.keys():
  e_lcm=lcm[p]
  for i in range(n):
    if p in factor[i]:
      e_a=factor[i][p]
    else:
      e_a=0
    b[i]*=p**(e_lcm-e_a) 
    b[i]%=mod
    
#print(b)
print(sum(b)%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
def sieve_advance(n):  #n未満の整数iについてi以下でiを割り切る最小の素数を求める。
    minfactor=[-1]*n
    minfactor[0],minfactor[1]=0,1
    isprime=[True]*n
    isprime[0],isprime[1]=False,False

    for i in range(2,n):
        if isprime[i]:
            minfactor[i]=i
            for j in range(i**2,n,i):
                isprime[j]=False
                if minfactor[j]==-1:
                    minfactor[j]=i
    
    return minfactor

minfactor=sieve_advance(10**6+1)
from collections import defaultdict
def prime_factor(n): #nをminfactorを利用して素因数分解する
    res=defaultdict(int)
    while n!=1:
        prime=minfactor[n]
        exp=0
        while minfactor[n]==prime:
            exp+=1
            n//=prime
        res[prime]=exp

    return res

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

factor=[[] for _ in range(n)]
lcm=defaultdict(int)
for i in range(n):
  num=nums[i]
  factor[i]=prime_factor(num)
  for p in factor[i].keys():
    e=factor[i][p]
    lcm[p]=max(lcm[p],e)
#print(lcm)

b=[1]*n
for p in lcm.keys():
  e_lcm=lcm[p]
  for i in range(n):
    e_a=factor[i][p]
    b[i]*=p**(e_lcm-e_a) 
    b[i]%=mod
    
#print(b)
print(sum(b)%mod)

Submission status: Time Limit Exceeded

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

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

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]

print(ans%mod)

Submission status: Time Limit Exceeded

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

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

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

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

print(ans%mod)

Submission status: Time Limit Exceeded

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

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

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

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

print(ans%mod)

Submission status: Time Limit Exceeded

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

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

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

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

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
from fractions import gcd

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

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

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)
l = 1
mod = 10**9+7
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:
import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
l = reduce(lcm, a)
mod = 10**9+7
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()))
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
l = reduce(lcm, a)
mod = 10**9+7
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())
from functools import reduce
#import numpy as np
def f(x):
  rtn = {}
  i = 2
  while x > 1:
    if x % i == 0:
      x //= i
      if i in rtn:
        rtn[i] += 1
      else:
        rtn[i] = 1
    else:
      i += 1
  return rtn

def lcm(xs,ys):
  rtn = {}
  for i in xs:
    if i in ys:
      rtn[i] = max(xs[i], ys[i])
    else:
      rtn[i] = xs[i]
  for i in ys:
    if not i in rtn:
      rtn[i] = ys[i]
  return rtn
    
a = list(map(lambda x:f(int(x)), input().split()))
l = reduce(lcm, a)
ans = 0
mod = 10**9 + 7
for j in range(n):
  b = 1
  for i in l:
    if i in a[j]:
      b *= i ** (l[i] - a[j][i])
    else:
      b *= i ** l[i]
  ans += b
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import gcd

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

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

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

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

total = 0
for a in A:
    total += l // a % LARGE

print(total % LARGE)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from fractions import gcd

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

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

input()
A = list(map(int, input().split()))
l = 1
for a in A:
    l = lcm(l, a)

print((l // np.array(A, dtype=np.int64)).sum() % LARGE)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from fractions import gcd
from functools import reduce

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

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

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

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

print((lcm // np.array(A, dtype=np.int64)).sum() % LARGE)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
from fractions import gcd
from functools import reduce

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

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

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

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

print((lcm // np.array(A, dtype=np.int64) % LARGE).sum() % LARGE)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
import numpy as np
def lcm(x,y):
  return (x*y)//gcd(x,y)
l = reduce(lcm, a)
mod = 10**9+7
print(sum(l//(np.array(a)))%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

lcm = dict()

def prime_factorize(n):
    a = dict()
    while not n & 1:
        a[2] = a.get(2, 0) + 1
        n >>= 1
    f = 3
    while f * f <= n:
        if not n % f:
            a[f] = a.get(f, 0) + 1
            n //= f
        else:
            f += 2
    if n != 1:
        a[n] = a.get(n, 0) + 1
    global lcm
    for key, value in a.items():
        lcm[key] = max(lcm.get(key, 0), value)
    return a

N = int(input())
A = map(int, input().split())
A_factored = [prime_factorize(a) for a in A]

total = 0
for a in A_factored:
    d = lcm.copy()
    for key, value in a.items():
        d[key] -= value
    n = 1
    for key, value in d.items():
        n *= key ** value
    total += n % MOD
    total %= MOD

print(total)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def solve():
    MOD = 10**9 + 7

    def getPrimeFactors(x):
        anss = []
        for d in range(2, int(x**0.5)+1):
            while x%d == 0:
                anss.append(d)
                x //= d
        if x != 1:
            anss.append(x)
        return anss

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

    PFss = []
    Primes = set()
    for A in As:
        PFs = getPrimeFactors(A)
        cnt = Counter(PFs)
        PFss.append(cnt)
        Primes |= cnt.keys()

    cntP = Counter()
    for PFs in PFss:
        for key, num in PFs.items():
            cntP[key] = max(cntP[key], num)

    lcmA = 1
    for key, num in cntP.items():
        lcmA *= pow(key, num, MOD)
        lcmA %= MOD

    def getInvs(n, MOD):
        invs = [1] * (n+1)
        for x in range(2, n+1):
            invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
        return invs

    invs = getInvs(10**6, MOD)

    ans = 0
    for A in As:
        ans += lcmA * invs[A]
        ans %= MOD

    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
import fractions
from functools import reduce

def main():
    N = int(input())
    a = list(map(int,input().split()))
    MOD = 10**9+7
            
    def lcm(x,y):
        return((x*y)//fractions.gcd(x,y))
        
    l = reduce(lcm,a)
    ans = 0
    for num in a:
        ans += l//num
        ans %= MOD
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    MOD = 10**9+7
            
    def lcm(x,y):
        return((x*y)//fractions.gcd(x,y))
        
    ans = 0
    l0 = 1
    for num in a:
        l1 = lcm(l0,num)
        ans = (ans*(l1//l0)+l1//num)%MOD
        l0 = l1
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    MOD = 10**9+7
            
    def lcm(x,y):
        return((x*y)//fractions.gcd(x,y))
        
    ans = 0
    l = [1]
    for num in a:
        l.append(lcm(l[-1],num))
        ans = (ans*(l[-1]//l[-2])+l[-1]//num)%MOD
        
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
Bi = list(map(int, input().split()))
soinsu = []
for i in range(N):
    soinsu.append([])
    B = Bi[i]
    for k in range(int(1+Bi[i]**1/2)):
        while B % (k+2) == 0:
            soinsu[i].append(k+2)
            B = B / (k+2)
soinsu_set = set()
for i in range(N):
    soinsu_set = soinsu_set | set(soinsu[i])
sum_number = 1
for i in soinsu_set:
    count = 0
    for k in range(N):
        count_k = soinsu[k].count(i)
        if count_k > count:
            count = count_k
    sum_number = sum_number * (i ** count)
A = 0
for i in range(N):
    A += sum_number / Bi[i]
print(int(A%(10**9+7)))

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)

def main():
    mod=1000000007
    n=int(input())
    A=tuple(map(int,input().split()))
    l=1
    for a in A:
        l=lcm(l,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:
import fractions


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


N = int(input())
A = list(map(int, input().split()))
A_lcm = 1
for a in A:
    A_lcm = lcm(A_lcm, a)

ans, MOD = 0, 10 ** 9 + 7
for a in A:
    ans += A_lcm // a
    ans = ans % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import numpy as np


def factor(primes, target):
    fact = {}
    x = target
    while x >= 2:
        tmp = primes[x]
        if tmp in fact:
            fact[tmp] += 1
        else:
            fact[tmp] = 1
        x = int(x/tmp)

    return fact


# get N
N = int(input())
A = np.array(input().split(), np.int64)
#A = [int(x) for x in input().split()]
#N = 3
#A = [1000000, 999999, 999998]
#MAX_NUM = 1000000

max_num = max(A)
# エラトステネスの篩
primes = np.zeros(max(A) + 1, np.int64)
primes[0] = primes[1] = -1
for x in range(2, max_num+1):
    if primes[x] != 0:
        continue

#    print(x)
    primes[x] = x
    i = x*2
    while i < max_num + 1:
        if primes[i] == 0:
            primes[i] = x
        i += x

final_fact = {}
for i in range(len(A)):
    tmp = factor(primes, A[i])
#    print(tmp)
    for key, value in tmp.items():
        if key in final_fact:
            tmp_value = final_fact[key]
            if tmp_value < value:
                final_fact[key] = value
        else:
            final_fact[key] = value

lcm = 1
for key, value in final_fact.items():
    lcm *= int(key ** value)
# print(lcm)

ans = 0
for i in A:
    ans += (lcm/i)
print(int(ans % 1000000007))

Submission status: Time Limit Exceeded

Solution code:
import fractions
import numpy as np


def factor(primes, target):
    fact = {}
    x = target
    while x >= 2:
        tmp = primes[x]
        if tmp in fact:
            fact[tmp] += 1
        else:
            fact[tmp] = 1
        x = int(x/tmp)

    return fact


# get N
N = int(input())
A = [int(x) for x in input().split()]
#N = 3
#A = [1000000, 999999, 999998]
#MAX_NUM = 1000000

max_num = max(A)
# エラトステネスの篩
primes = np.zeros(max(A) + 1)
primes[0] = primes[1] = -1
for x in range(2, max_num+1):
    if primes[x] != 0:
        continue

#    print(x)
    primes[x] = x
    i = x*2
    while i < max_num + 1:
        if primes[i] == 0:
            primes[i] = x
        i += x

final_fact = {}
for i in range(len(A)):
    tmp = factor(primes, A[i])
#    print(tmp)
    for key, value in tmp.items():
        if key in final_fact:
            tmp_value = final_fact[key]
            if tmp_value < value:
                final_fact[key] = value
        else:
            final_fact[key] = value

lcm = 1
for key, value in final_fact.items():
    lcm *= int(key ** value)
# print(lcm)

ans = 0
for i in A:
    ans += (lcm/i)
print(int(ans % 1000000007))

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
    if (y == 0):
        return x
    else:
        return gcd(y, x % y)
ans = 0
while (True):
    try:
        n = input()
        ans = 0
        s = 1
        a = []
        a = input().split()
        for i in a:
            i = int(i)
            s = s // gcd(max(s, i), min(s, i)) * i
        for i in a:
            i = int(i)
            ans = (ans + s // i) % 1000000007
        print(ans)
    except:
        break

Submission status: Time Limit Exceeded

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

maximum = max(v)
max_sqrt = int(maximum**0.5)+1
c = [0 for i in range(maximum+1)]

def prim(x):
	v = [0 for i in range(x+1)]
	while x>1:
		for i in range(2, int(x**0.5)+1):
			if x%i == 0:
				v[i] += 1
				x //= i
				break
		else:
			v[x] += 1
			break
	for i, a in enumerate(v):
		c[i] = max(c[i], a)
	return v

all_primes = []
for i in v:
	all_primes.append(prim(i))



total = 0

for i, primes in enumerate(all_primes):

	number = 1
	for j in range(maximum+1):
		if j>1:
			try:
				number *= j**(c[j] - primes[j])
			except IndexError:
				number *= j**(c[j])
	total += number


print(int(total % (1e9+7)))

Submission status: Time Limit Exceeded

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

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

def lcm_list(numbers):
    return reduce(lambda x, y: (x * y) // gcd(x, y), numbers, 1)

lcm = lcm_list(a)
aa = []
for i in range(len(a)):
    aa.append(lcm // a[i])
ans = sum(aa) % 1000000007
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

lcm = lcm_list(a)
aa = []
for i in range(len(a)):
    aa.append(lcm // a[i])
ans = sum(aa) % 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
N=int(input())
A=list(map(int,input().split()))
ans=ModInt(0)
Divisor=dict([(i,0) for i in range(1000000)])
def frac(n,div):
    ret = 0
    while not (n % div) :
        n //= div
        ret += 1
    return ret,n
for i in A:
    divided=i
    for j in range(2,int(divided**(0.5)+2)):
        chk,divided = frac(divided,j)
        if chk > Divisor[j]:Divisor[j] = chk
    Divisor[divided] = max(1,Divisor[divided])
LCM=ModInt(1)
for i in range(2,1000000):
    LCM*=i**ModInt(Divisor[i])
for i in A:
    ans+=LCM/ModInt(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
a = [int(c) for c in input().split()]
MOD = 10**9+7
dic = defaultdict(int)
ls = defaultdict(int)
for i in range(N):
  c = a[i]
  for j in range(2, int(c**0.5)+1):
    if c%j==0:
      cnt = 0
      while c%j==0:
        c //= j
        cnt += 1
      ls[(i,j)] = cnt
      dic[j] = max(dic[j], cnt)
  if c!=1:
    ls[(i,c)] = 1
    dic[c] = max(dic[c], 1)
ans = 0
for i in range(N):
  b = 1
  for k in dic.keys():
    x = int(k)
    b *= k**(dic[k]-ls[(i,k)])
    b %= MOD
  ans += b
  ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
x=reduce(lambda x,y: y//gcd(x,y)*x, a)
ans=0
for i in a:
  ans+=x//i
  ans%=1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
x=reduce(lambda x,y: y//gcd(x,y)*x, set(a))
ans=0
for i in a:
  ans+=x//i
  ans%=1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def PrimeFactorization(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1:
        pf[m] = 1
    return pf


def lcmlist(l):
    from collections import defaultdict
    d = defaultdict(int)
    for i in set(l):
        for k, v in PrimeFactorization(i).items():
            if v > d[k]:
                d[k] = v
    n = 1
    for k, v in d.items():
        n *= k ** v
    return n

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


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


def greatLcm(array):
    ans = 1
    for i in array:
        ans = lcm(ans, i)
    return ans


mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
p = greatLcm(a)
ans = 0
for j in a:
    ans += p // j
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
from math import *
input = sys.stdin.readline

def main():
    n = int(input())
    As = list(map(int, input().split()))
    mod = 10**9 + 7

    isp, fac_table = min_factor_table(max(As)+1)
    fac_table = fac_table[:-1]

    prime_factors = defaultdict(int)
    #各素因数の最大値を保持
    for i in range(n):
        pf = factorization(fac_table, As[i])
        for j in pf:
            prime_factors[j] = max(pf[j], prime_factors[j])
    
    lcm = 1
    for key in prime_factors:
        lcm *= pow(key, prime_factors[key])    
    
    ans = 0
    ans = sum([lcm // As[i] for i in range(n)]) % mod

    print(ans)
    return

def factorization(table, n):
    # O(log N )
    k = n
    prime_factors = defaultdict(int)
    while k != 1:
        if k % table[k] == 0:
            prime_factors[table[k]] += 1
            k //= table[k]

    return prime_factors


def min_factor_table(n):
    #多分計算量はO(N log N)
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    min_factor = [None]*(n+1)
    min_factor[0] = 0
    min_factor[1] = 1
    cnt = 0
    # 計算する必要があるのは√n まで
    for i in range(2, n+1):   
        for j in range(2, ceil(n/i)):
            cnt += 1
            if min_factor[i*j] is None:
                min_factor[i*j] = i
            is_prime[i*j] = False
        if is_prime[i]:
            min_factor[i] = i
    return is_prime, min_factor


#参考: https://qiita.com/ophhdn/items/e6451ec5983939ecbc5b
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd

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

def lcm_list(l):
    lcm = l[0]
    for i in range(len(l)):
        lcm = lcm*l[i] // gcd(lcm, l[i])
    return lcm

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

lcm = lcm_list(As)
b = [lcm//As[i] for i in range(n)]

print(sum(b) % mod)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
L = list(map(int,input().split()))
m = 10**9+7
ans = 0
def gcd(x,y):
  while y != 0:
    cur = x
    x = y
    y = cur%y
  return x
if n != 1:
  lcm = L[0]*L[1]//gcd(L[0],L[1])
  for i in range(2,n):
    p = gcd(L[i],lcm)
    lcm = L[i]*lcm//p
  for i in range(n):
    ans = (ans+(lcm//L[i]))%m
else:
  ans = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
L = list(map(int,input().split()))
m = 10**9+7
ans = 0
def gcd(x,y):
  while y != 0:
    cur = x
    x = y
    y = cur%y
  return x
if n != 1:
  lcm = L[0]*L[1]//gcd(L[0],L[1])
  for i in range(2,n):
    p = gcd(L[i],lcm)
    lcm = L[i]*lcm//p
  for i in range(n):
    ans = (ans+((lcm//L[i])%m))%m
else:
  ans = 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from copy import deepcopy
    N = int(input())
    A = list(map(int, input().split()))
    mA = 0
    for i in range(N):
        if mA < A[i]:
            mA = A[i]
    n = 2
    c = 1
    tA = deepcopy(A)
    while sum(A) > N:
        flag = False
        for i in range(N):
            if A[i] % n == 0:
                A[i] = A[i] // n
                flag = True
        if flag:
            c *= n
        else:
            n += 1
    b = 0
    for i in range(N):
        b += c // tA[i]
    print(b % (10**9+7))
resolve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce


def gcd(a, b):
    """
    return gcd of a,b
    ユークリッド
    """
    while b:
        a, b = b, a % b
    return a


def list_gcd(l):
    """
    l: list
    l のgcd を返す
    """
    return reduce(gcd, l)


def lcm(a, b):
    """
    a,bの最小公倍数
    """
    return a*b//gcd(a, b)


def list_lcm(l):
    """
    l:list
    lのlcmを返す
    """
    return reduce(lcm, l)


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

LCM = list_lcm(L)
print(sum([LCM//v for v in L])%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# from random import randint

MOD = 10**9+7

N = int(input())
A = list(map(int, input().split()))
# N = 10000
# A = [randint(1, 10**6) for _ in range(N)]

def gcd(a, b):
    if a > b:
        a, b = b, a
    if a == 0:
        return b
    return gcd(b%a, a)
def lcm(a, b):
    return (a * b) // gcd(a, b)

a_lcm = A[0]
for a_i in A[1:]:
    a_lcm = lcm(a_lcm, a_i)

sum_num = 0
for a_i in A:
    sum_num = (sum_num + (a_lcm//a_i)) % MOD

print(sum_num)

Submission status: Time Limit Exceeded

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

#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return 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)

def calc_gcd_list(l):
    gcd = l[0]
    for i in range(1, N):
        gcd = gcd(gcd, l[i])
    return gcd

def calc_lcm_list(l):
    lcm = l[0]
    for i in range(1, N):
        lcm = lcm * l[i] // gcd(lcm, l[i])
    return lcm


N = input_one_number()
lstA = input_multiple_number_as_list()
lcm = calc_lcm_list(lstA)
pow = 10**9 +7
print(sum(lcm//a for a in lstA)%pow)

Submission status: Time Limit Exceeded

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

#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))



#複数の最小公倍数
def calc_lcm_list(l):
    lcm = l[0]
    for i in l:
        lcm = lcm * i // fractions.gcd(lcm, i)
    return lcm


import fractions
N = input_one_number()
lstA = input_multiple_number_as_list()

lcm = calc_lcm_list(lstA)

ans = 0

pow = 10**9 +7

print(sum(lcm//a for a in lstA)%pow)

Submission status: Time Limit Exceeded

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

#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))



#複数の最小公倍数
def calc_lcm_list(l):
    lcm = l[0]
    for i in l:
        lcm = lcm * i // fractions.gcd(lcm, i)
    return lcm


import fractions
N = input_one_number()
lstA = input_multiple_number_as_list()

lcm = calc_lcm_list(lstA)

ans = 0
for a in lstA:
    ans += (lcm // a)

print(ans % 1000000007)

Submission status: Time Limit Exceeded

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

#整数値入力 1文字の入力
def input_one_number():
    return int(input())

#整数値龍力　複数の入力
def input_multiple_number():
    return map(int, input().split())

#整数値龍力　複数の入力(配列)
def input_multiple_number_as_list():
    return list(map(int, input().split()))



#複数の最小公倍数
def calc_lcm_list(l):
    lcm = l[0]
    for i in range(1, N):
        lcm = lcm * l[i] // fractions.gcd(lcm, l[i])
    return lcm


import fractions
N = input_one_number()
lstA = input_multiple_number_as_list()

gcd = calc_lcm_list(lstA)

ans = 0
for a in lstA:
    ans += (gcd // a)

print(ans % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_prime_factors(n):
    import numpy as np
    factors = np.arange(0, n+1, 1, dtype=np.int64)
    for i in range(2, n+1):
        if factors[i] == i:
            np.minimum(factors[i*2::i], i, out=factors[i*2::i])
    return factors

#

def main():
    N=ii()
    A=lmis()
    factors = get_prime_factors(10**6)
    d_lcm = defaultdict(int)
    d = [None] * N
    for i, a in enumerate(A):
        d[i] = dd = defaultdict(int)
        p = a
        while p > 1:
            dd[factors[p]] += 1
            p //= factors[p]
        for key in dd.keys():
            d_lcm[key] = max(d_lcm[key], dd[key])
    ans = 0
    for dd in d:
        tmp = 1
        for p in d_lcm.keys():
            tmp *= p ** (d_lcm[p] - dd[p])
            tmp %= N1097
        ans += tmp
        ans %= N1097
    print(ans)


main()