Posted on 2007-04-19 15:30
kk 阅读(892)
评论(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，知道结果后才知道原来这么简单的阿，偶土了。