문제

---

$n \choose m$의 끝자리 $0$ 의 개수를 출력하는 프로그램을 작성하시오.

입력

---

첫째 줄에 정수 $n$, $m$ ( $0 \le m \le n \le 2,000,000,000$, $n \ne 0$) 이 들어온다.

출력

---

첫째 줄에 $n \choose m$ 의 끝자리 $0$ 의 개수를 출력한다.

풀이

---

https://velog.io/@sw801733/C-%EB%B0%B1%EC%A4%80-1676%EB%B2%88-%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC-0%EC%9D%98-%EA%B0%9C%EC%88%98

$_nC_r = n! / (n -r)! * r!$

전에 풀었던 팩토리얼 0의 개수 처럼 만약 nCr 로 조합의 공식을 문제를 해결하려고 할 경우
숫자가 엄청나게 커져버리므로 사용할 수 없으며 끝의 0의 개수만 구하면 되기 때문에

전체 수를 구할 필요는 없다.

즉, 2개의 숫자의 곱으로 10이 나오는 경우에 전체 숫자의 0 이 추가되는 것이기 때문에

조합의 공식 안에 2 와 5의 연산 이 몇 번 존재하는지를 확인하면 된다.

단, 조합의 공식으로 인해 만약 $_5C_1$ 이나 $_5C_4$ 의 경우 분모는 5! 임에도 분자가 4! 이므로


5 는 1번, 2 는 0번 등장하게 된다.

이와 같이 항상 5 에 맞게 2 가 존재하지 않고 2 에 맞게 5 가 존재하지 않으므로 둘 중 개수가 적은 경우를 구하면 된다.

5 의 개수는 주어진 값에서 5의 제곱 개수를 구하고
2 의 개수는 주어진 값에서 2의 제곱 개수를 구하면 된다.

코드

---

#include <iostream>
#include <math.h>


using namespace std;

long long divide_a(long long n, int a)
{
    long long cnt = 0;
    for (long long i = 1; i <= n; i *= a)
    {
        cnt += (n / i);
    }
    return cnt;
}

int main()
{
    long long n, m;
    cin >> n >> m;

    long long cnt1 = divide_a(n, 2) - divide_a(n - m, 2) - divide_a(m, 2);
    long long cnt2 = divide_a(n, 5) - divide_a(n - m, 5) - divide_a(m, 5);

    cout << min(cnt1, cnt2);

    return 0;
}

리뷰

사실 2 x 5 = 10 으로 0이 추가 된다는 것을 떠올리는 데 생각보다 많은 시간이 걸렸다....
역시 정리도 중요하지만 복습도 엄청 중요!!