[BJ / 2004] 조합 0의 개수

문제

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

입력

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

출력

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

예시

풀이

조합의 공식은 n! / m! (n-m)! 이다.
n!의 0의 개수에서 m!의 0의 개수와 (n-m)!의 0의 개수를 빼주면 되는데,
팩토리얼의 경우 2의 배수의 개수가 5보다 많지만 조합은 정확하게 알 수 없기 때문에 모두 구해줘야 한다.
그래서 모두 구한 다음 2의 배수의 개수와 5의 개수 중 적은 수를 리턴하면 된다.

const readline = require('readline');

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = '';
rl.on('line', (line) => {
  input = line;
});

rl.on('close', () => {
  console.log(solution(input.split(' ').map((el) => parseInt(el))));
});

function solution(nums) {
  const [n_1, n_2] = getNumber(nums[0]);
  const [m_1, m_2] = getNumber(nums[1]);
  const [nm_1, nm_2] = getNumber(nums[0] - nums[1]);

  const [re_1, re_2] = [n_1 - m_1 - nm_1, n_2 - m_2 - nm_2];

  return Math.min.apply(null, [re_1, re_2]);
}

function getNumber(n) {
  let five = 0;
  let two = 0;

  for (let i = 2; i <= n; i *= 2) {
    two += parseInt(n / i);
  }

  for (let i = 5; i <= n; i *= 5) {
    five += parseInt(n / i);
  }
  return [two, five];
}