1423

N!が何桁の数であるか答えよ、という問題。Nは10M程度まで。

クエリが複数個くるので、取り敢えずメモをしておく。桁数はlogで求めることができる。(というかそういう定義になっているはず。)intで10M個持つことはできるが、10M回logを呼ぶとTLEするので、ある程度キャッシュしておいて、一番近い値からいくつかを毎回計算して求めてやれば良い。つまり1M回logを呼んで、結果をdouble配列に格納しておき、一番近い値から1回のlogで目的の値に到達することができる。10刻みなのは、10M^10がdoubleの範囲に収まるので、一括してlogを計算できるからで、他の値でも問題はない。他の早い言語だと10M回呼んでも間に合ったりしそうだけれど、試す気はしない。