백준 2004 조합 0의 개수

작성일 | In |

Problem : 조합 0의 개수

유형 : 수학

문제 설명

nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오.

예제 입력

첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다.

1
25 12

예제 출력

첫째 줄에 0의 개수를 출력한다.

1
2

해결 전략

끝자리에 0이 나오는 수는, 소인수 분해 했을때 2 x 5가 등장한 횟수를 구하면된다.
n C m 은 (n!) / ((n-m)!) / (m!) 로 구할 수 있다.

2 x 5 의 등장 횟수는 2와 5중에 가장 적게 등장한 숫자의 빈도 수를 구하면된다.

주의할 점

  • 25 의 경우 5가 두번 등장 한다.
  • 4 의 경우 2가 세번 등장 한다.
  • 이런식으로 제곱수의 경우에 주의

풀이

(n!) , (n-m)! , (m!) 에서 2와 5의 등장 횟수를 구한다.

  • n! 에서 등장한 2,5의 개수에서 나머지에서 등장한 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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n, m;

int five_counter(int k) {
    int cnt = 0;
    for (ll i = 5; i <= k; i *= 5) {
        cnt += k / i;
    }
    return cnt;
}

int two_counter(int k) {
    int cnt = 0;
    for (ll i = 2; i <= k; i *= 2) {
        cnt += k / i;
    }
    return cnt;
}

int solve() {
    int two = two_counter(n) - two_counter(n - m) - two_counter(m);
    int five = five_counter(n) - five_counter(n - m) - five_counter(m);
    return min(two, five);
}
void input() {
    cin >> n >> m;
    cout << solve();
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    cin.tie(NULL);  cout.tie(NULL);

    input();

    return 0;
}

피드백

없음