読者です 読者をやめる 読者になる 読者になる

川のブログ

川の適当気ままなブログです。 

AOJ 0052 Factorial II

AOJ volume0

こんにちは川です。

この問題は階乗に関係している問題ですが、普通に階乗してしまうと膨大な数となってしまいます。末尾が0となる場合は10がかけられた場合になります。10は5と2の二つの素数からなっています。階乗していくと2回に1回偶数なので2は大量にかけられていることがわかります。そこで5が何回かけられているかを数えれば0が末尾に何個あるかがわかります。

 

ソースコード

 

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,fac=0,ans=0,now,num;
while(cin>>n&&n!=0){
for(int i=1;;i++){
num=5*i;
if(num>n)break;
for(int j=1;num%5==0;j++){
num/=5;
now=j;
}
ans+=now;
}
cout<<ans<<endl;
ans=0;
}
}