首页 > 代码库 > 数论 - 算数基本定理的运用 --- 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就可。
后面也是看了解题报告才知道有这么一个结论。
这是算数基本定理的一个结论：
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 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<<ans<<endl; } return 0;}
数论 - 算数基本定理的运用 --- nefu 118 : n!后面有多少个0
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。