[c++]백준 2004 - 조합 0의 개수(수학, 빠르게 지수 구하기)

0. [c++] 백준

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

1. 풀이

오래간만에 좋은 문제를 접했다.

이 문제의 답은 조합을 하고 구한 결과의 min(2의 지수의 개수, 5의 지수의 개수)이다.

따라서 답을 구하기 위해 지수의 개수를 구해야 하는데, 일반적인 반복문을 활용해 지수를 구하려고 하면 입력의 크기가 커서 시간초과를 하게된다.

이를 해결하기 위해 다른 방법이 필요했는데, N!에서 k의 지수의 개수를 구하는 방법이 존재하였다.

N을 k^i로 계속 나누어주는 것이다.

이러면 N!에 포함된 k의 지수 개수를 구할 수 있게 된다.

이렇게 할 수 있는 이유는 k가 여러번 곱해진 수와 같은 경우, 그 횟수만큼 나누어 떨어지기에 점층적으로 합산이 되는 것이다.

ex) N은 25, k는 2인 경우

25 / 2 = 12 (2, 4, 6, ... , 24)

25 / 4 = 6 (4, 8, 12, 16, 20, 24)

25 / 8 = 3 (8, 16, 24)

25 / 16 = 1 (16)

따라서, N!에 포함된 2의 지수 개수는 22개이다.

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 35 36 37 38 39 40 41 42 43 44

#include<iostream> #include<algorithm> #include<vector>   using namespace std;   typedef unsigned long long ull;   int main() {     ios_base::sync_with_stdio(0);     cin.tie(0);       ull N, M;     cin >> N >> M;       ull count[2] = { 0 };          //2의 지수의 개수를 구하자.     for (ull i = 2; i <= N; i *= 2) {         count[0] += N / i;     }     for (ull i = 2; i <= (N - M); i *= 2) {         count[0] -= (N - M) / i;     }       for (ull i = 2; i <= M; i *= 2) {         count[0] -= M / i;     }       //5의 지수의 개수를 구하자.     for (ull i = 5; i <= N; i *= 5) {         count[1] += N / i;     }     for (ull i = 5; i <= (N - M); i *= 5) {         count[1] -= (N - M) / i;     }     for (ull i = 5; i <= M; i *= 5) {         count[1] -= M / i;     }       cout << min(count[0], count[1]);       return 0; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!