Posted on 2007-04-19 15:30
kk 閱讀(916)
評論(1) 編輯 收藏 引用 所屬分類:
Algorithm
終于悟到了。
首先，很容易想到的就是，求0的個數，就是求5的個數（如果這個你都想不明白的話，那就。。。再好好想想吧，呵呵）；
接下來，如何求5的個數呢？如果遍歷一遍的話，那顯然是太慢了！因為這種計算題太有規律了！想了好久，終于想出來了：
Result = 0; // 最后的結果
while ( N >= 5 )
{
N /= 5;
Result += N;
}
// 結束了。
沒錯，就是這么簡單！下面簡單說說為什么這樣子做是對的（偶小試了一下，沒問題，呵呵）：
第一次除以5表示5的倍數的個數，
第二次除以5表示5的平方的倍數的個數，（顯然，5的平方暗含了兩個0）
。。。依此類推
最后當N<5了，結束。
小小的驗證一下：
26！
26/5 = 5， 5/5 = 1，那么最后0的個數就是6了。用Google算了一下，結果G大叔直接用有效數字表示了，@$%$%@$%。。。不過應該是沒錯了。恩。
Sigh，知道結果后才知道原來這么簡單的阿，偶土了。