자연수 n을 입력받고, n!의 계산 결과 중 마지막에 붙은 연속된 0의 개수와 연속된 0 바로 앞에 나오는 숫자를 구하라.

[실행 예] input n: 15 output: 3 8

[설명] 15!은 1307674368000이므로, 마지막에 연속된 0은 3개이고, 바로 앞의 숫자는 8이다.

• 조건 *

n의 범위는 1 이상, 10000 이하입니다. 테스트 입력은 다음과 같습니다. 20! = 2432902008176640000 30! = 265252859812191058636308480000000 40! = 815915283247897734345611269596115894272000000000 50! = 30414093201713378043612608166064768844377641568960512000000000000 100! = 93326215443944152681699238856266700490715968264381621468592963 8952175999932299156089414639761565182862536979208272237582511852 10916864000000000000000000000000 프로그래밍 언어에서 제공하는 자릿수 제한 없는 곱셈을 이용하거나, 이런 형태의 곱셈 함수를 직접 구현해도 답을 얻을 수 있지만, 문제의 의도와는 다릅니다. 정답 검토의 편의를 위해 블로그 포스팅에 2012!와 10000!의 결과를 남겨주세요. (심화 문제) 연속된 0 앞에 나오는 여러 숫자를 구하는 것도 가능하니, 심심하신 분은 도전해보세요. ^^

1. Simple Approach

아주 간단하게 생각해서 굳이 다 계산할 필요없이 마지막 원하는 자릿수만 남겨보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# simple.factorial.coffee
n = 1
k = 3
N = 2012
digit = 1

digit = digit * 10 while k-- isnt 0
zero = 0
for i in [1..N]
    n = n*i
    while n % 10 is 0
        n = n/10
        zero++

    n = n%digit
    console.log "#{i}! = ...#{n}*10^#{zero}"

k는 원하는 자리 수. 3자리만 끊어서 보도록 했다. 결과는

1
2

2012! = ...928*10^501
[Finished in 0.7s]

2. without 2, 5

0의 개수를 결정하는 2와 5는 따로 처리한다. N까지 숫자를 모두 곱해서 소인수분해를 하면 2가 5보다 항상 클까? non-zero digit of factorial로 검색하니 바로 맨 위에 이 포스팅이 나왔다. Approach1은 누구나 생각할 수 있고 2에 대한 수학적인 증명이 있어야할텐데 그건 차차 생각해보도록 하고 일단 구현해보도록 했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#reduce2and5.factorial.coffee
n = 1
k = 3
N = 2012

digit = 1
while k-- isnt 0
    digit = digit * 10

zero = 0
n2 = 0

for i in [1..N]
    j = i

    while j % 10 is 0
        j /= 10
        zero++

    while j % 2 is 0
        j /= 2
        n2++

    while j % 5 is 0
        j /= 5
        n2--
        console.error i if n2 is 0
        zero++

    n = n*j % digit

while n2-- isnt 0
    n = n*2 % digit
console.log "#{N}! = ...#{n}*10^#{zero}"

결과는

1
2

2012! = ...928*10^501
[Finished in 0.2s]

확실하게 줄었다. Approach3과 4에 대해서는 더 생각해봐야겠는데 일단 카페 마감 시간이라 나가도록 하겠다.