POH7「プログラミングで彼女をつくる」「水着」ゲットチャレンジ！
POH8の問題を全部解いてしまったので、昔のにも挑戦してみます。
問題
階乗とは数学の演算の一つで、N の階乗をN! と書きます。N が自然数であるとき、階乗は次のように計算できます。
N! = N * (N - 1) * ... * 2 * 1
N が与えられたとき、N! のすべての桁の代わりに、N! の最下位桁から続く0 をすべて除いた値の下位9桁を求めるプログラムを作成してください。
9桁ではあるが先頭が0であるような場合は先頭の0を取り除いた値を出力してください。先頭に0のついた値を出力すると誤答となります。
例えば N = 38 の時は以下のようになります。
条件
すべてのテストケースにおいて、以下の条件をみたします。
1 ≦ N ≦ 1000000
入力例１
入力
15出力
307674368入力例２
入力
10出力
36288
ちょっと見、ただ単に階乗を求めて、ちょこちょこっと条件に合うように変更するだけにみえますが、実はトラップが何個も仕掛けてありました。
２つの入力例だけの場合は、上記の通り何も考えずにトラップに引っかからずに通ってしまいます。
トラップ１
整数型では単に階乗を求めてしまうとかなり早い段階でオーバーフローを起こしてしまいます。
LL言語で動的型で解こうとしても、JavaScriptなどは内部で浮動小数点型に変換されてしまうため、正確な値がでなくなります。
トラップ２
入力範囲が1000000まで。そのため、何も考えずに再帰で書いてしまうとほぼスタックオーバーフローになります。
