문제
풀이
0의 개수를 구하는 문제는 2와 5의 문제 중 갯수가 작은 수를 찾는 문제이다. 이 문제 역시도 같은 문제이다. combination 공식에 따라 분자의 팩토리얼에서 나온 2와 5의 개수들을 분모의 팩토리얼에서 나온 2와 5의 개수들을 빼서 2와 5 중 개수가 작은 수를 출력하면 되는 문제이다. 기존 방법으로 O(N^2)으로 돌렸더니 시간 초과로 실패하였다. 새로운 O(N)으로 2와 5의 개수를 푸는 코드를 적용하였다. 2와 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
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
long long fivecont_a = 0;
long long fivecont_b = 0;
long long fivecont_c = 0;
long long twocont_a = 0;
long long twocont_b = 0;
long long twocont_c = 0;
long long N, M;
scanf("%lld %lld", &N, &M);
for(long long i = 5; i<=N; i*=5){
fivecont_a = fivecont_a + N/i;
}
for(long long j = 5; j<=M; j*=5){
fivecont_b = fivecont_b + M/j;
}
for(long long k = 5; k<=(N-M); k*=5){
fivecont_c = fivecont_c + (N-M)/k;
}
for(long long i = 2; i<=N; i*=2){
twocont_a = twocont_a + N/i;
}
for(long long j = 2; j<=M; j*=2){
twocont_b = twocont_b + M/j;
}
for(long long k = 2; k<=(N-M); k*=2){
twocont_c = twocont_c + (N-M)/k;
}
printf("%lld\n", min(fivecont_a-fivecont_b-fivecont_c, twocont_a-twocont_b-twocont_c));
}
