[BaekJoon][1676] 팩토리얼 0의 개수

BAEKJOON ONLINE JUDGE

 

1676 팩토리얼 0의 개수

 

https://www.acmicpc.net/problem/1676

 

 

이 문제는 팩토리얼 계산 결과값에서 0의 개수를 찾는 것이 아니다.

팩토리얼이 결국 곱으로 이루어진 연산이기 때문에 그리고 0은 10을 얼마나 곱하느냐에 따라 결정이 되기 때문에 팩토리얼을 이루는 수의 소인수 중에서 2와 5의 개수에 따라 결정이 된다.

 

정리를 하면

 

N! = 1 x 2 x 3 x ... x N

ex) 10! = 3628800

10! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10

10! = 1 x 2 x 3 x (2 x 2) x 5 x (2 x 3) x 7 x (2 x 2 x 2) x (3 x 3) x (2 x 5)

10! = 2^8 x 3^4 x 5^2 x 7

10! = (2^2 x 5^2) x 2^6 x 3^4 x 7

10! = 10^2 x 2^6 x 3^4 x 7

2와 5의 개수 중 작은 값이 10의 개수 (0의 개수)가 된다.

 

따라서 0의 개수를 구할 때에는 2의 개수와 5의 개수를 구하고 그 중 작은 값이 결과값이 된다.

 

for (i = 2; i <= n; i++) {
        temp = i;
        while (!(temp % 5)) {
            five++;
            temp /= 5;
        }
        while (!(temp % 2)) {
            two++;
            temp /= 2;
        }
    }
 
    printf("%d\n", (two < five) ? two : five);

하지만 위 구현 알고리즘은 O(n + a)로 1억 이상의 수가 들어오면 time limit이 나온다.

 

위 방법보다 효율적인 방법을 찾아보자.

 

 

예를 들어 100!의 경우

 

 

 

 

 

 

 

 

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	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

 

 

 

 

 

 

 

 

위 테이블에 있는 수들이 팩토리얼을 이루는 수들이다. (곱해질 수들)

 

 

이 중 5를 인수로 가지고 있는 수들을 찾아보자.

 

 

 

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	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

 

 

 

색상이 표시된 수들이 5를 인수로 가지고 있는 수들이다.

이는 총 20개  -> 100 / 5 개이다.

 

그 중 25는 5를 인수로 하나를 더 가지고 있다. ( 25 = 5 x 5 )

 

 

 

 

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	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

 

 

25의 배수들은 5를 2개씩 가지고 있기 때문에 개수를 더 세어주어야 한다.

 

총 4개  -> 100 / 25

 

따라서 100!의 0의 개수는 20 + 4 = 24개이다.

( !100 = 933262154439441526816992388562667 004907159682643816214685929638952 175999932299156089414639761565182 862536979208272237582511852109168 64000000000000000000000000)

 

 

2도 마찬가지로 계산하여 개수를 구할 수 있다.

 

 

최종적으로 인수 2의 개수와 5의 개수를 구하여 둘 중 작은 값이 최종 0의 개수이다.

 

* 팩토리얼 0의 개수의 경우 5의 개수 2의 개수보다 항상 작으므로 5의 개수만 구해도 된다.