kmjp's blog

競技プログラミング参加記です

AtCoder ABC #148 : E - Double Factorial

新ABCで一番簡単な回?
https://atcoder.jp/contests/abc148/tasks/abc148_e

問題

  • nが1以下の時f(n)=1
  • nが2以上のときf(n)=n*f(n-2)

整数Nが与えられるとき、f(N)は末尾に0が何個付くか。

解法

Nが奇数の時、f(N)は奇数なので0。
Nが偶数の場合、f(N)=N*(N-2)*(N-4)*...が素因数として5の何乗を持つかを考えよう。
floor(N/10)+floor(N/(10*5))+floor(N/(10*5^2))+floor(N/(10*5^3))+...
となるのでそれが解。
素因数として明らかに2より5の方が少ないので、2の方は考えなくてよい。

ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	if(N%2==1) {
		cout<<0<<endl;
	}
	else {
		ll ret=0;
		ll cur=10;
		while(cur<=N) {
			ret+=N/cur;
			cur*=5;
		}
		cout<<ret<<endl;
	}
}

まとめ

400ptじゃないの?と思いながら解いてた。