階乗

解説/アルゴリズム

$6 \times 5 \times 4 \times 3 \times 2 \times 1$ のように 1 から n までの整数を全て掛け合わせたものをnの階乗といい、 n! と表す。

コード例

function fact(n: number): number {
  n = Math.floor(n);

  if (n <= 0) {
    return 1;
  }

  let ret = n;
  while (--n) {
    ret *= n;
  }

  return ret;
}

console.log(fact(0)); // 1
console.log(fact(1)); // 1
console.log(fact(2)); // 2
console.log(fact(3)); // 6
console.log(fact(4)); // 24
console.log(fact(5)); // 120

階乗の末尾の 0 の数

function trailingZeroes(n: number): number {
  let ret = 0;

  while (n > 0) {
    n = Math.floor(n / 5);
    ret += n;
  }

  return ret;
}

console.log(trailingZeroes(1)); // 0
console.log(trailingZeroes(5)); // 1
console.log(trailingZeroes(10)); // 2
console.log(trailingZeroes(100)); // 24
console.log(trailingZeroes(999)); // 246
console.log(trailingZeroes(1000)); // 249

n! の末尾に 0 があると、 10 で割り切れるので、素因数分解した際、 2 と 5 のセットが何回出てくるかが、末尾の 0 の数になる。

2 に比べて 5 の数のほうが少ないので、値が 0 になるまで 5 で割り続け、商の合計を求める。

• 1 回目のループは、 $1,2,3,...,n$ の中で、 5 で 1 回以上割り切れる数を計算 (n / 5)
• 2 回目のループは、 $1,2,3,...,n$ の中で、 5 で 2 回以上割り切れる数を計算 (n / 25)
• 3 回目のループは、 $1,2,3,...,n$ の中で、 5 で 3 回以上割り切れる数を計算 (n / 125)

二重階乗の末尾の 0 の数

function dfTrailingZeroes(n: number): number {
  let ret = 0;

  if (n % 2 == 1) {
    return 0;
  }

  n = Math.floor(n / 2);

  while (n > 0) {
    n = Math.floor(n / 5);
    ret += n;
  }

  return ret;
}

n が奇数の場合、 2 が出てくることがないので、 2 と 5 のペアを作ることができない。なので末尾の 0 の数は 0 となる。

n が偶数の場合、たとえば $n = 10$ のとき、

• $10 \times 8 \times 6 \times 4 \times 2 = 2^5(5 \times 4 \times 3 \times 2 \times 1) = 2^5(5!)$

となるので、結局は $(\frac{n}{2})!$ の末尾の 0 の数を数えることになる。

関連記事

• 順列
• 組み合わせ