N! 0의 개수

#include <iostream>
#include <algorithm>
#include <vector>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

using namespace std;
int main() {
	//15 10 5 
	// 0의 개수 2*5의 쌍의 개수 -> 5의 개수 
	// 5 10 15 20 25 30 35 40 45 50
	// 1 1 1 1 2 1 1 1 1 2
	// 
	
	int n;
	scanf("%d",&n);
	
	int cnt = 0;
	for(int i = 1; i<=n; i++){
		int tmp = i;
		while(tmp%5==0){
			cnt++;
			tmp /= 5;
		}
		
		
	}
	
	printf("%d",cnt);
	
	return 0;
}

0의 개수는 10이 얼마나 곱해졌나를 찾으면 된다.

10이 얼마나 곱해졌냐는 2*5가 얼마나 있나를 찾으면된다.

팩토리얼에서 2의개수가 5의개수 보다 많으므로

5의 개수가 몇개 있는지 알면

N!에 0이 몇개 있는지 알 수 있다.

 

 

 

항상 2의 개수가 5의 개수 보다 많은 지 확인

#include <iostream>
#include <algorithm>
#include <vector>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

using namespace std;
int main() {
	//15 10 5 
	// 0의 개수 2*5의 쌍의 개수 -> 5의 개수 
	// 5 10 15 20 25 30 35 40 45 50
	// 1 1 1 1 2 1 1 1 1 2
	// 
	
	for(int n=1; n<100; n++){
		int cnt = 0;
		int cnt2 = 0;
		for(int i = 1; i<=n; i++){
			int tmp = i;
			int tmp2 = i;
			while(tmp%5==0){
				cnt++;
				tmp /= 5;
			}
			while(tmp2%2==0){
				cnt2++;
				tmp2 /= 2;
			}
		}
			printf("%d에서 약수의 개수 2: %d, 5: %d\n",n, cnt2, cnt);
		}
	

		return 0;
}

 

결과

1에서 약수의 개수 2: 0, 5: 0
2에서 약수의 개수 2: 1, 5: 0
3에서 약수의 개수 2: 1, 5: 0
4에서 약수의 개수 2: 3, 5: 0
5에서 약수의 개수 2: 3, 5: 1
6에서 약수의 개수 2: 4, 5: 1
7에서 약수의 개수 2: 4, 5: 1
8에서 약수의 개수 2: 7, 5: 1
9에서 약수의 개수 2: 7, 5: 1
10에서 약수의 개수 2: 8, 5: 2
11에서 약수의 개수 2: 8, 5: 2
12에서 약수의 개수 2: 10, 5: 2
13에서 약수의 개수 2: 10, 5: 2
14에서 약수의 개수 2: 11, 5: 2
15에서 약수의 개수 2: 11, 5: 3
16에서 약수의 개수 2: 15, 5: 3
17에서 약수의 개수 2: 15, 5: 3
18에서 약수의 개수 2: 16, 5: 3
19에서 약수의 개수 2: 16, 5: 3
20에서 약수의 개수 2: 18, 5: 4
21에서 약수의 개수 2: 18, 5: 4
22에서 약수의 개수 2: 19, 5: 4
23에서 약수의 개수 2: 19, 5: 4
24에서 약수의 개수 2: 22, 5: 4
25에서 약수의 개수 2: 22, 5: 6
26에서 약수의 개수 2: 23, 5: 6
27에서 약수의 개수 2: 23, 5: 6
28에서 약수의 개수 2: 25, 5: 6
29에서 약수의 개수 2: 25, 5: 6
30에서 약수의 개수 2: 26, 5: 7
31에서 약수의 개수 2: 26, 5: 7
32에서 약수의 개수 2: 31, 5: 7
33에서 약수의 개수 2: 31, 5: 7
34에서 약수의 개수 2: 32, 5: 7
35에서 약수의 개수 2: 32, 5: 8
36에서 약수의 개수 2: 34, 5: 8
37에서 약수의 개수 2: 34, 5: 8
38에서 약수의 개수 2: 35, 5: 8
39에서 약수의 개수 2: 35, 5: 8
40에서 약수의 개수 2: 38, 5: 9
41에서 약수의 개수 2: 38, 5: 9
42에서 약수의 개수 2: 39, 5: 9
43에서 약수의 개수 2: 39, 5: 9
44에서 약수의 개수 2: 41, 5: 9
45에서 약수의 개수 2: 41, 5: 10
46에서 약수의 개수 2: 42, 5: 10
47에서 약수의 개수 2: 42, 5: 10
48에서 약수의 개수 2: 46, 5: 10
49에서 약수의 개수 2: 46, 5: 10
50에서 약수의 개수 2: 47, 5: 12
51에서 약수의 개수 2: 47, 5: 12
52에서 약수의 개수 2: 49, 5: 12
53에서 약수의 개수 2: 49, 5: 12
54에서 약수의 개수 2: 50, 5: 12
55에서 약수의 개수 2: 50, 5: 13
56에서 약수의 개수 2: 53, 5: 13
57에서 약수의 개수 2: 53, 5: 13
58에서 약수의 개수 2: 54, 5: 13
59에서 약수의 개수 2: 54, 5: 13
60에서 약수의 개수 2: 56, 5: 14
61에서 약수의 개수 2: 56, 5: 14
62에서 약수의 개수 2: 57, 5: 14
63에서 약수의 개수 2: 57, 5: 14
64에서 약수의 개수 2: 63, 5: 14
65에서 약수의 개수 2: 63, 5: 15
66에서 약수의 개수 2: 64, 5: 15
67에서 약수의 개수 2: 64, 5: 15
68에서 약수의 개수 2: 66, 5: 15
69에서 약수의 개수 2: 66, 5: 15
70에서 약수의 개수 2: 67, 5: 16
71에서 약수의 개수 2: 67, 5: 16
72에서 약수의 개수 2: 70, 5: 16
73에서 약수의 개수 2: 70, 5: 16
74에서 약수의 개수 2: 71, 5: 16
75에서 약수의 개수 2: 71, 5: 18
76에서 약수의 개수 2: 73, 5: 18
77에서 약수의 개수 2: 73, 5: 18
78에서 약수의 개수 2: 74, 5: 18
79에서 약수의 개수 2: 74, 5: 18
80에서 약수의 개수 2: 78, 5: 19
81에서 약수의 개수 2: 78, 5: 19
82에서 약수의 개수 2: 79, 5: 19
83에서 약수의 개수 2: 79, 5: 19
84에서 약수의 개수 2: 81, 5: 19
85에서 약수의 개수 2: 81, 5: 20
86에서 약수의 개수 2: 82, 5: 20
87에서 약수의 개수 2: 82, 5: 20
88에서 약수의 개수 2: 85, 5: 20
89에서 약수의 개수 2: 85, 5: 20
90에서 약수의 개수 2: 86, 5: 21
91에서 약수의 개수 2: 86, 5: 21
92에서 약수의 개수 2: 88, 5: 21
93에서 약수의 개수 2: 88, 5: 21
94에서 약수의 개수 2: 89, 5: 21
95에서 약수의 개수 2: 89, 5: 22
96에서 약수의 개수 2: 94, 5: 22
97에서 약수의 개수 2: 94, 5: 22
98에서 약수의 개수 2: 95, 5: 22
99에서 약수의 개수 2: 95, 5: 22