ABC148 E. Double Factorial
問題
0以上の整数nに対し、関数f(n)を以下のように定める。
- f(n) = 1 (n<2)
- f(n) = n*f(n-2) (n>=2)
整数Nが与えられる時、f(N)の10進数表記の末尾の0の個数を求めよ。
制約
- 0 <= N <= 10^18
解法
偶数と奇数をそれぞれ考えてみる。
奇数は1*3*5*...と奇数の掛け算なので、答えは偶数にならず、末尾の0はない。
偶数の場合は、1*2*4*6*8*...となるが、10の倍数がいくつ作れるか？が問題になる。
例えば、10=2*5だったり、50=2*5*5のように、素因数分解してでてくる5の数が何個あるかがわかれば、他の2と掛け算して、10が何個作れるか＝答えがわかる。
N以下の偶数で素因数分解して5が出てくる回数は、5が何回でてくるか？はN/5で求められる。
次に同時に5が2回出てくるケースを考えると、5^2が何回でてくるか？で、N/(5^2)で求められる。
これを5^25程度まで繰り返してすべての回数の和を求めると、5の出現回数がわかる。
これに2をかけて10にすればよいので、結局、上記の回数の和が答えになる。
