pku 1401 Factorial 算数基本定理 && 51nod 1003 阶乘后面0的数量

题意：计算N！的末尾0的个数

思路：算数基本定理

有0，分解为2*5，寻找2*5的对数，2的因子个数大于5，转化为寻找因子5的个数。又有算数基本定理：

n！在素数因子分解中p的幂为[n/p]+[n/p²]+[n/p³]+...

同时最大次数不会超过log_pn。通过换底公式，有ln(n)/ln(p)

代码：(51Nod去掉t循环即可)

 #include <iostream>

 #include <math.h>

 using namespace std;

 int main() {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     ios::sync_with_stdio(false);

     int n,t;

     cin>>t;

     while(t--) {

         cin>>n;

         int num=,sum=,index=(int)(log(n*1.0)/log(*1.0));

         for(int i=; i<=index; ++i) {

             sum+=n/num;

             num*=;

         }

         cout<<sum<<endl;

     }

     return ;

 }

巴特西

pku 1401 Factorial 算数基本定理 && 51nod 1003 阶乘后面0的数量

最新文章

热门文章