[수학 3 단계] 백준 2004번 조합 0의 개수 oo

문제

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

입력

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

출력

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

n!에서 곱해지는 5의 수를 찾기.

n을 5로 나누면 5의 배수 개수가 구해짐

n을 25로 나누면 25의 배수 개수가 구해짐 

만약 25를 생각했을 때 

25/5 는 5로 5,10,15,20,25 5개

25/25는 1로 25 1개

즉 5가 6번 곱해짐.

125는 25/125가 0으로 몫이 1보다 작아지므로 생략

 

 

25개 두번 세지지만 두번째 25에서는 1만 더해짐 즉 5가 곱해지면서 추가되는 5또한 1개씩 증가되므로 상관 없음.

#include <iostream>
#include <vector>
#include<queue>
#include <string>
#include<cmath>
#include<string.h>
#include <map>
#include<algorithm>
using namespace std;

long long int i;
int n, r;
int five = 0, two = 0;

int fiveCount(int num) {
    int count = 0;

    for (i = 5; num / i >= 1; i *= 5)
        count += num / i;

    return count;
}

int twoCount(int num) {
    int count = 0;

    for (i = 2; num / i >= 1; i *= 2)
        count += num / i;

    return count;
}

int main() {

    cin >> n >> r;


    five += fiveCount(n);
    if (r != 0)five -= fiveCount(r);
    if (n != r)five -= fiveCount(n - r);

    two += twoCount(n);
    if (r != 0)two -= twoCount(r);
    if (n != r)two -= twoCount(n - r);

    printf("%d\n", min(two, five));

    return 0;
}