ABC148 E - Double Factorial

atcoder.jp

相変わらずここでレコメンドされたやつを解いてるわけだが、 教育的に良い問題だと思ったので理解のために記事にすることにした。 https://kenkoooo.com/atcoder#/user/sd08013

1個飛ばしの整数の階乗的なものの末尾の0の個数を求めるというシンプルなもの。 f(10)なら10*8*6*4*2となる。

初手の方針

nの最大値が10¹⁸で再帰的にやるのは不可能&&愚直にdpテーブルみたいなものを作るのもメモリ制限で難しそうだなと思った。 ということでf(n)を何かしらの漸化式で表して再帰的にf(10)やf(100)の値から求めようとした。 例えばf(100)だったら100*98*...*10*8...*1中に10の倍数を数え上げれないかなと思って進めた。 f(100) = 2 + 9 * f(10) f(1000) = 3 * 9 * f(100) ... しかしf(10^18)まで求めたところ例3の結果と一致せず頓挫。

f(100)の例だと20*50のようなパターンがごっそり抜け落ちている。

正答

素因数分解するというのが正しい方針。 どうも数Aでやっているらしいが10年以上前の話なのでまったくこの発想には至らなかった。

よく見るのが

0!に含まれる素因数2の数を求めよ

みたいな問題

この問題に帰着させると

となって(n/2)!中に含まれる素因数5の数を求めよという問題に言い換えられる。

肝心の階乗に含まれる素数の数の求め方は 例えば10!中の素因数2の場合(2の倍数の数)+(2²の倍数の数)+(2³の倍数の数)...となり5+2+1=8となる。

一般化するとn!中に含まれる素因数pの数は となる。

ということで提出したのが以下のコード

Submission #9291738 - AtCoder Beginner Contest 148

本日の気付き

• powやfloorなどテンプレートの型にlong long が存在しないものがありそのまま利用すると誤差がでるので利用する際は注意する

using pow in long long - C++ Forum

• 1段階深い考察を意識したい

愚直にをコードに落とすと以下のようになるが

while (n/P_POW(5,c)) {
      res += n/P_POW(5,c);
      c++;
    }
    return res;

更に簡潔にこう書ける。

while (N) {
        res += N / 5;
        N /= 5;
    }
    return res;