paiza POH ando #_poh 水着チャレンジ

	URL
解答集	http://qiita.com/cielavenir/items/2fd430a3468a068feef5
withVaList()を書いた話	http://qiita.com/cielavenir/items/2598d47b97a7c9caf970
水着チャレンジ(のrobustな解法)	http://qiita.com/cielavenir/items/46f873191b37736d5062

N!の下位0を取り除いた状態の下位9桁を求める問題。
普通に考えると、iを掛けて、10で割れるだけ割って、10**9の余りを取れば良いと思うかもしれない。
しかし、これだと、Nが5の冪の場合に死ぬ。問題文の制約の場合、(本番テストケースには含まれていないが)最悪ケースは390625(==5**8)であり、正解するためには10**17で計算して最後に10**9の余りを取る必要がある。これはかなりcostlyである。
これを防ぐためには、予め下位の0の個数を求め、各iに対し予め2で割ったり5で割ったりしておくと良い。
0の個数を求めるには、5の冪で割った商を足しあわせれば良い。

この方法であればint64で計算できる。

なお、「5の冪の階乗」がコーナーケースであるというのはえちごやえちぜん氏の指摘です。感謝します。
https://twitter.com/echigoyaechizen/status/676288524383993856

paizapoh7_4c.rb

#!/usr/bin/ruby
N=gets.to_i
z=0
n=N
while n>0
	z+=n/5
	n/=5
end
r=1
c2=0
c5=0
(1..N).each{|_|
	i=_
	while c2<z && i%2==0
		c2+=1
		i/=2
	end
	while c5<z && i%5==0
		c5+=1
		i/=5
	end
	r*=i
	r%=10**9
}
p r

paizapoh7_4c.swift

//usr/bin/env swift $0 $@;exit
let N=Int(readLine()!)!
var z=0
var n=N
for ;n>0;n/=5 {z+=n/5}
var r:Int64=1
var c2=0
var c5=0
var j=1
for ;j<=N;j++ {
	var i=j
	for ;c2<z && i%2==0;i/=2 {c2++}
	for ;c5<z && i%5==0;i/=5 {c5++}
	r*=Int64(i)
	r%=1000000000
}
print(r)