🐙

ABC 148 | E - Double Factorial

2020/11/27に公開

競プロ

約数

数列

tech

問題

考えたこと

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

上記より $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;
}

ABC 148 | E - Double Factorial

問題

考えたこと

コード

参考

Discussion