本文主要是介绍uva 10061 How many zero's and how many digits ?（不同进制阶乘末尾几个0）+poj 1401，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意是求在base进制下的 n！的结果有几位数，末尾有几个0。
想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零，以及之前有做过的一道n阶乘的位数。
当时都是在10进制下的。
10进制下的做法是：
1. n阶位数：直接 lg（n！）就是得数的位数。
2. n阶末尾0的个数：由于2 * 5 将会在得数中以0的形式存在，所以计算2或者计算5，由于因子中出现5必然出现2，所以直接一趟遍历，找出能整除5的数就行了，5的个数就是末尾0的个数。
推广到base进制下：
1. n阶的位数：log base （n！），换底公式，可以换成 lg（n！） / lg（base）。
2.n阶末尾0的个数：在n！中找可以凑成base的因子，比如16，可以找1， 16或者2,8或者4,4。
具体做法是n！里面的每一个数都分解成因子相乘的形式，并记录下来，然后到base中去凑，若能凑成，阶乘末尾就多一个0。
代码：
#include <stdio.h>
#include <math.h>
#include <string.h>int n, base;
int a[1000];//记录n中小于等于base的因子数int ZeroNum()
{memset(a, 0, sizeof(a));//将n!中的所有数拆分出因子，并记录下来该因子（j）对应有多少个for (int i = 2; i <= n; i++){int tmp = i;for (int j = 2; j <= tmp && j <= base; j++){while (tmp % j == 0){a[j]++;tmp /= j;}}}//将拆分出的因子枚举，若其能拼凑成一组base，则出现一个0。int res = 0;while (1){int tmp = base;for (int i = 2; i <= tmp; i++){while (tmp % i == 0 && a[i] > 0){a[i]--;tmp /= i;}}if (tmp == 1)res++;elsebreak;}return res;
}int DigitNum()
{double sum = 0;int res;for (int i = 1; i <= n; i++){sum += log(i);}res = sum / log(base) + 1;return res;
}int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALwhile (scanf("%d%d", &n, &base) == 2){printf("%d %d\n", ZeroNum(), DigitNum());}return 0;
}
大神带你飞。
不理解这个求末尾0的做法：
add 2014.12.30:
正在学习数论，看完书再翻回来看这个代码就懂了。
这是素数的一个基本定理，即：n！的素因子分解种的素数p的幂为：（n / p） + （n / p ^ 2） + （n / p ^ 3） + …
在十进制下，能凑成末尾0的因子是2,5，而对于n！，在因式分解中，2的因子个数要大于5的因子个数（++先到2后到5，so有5必有2）。
所以如果存在一个因子5，必然对应着n！末尾的一个0，所以就变成了求n！中5的因子数，直接由性质得出，见下题poj1401.
转换成base进制下，自然成了找到乘积为base中最大的那个素因子，然后算有几个，最后转换下进制就行了。
#include <stdio.h>
#include <math.h>int main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);#endif // LOCALint n, base;while (scanf("%d%d", &n, &base) == 2){int num;double sum = 0;//计算位数for (int i = 1; i <= n; i++){sum += log(i);}num = sum / log(base) + 1;//计算末位0的个数int cnt2 = 0;int cnt1;int maxprime;
//找最大素因子
for (int i = 2; i <= base; i++){cnt1 = 0;while (base % i == 0){maxprime = i;cnt1++;base /= i;}}while (n){n /= maxprime;cnt2 += n;}printf("%d %d\n", cnt2 / cnt1, num);}return 0;
}
poj 1401：
#include <stdio.h>
#include <math.h>int findZero(int n, int base)
{int cnt2 = 0;int cnt1;int maxprime;for (int i = 2; i <= base; i++){cnt1 = 0;while (base % i == 0){maxprime = i;cnt1++;base /= i;}}while (n){n /= maxprime;cnt2 += n;}return cnt2 / cnt1;
}int main()
{
#ifdef LOCAL//freopen("in.txt", "r", stdin);
#endif // LOCALint ncase;scanf("%d", &ncase);while (ncase--){int n;scanf("%d", &n);printf("%d\n", findZero(n, 10));}return 0;
}
这篇关于uva 10061 How many zero's and how many digits ?（不同进制阶乘末尾几个0）+poj 1401的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
