AtCoder Beginner Contest 148 - E - Double Factorial
数学問題はググったら考え方でること多いからちゃんとググろう...
https://gyazo.com/c01f204873f9d09f0b1a0d0e674c94e0
考え方
この問題は全く手が出ませんでした。10の倍数、5の倍数とかを考えてた..
終わった後にtwitter見てたらググれば考え方出てくるというのがあったのでググった
これがかなりわかりやすかった
上記リンクでは、$ N!でいくつ0が続くかという問題。
いくつ0が続くかは作れる10の個数(つまり2と5のセットがいくつ出てくるか, 10を素因数分解して2と5が何セットできるかという問題になる)
この時、明らかに2の方が多いと言えるので、5の数を数えればいい
最終的には5で何回割れるかという問題になる
元の問題に戻ると、階乗ではないので、これがそのまま使えないと見える。
少し$ f(x)を分解していく、入力例1が分かりやすい
https://gyazo.com/54c51d56f7dbf2bb98a80c177d45a711
$ f(12)は$ 12 \times 10 \times 8 \times 6 \times 4 \times 2になる
式を分解していく
a. $ (6 \times 2) \times (5 \times 2) \times (4 \times 2) \times (3 \times 2) \times (2 \times 2) \times (1 \times 2)
b. $ 2^{6} \times (6 \times 5 \times 4 \times 3 \times 2 \times 1)
c. $ 2^{6} \times 6!
一般式に直すと -> $ 2^{ \frac{N}{2} } \times \frac{N}{2}!
階乗の形に直せた、前のこの時、明らかに2の方が多いと言えるので、5の数を数えればいい でも書いた通り, 明らかに2が多くなることは想定できるので、左の$ 2^{ \frac{N}{2} } は無視して問題ない$ \frac{N}{2}! だけを考えればいい
あとは、上記リンクの通り$ \frac{N}{2}を何回Nで割れるかを計算すれば良い
また、Nが奇数の場合は2の倍数が1度も出ないので0と考えて良い
提出したコード
code: E.cpp
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) #define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i) #define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i) #define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }
int main() {
ll n; cin >> n;
if(n%2 == 1) {
cout << 0 << endl;
return 0;
} else {
ll ans = 0;
ll tmp = n/2;
while(tmp) {
tmp /= 5;
ans += tmp;
}
cout << ans << endl;
}
return 0;
}
解説動画を見て
https://www.youtube.com/watch?v=F2p_e6iKxnk
こういう1つ飛ばしの階乗を$ N!!..二重階乗というらしい