新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じゃないの?と思いながら解いてた。