数论 - 算数基本定理的运用 --- nefu 118 : n!后面有多少个0-阿里云开发者社区

开发者社区> 开发与运维> 正文

数论 - 算数基本定理的运用 --- nefu 118 : n!后面有多少个0

简介:  题目链接:http://acm.nefu.edu.cn/JudgeOnline/problemshow.php   Mean:   略。 analyse:  刚开始想了半天都没想出来,数据这么大,难道是有什么公式? 首先我们要知道一点:n!里面所有的0都是2*5得来的,而且不管怎样2的数量一定是>5的数量,所以我们只需要考虑有多少个5就可。

 


 

Mean: 

 略。

analyse:

 刚开始想了半天都没想出来,数据这么大,难道是有什么公式?

首先我们要知道一点:n!里面所有的0都是2*5得来的,而且不管怎样2的数量一定是>5的数量,所以我们只需要考虑有多少个5就可。

后面也是看了解题报告才知道有这么一个结论。

这是算数基本定理的一个结论:

   n!的素因子分解中的素数p的幂为:[n/p]+[n/p^2]+[n/p^3]+...

知道这个结论,这道题就是一道大水题,1分钟ac。数论就是这样==。

Time complexity:O(n)

 

Source code:

 

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
.............................................
           佛祖镇楼                  BUG辟易
     佛曰:
           写字楼里写字间,写字间里程序员;
           程序人员写程序,又拿程序换酒钱。
           酒醒只在网上坐,酒醉还来网下眠;
           酒醉酒醒日复日,网上网下年复年。
           但愿老死电脑间,不愿鞠躬老板前;
           奔驰宝马贵者趣,公交自行程序员。
           别人笑我忒疯癫,我笑自己命太贱;
           不见满街漂亮妹,哪个归得程序员?
*/

//Memory   Time
// 1347K   0MS
// by : Snarl_jsb
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<climits>
#include<cmath>
#define MAX 1100
#define LL long long
using namespace std;


int main()
{
//    freopen("C:\\Users\\ASUS\\Desktop\\cin.txt","r",stdin);
//    freopen("C:\\Users\\ASUS\\Desktop\\cout.txt","w",stdout);
    int t,m;
    cin>>t;
    while(t--)
    {
        cin>>m;
        int five=5;
        int ans=0;
        while(five<=m)
        {
            ans+=m/five;
            five*=5;
        }
        cout<<ans<<endl;
    }
    return 0;
}
    

  

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章