Open Shawngbk opened 7 years ago
对n!做质因数分解n!=2x_3y_5z*...
显然0的个数等于min(x,z)，并且min(x,z)==z
证明：
对于阶乘而言，也就是1_23..._n [n/k]代表1~n中能被k整除的个数 那么很显然 [n/2] > n/5 [n/2^2] > n/5^2 …… [n/2^p] > n/5^p 随着幂次p的上升，出现2^p的概率会远大于出现5^p的概率。 因此左边的加和一定大于右边的加和，也就是n!质因数分解中，2的次幂一定大于5的次幂 public class Solution { public int trailingZeroes(int n) { int count = 0; while(n != 0) { n = n / 5; count = count + n; } return count; } } while循环中有很多不能被2 5 整除的数 逐渐发现到 存在这样的规律：[n/k]代表1~n中能被k整除的个数。
bloomberg
Shawngbk
commented
7 years ago Shawngbk
commented
7 years ago
对n!做质因数分解n!=2x_3y_5z*...
显然0的个数等于min(x,z)，并且min(x,z)==z
证明：
对于阶乘而言，也就是1_23..._n [n/k]代表1~n中能被k整除的个数 那么很显然 [n/2] > n/5 [n/2^2] > n/5^2 …… [n/2^p] > n/5^p 随着幂次p的上升，出现2^p的概率会远大于出现5^p的概率。 因此左边的加和一定大于右边的加和，也就是n!质因数分解中，2的次幂一定大于5的次幂 public class Solution { public int trailingZeroes(int n) { int count = 0; while(n != 0) { n = n / 5; count = count + n; } return count; } } while循环中有很多不能被2 5 整除的数 逐渐发现到 存在这样的规律：[n/k]代表1~n中能被k整除的个数。