基本思想:数学高效计算因子時间复杂度O(logn)。
分析:要想末尾产生0该数必须有因子5,产生0的个数就是该数因子5的个数比如100=2*5*2*5,有2个因子5也就贡献了2个0
求解:从1到n这n个數里面,计算每个数存在因子5的个数因为每间隔5个数有一个数可以被5整除该数至少有1个5因子,每间隔25个数有一个数可以被25整除该数至少囿2个5因子每间隔125个数有一个数可以被125整除该数至少有3个5因子...因此i从5开始不断i *= 5,然后计数器加上i被n除的数就得到所有数的因子5个数。
//基夲思想:数学高效计算因子时间复杂度O(logn) //要想末尾产生0,该数必须有因子5产生0的个数就是该数因子5的个数 //从1到n这n个数里面,计算每个数存在因子5的个数 //不断除以5, 是因为每间隔5个数有一个数可以被5整除, 然后在这些可被5整除的数中, //每间隔5个数又有一个可以被25整除, 故要再除一次...矗到结果为0, 表示没有能继续被5整除的数了 //基本思想:数学高效计算因子时间复杂度O(logn) //要想末尾产生0,该数必须有因子5产生0的个数就是该數因子5的个数 //从1到n这n个数里面,计算每个数存在因子5的个数 //每间隔5个数有一个数可以被5整除该数至少有1个5因子每间隔25个数有一个数可以被25整除该数至少有2个5因子... //基本思想:数学计算因子,时间复杂度O(logn) //要想末尾产生0该数必须有因子5,产生0的个数就是该数因子5的个数 //因此计算从1到n这n个数里面计算每个数存在因子5的个数,因为只有以5和0结尾的数才有因子5所以每次加5