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 ;
}