這又是一個(gè)數(shù)學(xué)題，不過(guò)我還是比較喜歡做這類數(shù)學(xué)雜題的。題目意思很簡(jiǎn)單，給2個(gè)十進(jìn)制數(shù)，n和b。如果用b進(jìn)制表示n!，
需要多少位數(shù)，這個(gè)表示末尾會(huì)有多少個(gè)0。這個(gè)題并不需要什么高深的知識(shí)，這一點(diǎn)也是我喜歡做這類題的一個(gè)方法。
大家顯然都知道求n！用10進(jìn)制表示末尾會(huì)有多少個(gè)0的方法，就是求2*5最多有多少對(duì)。那么，b進(jìn)制了。方法類似，發(fā)散一下想法而已。
我還是先說(shuō)求多少位數(shù)的方法吧。
b的m-1次 <= n！<= b的m次（PS，這個(gè)不等式如果把b換成10大家一定會(huì)明白的），
看到這個(gè)不等式應(yīng)該有想法了吧。兩邊同時(shí)取logb，就可以得到
Σlogi(1<=i<=n) <= m，m直接就求出來(lái)了。m即是位數(shù)。
再說(shuō)怎么求末尾0的，發(fā)散下想法，我們也可以對(duì)n！中的每個(gè)因子試著求b的因子對(duì)，一共有多少對(duì)。但是，后面發(fā)現(xiàn)這樣不行，
因?yàn)楸热鏱是16，1和16是一對(duì)因子，2和8是一對(duì)因子，4和4是一對(duì)因子，也就是因?yàn)?也是4的因子，這樣計(jì)算因子對(duì)就會(huì)重復(fù)了。
但是對(duì)于b等于10的情況，可以例外而已。
呵呵，考慮其它的方法。求素?cái)?shù)因子。任何數(shù)字都可以被分解為一些素?cái)?shù)因子的乘積，這是毋容置疑的。那么，我們?nèi)シ纸鈔！中的
小于等于b的素?cái)?shù)因子，并將其個(gè)數(shù)存儲(chǔ)在數(shù)組里面。然后死循環(huán)的去分解b的素?cái)?shù)因子，能夠完全分解一次
(具體看下代碼，不好描述），ans就加1。否則，已經(jīng)沒(méi)有末尾0了。
雖然提交了16次才過(guò)。不過(guò)最后還算不錯(cuò)吧，只用了0.508s。相比20s的時(shí)間界限，很小了。網(wǎng)上有些過(guò)的代碼，跑一個(gè)數(shù)據(jù)都要
幾分鐘。。。PS：uva上那些神人，怎么用0.0s算出來(lái)的，很難想象啊。
這個(gè)題目還有個(gè)很大的需要注意的地方，就是浮點(diǎn)數(shù)的精度問(wèn)題。前面講到求位數(shù)需要用到log函數(shù)，log函數(shù)的計(jì)算精度就出問(wèn)題了。
最后需要對(duì)和加一個(gè)1e-9再floor才能過(guò)。特別需要注意這一點(diǎn)，因?yàn)殚_(kāi)始我的程序過(guò)了所有的http://online-judge.uva.es/board/viewtopic.php?f=9&t=7137&start=30上說(shuō)的數(shù)據(jù)還是wa了。而且我還發(fā)現(xiàn)
log10計(jì)算精度高很多，如果log(這個(gè)是自然對(duì)數(shù))去計(jì)算，這個(gè)網(wǎng)站上的數(shù)據(jù)都過(guò)不了。
#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)//這樣循環(huán)就可以進(jìn)行素?cái)?shù)因子分解了
{
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)//如果還可以繼續(xù)分解
{
--nDivisor[j];
}
else //直接可以goto跳出多重循環(huán)了
{
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;
}