UVA 10061 How many zeros and how many digits?

题目

多少个零和数字？

分析

1. 真的难；
2. 计算 n! 有多少位以及有多少尾零；

3. 第一个问题是多少位，举一些栗子， 16(10)=1×101+6×100

   256(10)=2×102+5×101+6×100

   对于给定的数字 a 和进制b，只需要求 k=floor(logba)=floor(logalogb) 即可获得位数 k ，实际上所求的是bk<a<bk+1；

   再而是对于 n! ，如果先行求出 n! ，可能存在溢出和超时，那么可以这样 log(n!)=log(n×(n−1)×(n−2)×…×1)=log(n)+log(n−1)+log(n−2)+…+log(1)

4. 第二个问题是尾零，观察 3000(10)! ，

   求尾零实际是在求有多少个10相乘， 1000=10×10×10 有3个10就有三个0，再而分析，有1个10就有一个5（

   最大质因数

   ），求出这些数分解后有多少个5相乘，就有多少个尾零，为什么考虑5呢？因为阶乘可能溢出或者超时，如果拆开对每个数考察，只考察10结果是不可靠的，所以应该考察组成10的因子；

   3000(10)! 可以表示为

   1×2×3×4×(5×1)×…×9×(5×2)×…×14×(5×3)×…×1×(5×600)

   有600个5相乘，就是有600个0。

   但是在上式中，括号内的 [1,600] 这些数字中又有5的倍数，那么 [1,600] 中有多少个5的倍数，意味着漏了多少个0。

   1×2×3×4×(5×1)×…×9×(5×2)×…×14×(5×3)×…×1×(5×120)

   有120个5相乘，就是有120个0 。

   但是在上式中，括号内的 [1,120] 这些数字中又有5的倍数，那么 [1,120] 中有多少个5的倍数，意味着又漏了多少个0。

   1×2×3×4×(5×1)×…×9×(5×2)×…×14×(5×3)×…×1×(5×24)

   有24个5相乘，就是有24个0 。

   但是在上式中，括号内的 [1,24] 这些数字中又有5的倍数，那么 [1,24] 中有多少个5的倍数，意味着又漏了多少个0。

   1×2×3×4×(5×1)×…×9×(5×2)×…×14×(5×3)×…×1×(5×4)×…×24

   有4个5相乘，就是有4个0 。

   此时不再有5，结束。共有 600+120+24+4=748 个尾零。

代码

#include <stdio.h>
#include <math.h>

int cal_digit(int n, int b)
{
    int i;
    double l;
    for (i = , l = ; i <= n; i++)
        l += log10(i) / log10(b);
    return l + ;
}

int cal_zero(int n, int b)
{
    int i, d, m, t;
    for (i = , d = ; i <= b; i++) {
        m = ;
        while (b % i == ) {
            m++;
            d = i;
            b /= i;
        }
    }
    for (t = ; n > ; ) {
        t += n / d;
        n /= d;
    }
    return t / m;
}

int main(void)
{
    int n, b;
    while (scanf("%d%d", &n, &b) != EOF)
        printf("%d %d\n", cal_zero(n, b), cal_digit(n, b));
    return ;
}