[백준] 마지막 팩토리얼 수2 - Python

문제

출처

이해

입력

• 첫째 줄에 N이 주어진다. N은 최대 100자리인 자연수이다.
• N
  • 타입: 자연수
  • 범위: [1, 10^100-1]

출력

• N!의 0이 아닌 마지막 자리수

조건

없음

예시

입력
5

출력
2

접근

N!에서 0이 아닌 마지막 자리 숫자를 구한다는 것은 뒤에서부터 연속으로 등장하는 0을 제거하고 10의 나머지를 구하는 것과 같다.

예를 들면 다음과 같다.

3! = 6 이므로 답은 6
5! = 120 이므로 답은 2
10! = 3628800 이므로 답은 8

n의 0이 아닌 마지막 자리 숫자를 $L(n)$ 이라고 하자. 그럼 구해야 하는 답은 $L(N!)$이다. 그런데 $L(nm) = L(L(n)L(m))$임은 자명하다. 따라서 다음과 같은 점화식을 세울 수 있다

\[L(N!) = L(L(N)L((N-1)!))\]

이런 방식으로 계산하면 N!을 계산하는 대신 N-1번의 한 자리 수 곱셈으로 답을 구할 수 있다. 그러나 N은 최대 $10^{100}-1$ 이므로 최악의 경우 $10^{100}-2$번의 곱셈을 해야 한다. 이 방법은 아니라는 말이다.

우선 N!을 계산하지 않고 0을 떼는 방법을 생각해보자. 123400은 다음과 같이 표현할 수 있다.

\[123400 = 1234 \times 10^2\]

즉, 자연수 X에 대하여 뒤쪽으로 0이 n개 붙는 수는 다음과 같이 표현할 수 있다.

\[\begin{align} X &= P \times 10^n\\ &= P \times 2^n \times 5^n \end{align}\]

또한 다음이 성립한다는 것을 알 수 있다.

\[\begin{align} L(X) &= L(P\times 10^n)\\ &= L(P) \end{align}\]

N!의 경우에는 소인수분해했을 때 항상 2의 개수가 5의 개수보다 많다. 2로 나누어 떨어지는 수는 2번에 1번, 5로 나누어 떨어지는 수는 5번에 1번이기 때문이다. 따라서 N!의 경우 뒤쪽으로 0이 붙는 개수는 소인수분해했을 때 5의 개수라는 것을 알 수 있다.

위와 같은 N!과 L의 성질을 활용해보자.

N = 5A라고 하면 다음과 같이 5의 배수를 빼낼 수 있다.

\[\begin{align} N! &= 1 \times 2 \times 3 \times ... \times N \\ &= (5 \times 10 \times ... \times 5A) \times (1 \times 2 \times 3 \times 4) \times (6 \times 7 \times 8 \times 9) \\&\quad \times (11 \times 12 \times ...) \times ... \times ((5A - 4) \times (5A - 3) \times ... \times (5A - 1)) \end{align}\]

여기서 세 가지 패턴을 볼 수 있다.

#1 
(5 * 10 * ... * 5A)

#2
(1 * 2 * 3 * 4)
(11 * 12 * 13 * 14)
...

#3
(6 * 7 * 8 * 9)
(16 * 17 * 18 * 19)
...

#1은 자명하게 $5^A\times A!$이다.

#2의 n번째 항은 다음 집합의 모든 원소의 곱이다.

\[\{n \times 10 + a|a \in \{1,2,3,4\}\}\]

그런데 앞에서 나온 L의 성질에 따르면 다음이 성립한다.

\[L(n \times 10 + a) = L(a)\]

따라서 모든 항은 $L(L(1)L(2)L(3)L(4)) = 4$이다.

#3 역시 마찬가지로 모든 항은 $L(L(6)L(7)L(8)L(9)) = 4$이다.

따라서 다음이 성립한다.

\[\begin{align} L(N!) &= L((5A)!)\\ &= L(L(5^A \times A!) \times L(4) \times L(4) \times ...)\\ &= L(5^A \times A! \times 4^A)\\ &= L(10^A \times A! \times 2^A)\\ &= L(A! \times 2^A)\\ \end{align}\]

