n,m이 매우 클 때 (a1a2a3...an)/(b1b2b3...bm) 분수를 계산하는 마법같은 방법

28828번: Упражнения в умножении (acmicpc.net)

 

 

$\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}}$과 $10^{6}$ 이하로 차이나는 정수를 구하는 문제

 

n,m이 $10^{5}$까지이고, $a_{i}, b_{i}$가 $10^{9}$이라 단순하게 곱하고 나누면 시간초과가 난다

 

v1 = 1

for i in range(n):
    
    v1 *= A[i]

v2 = 1

for j in range(m):
    
    v2 *= B[j]

print(v1//v2)

 

 

곱셈을 덧셈으로 바꾸는 대표적인 방법이 로그를 취하는 것이다

 

$\frac{a_{1}a_{2}...a_{n}}{b_{1}b_{2}...b_{m}} = X$라고 하면 $$logX = log(a_{1}a_{2}...a_{n}) - log(b_{1}b_{2}...b_{m}) = \sum_{i = 1}^{n} log(a_{i}) - \sum_{j = 1}^{m} log(b_{j})$$

 

따라서 배열 A,B 원소 각각에 로그를 취하고 더해서 두 값을 빼면 logX를 구할 수 있고

 

여기에 exp값을 취해주면 X가 된다

 

from decimal import *
import math

n,m = map(int,input().split())

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

v1 = 0

for i in range(n):
    
    v1 += Decimal(math.log(A[i]))

v2 = 0

for j in range(m):
    
    v2 += Decimal(math.log(B[j]))

X = v1 - v2

print(int(math.exp(X)))

 

 

10^6 차이면 여유로울줄 알았는데 Decimal 안쓰면 틀리더라

 

Decimal에도 ln()이랑 exp()있는데 시간 엄청 걸리더라(8초)

 

그래서 그냥 Decimal(math.log())로 하고 마지막에 math.exp()하는게 훨씬 빠름(0.4초)

 

from decimal import *
import math

n,m = map(int,input().split())

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

v1 = 0

for i in range(n):
    
    v1 += Decimal(A[i]).ln()

v2 = 0

for j in range(m):
    
    v2 += Decimal(B[j]).ln()

X = v1 - v2

print(int(X.exp()))