题目链接:点击打开链接
题目的意思就的求n!的末尾的0的个数。
我们知道n!=1*2*3*4*......*n。那么,我们说末尾的0的个数取决于1-n中各数分解因数后,其中2和5的个数。我们可以知道2的个数远远要大于5的个数,那么n!末尾的0,就取决于其中的5的个数了。我们知道,每隔5个数就会有一个是5的倍数,而这个些个能被5整除的数,每隔5个数,又能被25整除一次,所以,需要再除5。
所以可以得到一个递推公式:
f(x)=0,(x<5);
f(x)=x/5+f(x/5);
代码:
#include <cstring> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; /* n!的末尾的0的个数取决于1-n分解因数中2和5的个数. 那么我们知道2的个数的及其多的,关键就是看5的个数。 那么就可以扩张到因子为m的情况了。......beautifal!! */ int f(int x){ if(x<5) return 0; return x/5+f(x/5); } int main(){ int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); printf("%d\n",f(n)); } return 0; }
由此可以推广到,如果就1-n的各个数的因子中为m的个数。也就很简单了。
代码:
int f(int x){ if(x<m) return 0; return x/m+f(x/m); }
感觉m为质数的时候,应该是可以的。
可以知道,递推公式是:
f(x)=0,x<m;
f(x)=x/m+f(x/m);
又发现n!用2进制表示,末尾0个数的求解方法。
点击打开链接 nyoj 954
也是统计2的因子个数。n!=2^a1*3^a2*5^a3......
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; int f(int x){ if(x<2) return 0; return (x>>1)+f(x>>1); } int main(){ int n; while(~scanf("%d",&n)){ printf("%d\n",f(n)+1); } return 0; }