N = 5A일 때를 증명했으므로 N = 5A + B (A > 0, 0 < B < 5)일 때를 증명해보자.

\[\begin{align} L(N!) &= L((5A+B)!)\\ &= L((5A)! \times (5A+1) \times ... \times (5A+B))\\ &= L(L((5A)!) \times L((5A+1) \times ... \times (5A+B)))\\ &= L(L(A! \times 2^A) \times L((5A+1) \times ... \times (5A+B)))\\ \end{align}\]

이제 $L((5A+1) \times … \times (5A+B))$ 의 경우의 수만 계산하면 된다.

B = 1일 때,
L(5A+1) = 6

B = 2일 때,
L((5A+1) * (5A+2)) = 6 * 7 = 2

B = 3일 때,
L((5A+1) * (5A+2) * (5A+3)) = 2 * 8 = 6

B = 4일 때,
L((5A+1) * (5A+2) * (5A+3) * (5A+4)) = 6 * 9 = 4

6, 2, 6, 4는 불편하다. 다시 돌아와서 식을 보자.

\[L(N!) = L(L(A! \times 2^A) \times L((5A+1) \times ... \times (5A+B)))\]

A > 0이므로 $L(A! \times 2^A)$ 는 짝수이다. 그런데 임의의 짝수 K에 대하여 다음이 성립한다.

\[L(K \times 1) = L(K)\\ L(K \times 6) = L(K)\]

따라서 B = 1일 때의 값을 1과 6중 무엇으로 하든 $L(N!)$의 값은 동일하다.

1을 선택하면 경우의 수는,

B = 1일 때, 1
B = 2일 때, 2
B = 3일 때, 6
B = 4일 때, 4

이고 L(B!)과 같다.

그러므로

\[\begin{align} L(N!) &= L((5A+B)!)\\ &= L((5A)! \times (5A+1) \times ... \times (5A+B))\\ &= L(L((5A)!) \times L((5A+1) \times ... \times (5A+B)))\\ &= L(L(A! \times 2^A) \times L((5A+1) \times ... \times (5A+B)))\\ &= L(L(A! \times 2^A) \times L(B!))\\ &= L(A! \times 2^A \times B!)\ \end{align}\]

정리하면 다음과 같다.

\[\begin{align} L(N!) &= L(A! \times 2^A) &(N = 5A)\\ &= L(A! \times 2^A \times B!) &(N = 5A + B (A > 0, 0 < B < 5)) \end{align}\]

그런데 B = 0일때 (2)가 (1)이므로

\[L(N!) = L(L(A!) \times L(2^A) \times L(B!)) \quad (N = 5A + B (A \gt 0, 0 \le B \lt 5))\]

그런데 A = 0일때도 성립하므로

\[L(N!) = L(L(A!) \times L(2^A) \times L(B!)) \quad (N = 5A + B (A \ge 0, 0 \le B \lt 5))\]

따라서, $L(N!)$을 구하는 문제는 $L(A!)$, $L(2^A)$, $L(B!)$을 구하는 작은 문제로 쪼갤 수 있다.

$L(2^A)$는 4를 주기로 반복되고, $L(B!)$는 B < 5이므로 쉽게 구할 수 있다. $L(A!)$는 공식을 적용하여 쪼갤 수 있으므로 반복적으로 공식을 적용하면 결과적으로 쉽게 답을 구할 수 있다.

요약

$N=10^{100}-2$번의 곱셈을 통해 $L(N!)$을 구하는 대신, $L(N!)$을 $L((N//5)!)$로 표현하여 약 $k \times log_5N$번의 곱셈으로 답을 구한다.

구현

N = int(input())
ans = 1
fact = [1,1,2,6,4]

while N >= 5:
    A = N // 5
    B = N % 5
    ans *= fact[B] * (2 ** (A % 4))
    ans %= 10
    N = A
    
print(ans * fact[N] % 10)