[BOJ/2004] 조합 0의 개수

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

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

 

사용 알고리즘

- 

 

풀이

- 끝자리가 0이 되려면 2와 5가 필요

- 따라서 0이 몇 개인지 알아내려면, N!를 소인수 분해하여 2와 5의 개수중 작은 수의 개수가 0의 개수

- 2의 개수 = n / 2^1 + n / 2^2 + n / 2^3...

- 5의 개수 = n / 5^1 + n / 5^2 + n / 5^3...

 

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/2004.cpp

#include <cstdio>
#include <vector>
 
using namespace std;
 
int main(void) {
    long long n, m; scanf("%lld %lld", &n, &m);
    long long two = 0, five = 0;
    for (long long i = 2; i <= n; i *= 2) two += (n / i);
    for (long long i = 5; i <= n; i *= 5) five += (n / i);
    for (long long i = 2; i <= m; i *= 2) two -= (m / i);
    for (long long i = 5; i <= m; i *= 5) five -= (m / i);
    for (long long i = 2; i <= (n - m); i *= 2) two -= ((n - m )/ i);
    for (long long i = 5; i <= (n - m); i *= 5) five -= ((n - m) / i);
    printf("%lld\n", (five < two) ? five : two);
    return 0;
}