けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 148 E - Double Factorial (500 点)

じゅぴろ君が「これは中受典型」と言いそうな雰囲気がありますね。

問題へのリンク

問題概要

 0 以上の整数  N が与えられる。

 N \times (N-2) \times (N-4) \times \dots

を計算した値において、末尾に何個の 0 がつくのかを求めよ。

制約

  •  0 \le N \le 10^{18}

考えたこと

これとよく似た形で、たとえば


 1333! の末尾に 0 が何個つくか?


という感じの問題は、中学受験でも高校受験でも大学受験でもよく見る問題ではある。具体的な解法も割と明快で、 1333!

  •  1333! = 2^{a} \times 5^{b} \times \dots

素因数分解したときに、 c = \min(a, b) 個の分だけ「2 と 5 のペアを作って 10 を作る」ことができる。よって、  1333! の末尾には  c 個の 0 がつくことになる。

そして、割と明らかに  a \ge b となっていることがわかる。よって  b を求めればよい。 b を求めるには、以下のように考えればよい。

  •  1, 2, 3, \dots, 1333 のうち、5 で 1 回以上割れる数は、 5, 10, 15, \dots の 1333 / 5 = 266 個
  •  1, 2, 3, \dots, 1333 のうち、5 で 2 回以上割れる数は、 25, 50, 75, \dots の 1333 / 25 = 53 個
  •  1, 2, 3, \dots, 1333 のうち、5 で 3 回以上割れる数は、 125, 250, 375, \dots の 1333 / 125 = 10 個
  •  1, 2, 3, \dots, 1333 のうち、5 で 4 回以上割れる数は、 625, 1250 の 1333 / 625 = 2 個

これらを合計して、266 + 53 + 10 + 2 = 331 個となる。

より具体的に

より具体的には、 N! が 5 で割れる回数  b は、

long long b = 0;
while (N) {
    b += N / 5;
    N /= 5;
}

という感じで求めることができる。

今回の問題の場合

今回の問題は、 N! ではなく、

  •  N \times (N-2) \times \dots

なので、微妙に違う。でも実はほとんど一緒。

N が奇数のとき

たとえば  N = 9 のとき、

  •  9 \times 7 \times 5 \times 3 \times 1

となる。ここに偶数はない。2 で割れる数がないと、どんなに 5 が大量に供給されたとしても 10 を作ることができない。よって、ダメ。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^{4} (5!)

となる。つまり、結局、 (\frac{N}{2})! の末尾に 10 が何個あるかを求める問題に帰着された。

まとめ

  •  N が奇数のとき、0 個
  •  N が偶数のとき、 (\frac{N}{2})! が何回 5 で割り切れるか

計算量は  O(\log{N})

#include <iostream>
using namespace std;

long long solve(long long N) {
    if (N % 2 == 1) return 0;

    long long res = 0;
    N /= 2;
    while (N) {
        res += N / 5;
        N /= 5;
    }
    return res;
}

int main() {
    long long N; cin >> N;
    cout << solve(N) << endl;
}