ABC 148 | E - Double Factorial

1 min読了の目安(約1100字TECH技術記事

問題

考えたこと

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

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

NNが奇数の場合は22が出てくる事がないので答えは00である。

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

気をつけるのは以下のように10=5×210 = 5 \times 255は1つだが、50=5×5×250 = 5 \times 5 \times 255は2つある。

偶数のみの数列なのでまずNN22で割る。
それを55で割ると少なくとも1つの55の約数を持っている数字の数を出すことができる。
次にNN25(=5×5)25( = 5 \times 5)で割ると2525の約数をもっている数字の数を出すことができる。
このようにしていけばNNまでの奇数の数列の中で約数が55の合計数を数えることができ、それが末尾の連続する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;
}

参考