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

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

AtCoder ABC 148 E - Double Factorial (緑色, 500 点)

AtCoder AtCoder500点 ABC-E 整数問題 N進法 pで何回割れるか 緑色diff ルジャンドルの定理

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

問題へのリンク

問題概要

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^{5} (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;
}