SRM420 Div2 1000

問題

AからBまでの数字の積Cを考える．このとき答えはC=D*10^Eと書くことができる．これを計算する．
ただし，出力は，Dの部分が10ケタを超えるときは「上5ケタ...下5ケタ * 10^E」で出力する．

考え方

多倍長演算的なのは結構値が大きくなるので，間に合わない．

桁が大きくなるので，log10をとって計算する．
log10(A*(A+1)*...*B)=log10(C*10^E)なので，log10(A)+log10(A+1)+...+log10(B)=log10(C)+Eとなる．左辺はループで計算できる．必要なのはCとE．
下5ケタは逐次計算していけるので，このときEも一緒に計算する．
この下5ケタの計算方法は，かけてmodをとると，桁あふれしたりで，十分な精度で計算できない．なので，x*yを計算する前に，xとyの素因数で2と5の個数を求めて，先に末尾の0の個数(E)を計算・除去してから計算する．
上5ケタの計算方法は，C=pow( (左辺)-(左辺の整数部分) )が結果の先頭部分を表す小数となる．なので，(int)(C*10000)で得られる．
表示の切り替えは，Dの桁数が10ケタ以上なら分けて表示しないといけない．Dの桁数は，(左辺の整数部分)が全体の桁数を表すので，「(左辺の整数部分)-E」で求められる．これが10以上のときは分けて表示，そうでなければ，下5ケタの計算の時に10ケタ以上の精度で計算しておいて，その結果を返す．

反省

桁が大きくなるような計算はlogとか使うといいことがあるかも．