這又是一個數學題，不過我還是比較喜歡做這類數學雜題的。題目意思很簡單，給2個十進制數，n和b。如果用b進制表示n!，
需要多少位數，這個表示末尾會有多少個0。這個題并不需要什么高深的知識，這一點也是我喜歡做這類題的一個方法。
大家顯然都知道求n！用10進制表示末尾會有多少個0的方法，就是求2*5最多有多少對。那么，b進制了。方法類似，發散一下想法而已。
我還是先說求多少位數的方法吧。
b的m-1次 <= n！<= b的m次（PS，這個不等式如果把b換成10大家一定會明白的），
看到這個不等式應該有想法了吧。兩邊同時取logb，就可以得到
Σlogi(1<=i<=n) <= m，m直接就求出來了。m即是位數。
再說怎么求末尾0的，發散下想法，我們也可以對n！中的每個因子試著求b的因子對，一共有多少對。但是，后面發現這樣不行，
因為比如b是16，1和16是一對因子，2和8是一對因子，4和4是一對因子，也就是因為2也是4的因子，這樣計算因子對就會重復了。
但是對于b等于10的情況，可以例外而已。
呵呵，考慮其它的方法。求素數因子。任何數字都可以被分解為一些素數因子的乘積，這是毋容置疑的。那么，我們去分解n！中的
小于等于b的素數因子，并將其個數存儲在數組里面。然后死循環的去分解b的素數因子，能夠完全分解一次
(具體看下代碼，不好描述），ans就加1。否則，已經沒有末尾0了。
雖然提交了16次才過。不過最后還算不錯吧，只用了0.508s。相比20s的時間界限，很小了。網上有些過的代碼，跑一個數據都要
幾分鐘。。。PS：uva上那些神人，怎么用0.0s算出來的，很難想象啊。
這個題目還有個很大的需要注意的地方，就是浮點數的精度問題。前面講到求位數需要用到log函數，log函數的計算精度就出問題了。
最后需要對和加一個1e-9再floor才能過。特別需要注意這一點，因為開始我的程序過了所有的http://online-judge.uva.es/board/viewtopic.php?f=9&t=7137&start=30上說的數據還是wa了。而且我還發現
log10計算精度高很多，如果log(這個是自然對數)去計算，這個網站上的數據都過不了。
#include <stdio.h>
#include <string.h>
#include <math.h>
int nN, nB;
int nDivisor[1000];
int GetDigit(int nN, int nB)
{
double fSum = 0.0;
for (int i = 2; i <= nN; ++i)
{
fSum += log10(i);
}
fSum /= log10(nB);
return floor(fSum + 1e-9) + 1;
}
int GetZero(int nN, int nB)
{
memset(nDivisor, 0, sizeof(nDivisor));
for (int i = 2; i <= nN; ++i)
{
int nTemp = i;
for (int j = 2; j <= nTemp && j <= nB; ++j)//這樣循環就可以進行素數因子分解了
{
while (nTemp % j == 0)
{
nDivisor[j]++;
nTemp /= j;
}
}
}
int nAns = 0;
while (1)
{
int nTemp = nB;
for (int j = 2; j <= nTemp; ++j)//分解nB
{
while (nTemp % j == 0)
{
if (nDivisor[j] > 0)//如果還可以繼續分解
{
--nDivisor[j];
}
else //直接可以goto跳出多重循環了
{
goto out;
}
nTemp /= j;
}
}
++nAns;
}
out:
return nAns;
}
int main()
{
while (scanf("%d%d", &nN, &nB) == 2)
{
int nDigit = GetDigit(nN, nB);
int nZero = GetZero(nN, nB);
printf("%d %d\n", nZero, nDigit);
}
return 0;
}