PKU 1401-Factorial

問題概要

N!の最後につく0の数を求めよ

解法

N!を素因数分解したときの2^a 5^bのmin(a,b)が0の個数になる．
ここで，明らかに2の倍数の方が出現頻度が高いのでbだけ考える．
すると，Nが0になるまで5で割っていき，その総和を求めると答えになることが分かる．

実装(C)

#include <stdio.h>
int main() {
	int n,r;
	for(scanf("%d",&n);~scanf("%d",&n);){
		r=0;
		while(n){
			r+=n/5;
			n/=5;
		}
		printf("%d\n",r);

	}
	return 0;
}