Java求N!中末尾有多少个0
作者:鑫炫 / 发布于2017-8-29/ 58
对N进行质因数分解 N=2^x * 3^y * 5^z...,由于10 = 2*5,所以末尾0的个数只和x与z有关,每一对2和5相乘可以得到一个10,于是末尾0的个数=min(x,z)。在实际中x是远远大于z的,所以我们只要求出z的值即可。 根据公式 z = N/5 + N/5^2 + N/5^3+...+N/5^k 这表明,5的倍数贡献了一个5,5^2的倍数又贡献了一个5...。 比如:25其实是贡献了2个5,但是在N/5中已经贡献了一个,所以在N/5^2中再贡献一个;同样,125在N/5中贡献一个,在N/5^2中贡献一个,在N/5^3中再贡献一个,一共是3个。
评论列表