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

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

阅读量：6158 次

发布时间：2019-06-21

本文共 1837 字，大约阅读时间需要 6 分钟。

题目链接:

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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #define MAX 1100#define LL long longusing 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<
                 
                  <