ABC 148 | E - Double Factorial

問題

https://atcoder.jp/contests/abc148/tasks/abc148_e

考えたこと

問題文の定義より以下のようになる。

上記より$N$が偶数のときは$N$までの偶数の掛け合わせが$f(N)$の答えとなり、奇数のときは$N$までの奇数の掛け合わせが$f(N)$の答えとなる。
末尾の連続する0を数えるには$f(N)$に$10=5\times2$がいつくあるか数えればいい。

$N$が奇数の場合は$2$が出てくる事がないので答えは$0$である。

$N$が偶数のときはNまでの偶数の数列の中で各数の約数の中で$5$と$2$の数を数えればいい。$2$の約数の数は明らかに$5$より多いので$5$の数のみを数えればいい。

気をつけるのは以下のように$10 = 5 \times 2$で$5$は1つだが、$50 = 5 \times 5 \times 2$と$5$は2つある。

偶数のみの数列なのでまず$N$を$2$で割る。
それを$5$で割ると少なくとも1つの$5$の約数を持っている数字の数を出すことができる。
次に$N$を$25( = 5 \times 5)$で割ると$25$の約数をもっている数字の数を出すことができる。
このようにしていけば$N$までの奇数の数列の中で約数が$5$の合計数を数えることができ、それが末尾の連続する0の個数である。

コード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;

int main() {
  ll n;
  cin >> n;
  if (n % 2 == 1) {
    cout << 0 << endl;
    return 0;
  }
  ll ans = 0;
  n /= 2;
  while (n > 0) {
    ll v = n / 5;
    ans += v;
    n /= 5;
  }
  cout << ans << endl;
}

参考

https://atcoder.jp/contests/abc148/tasks/abc148_e/editorial