乘阶后缀0有关问题

wuyoudexian / 2023-08-06 / 原文

给定一个数\(n\)，求\(n!\)有多少个后缀0。比如\(5!=1\times2\times3\times4\times5=120\)，有1个后缀0。

n!的后缀0

因为只有\(2\times5\)才能产生后缀0，且2因子的数量一定比5因子的数量更多，所以只需要判断5因子的数量即可。

先计算1~n之间有多少个数被5整除，很显然，是\(\lfloor \frac{n}{5} \rfloor\)个。再计算1~n之间有多少个数被25整除，以此类推，直到第\(k\)次时\(5^k>n\)就不需要计算了。代码如下

for(int i = 5; i <= n; i *= 5) {
    ans += n / i;
}

(n!)!的后缀0

由上面的思路，先计算1!~n!之间有多少个数被5整除，显然有\(\lfloor \frac{1}{5} \rfloor+\lfloor \frac{2}{5} \rfloor+\cdots+\lfloor \frac{n}{5} \rfloor\)个。
再令原式\(=\lfloor \frac{1}{5} \rfloor+\lfloor \frac{2}{5} \rfloor+\cdots+ \lfloor \frac{s-1}{5} \rfloor+\lfloor \frac{s}{5} \rfloor +\cdots+\lfloor \frac{n}{5} \rfloor\)（s为最接近n且小于n的5的倍数）。
=\(5\times(1+2+3+\cdots+(\lfloor \frac{n}{5}\rfloor-1))+(n\%5+1)\times\lfloor \frac{n}{5} \rfloor\)
=\(5\times\lfloor \frac{n}{5}\rfloor\times(\lfloor \frac{n}{5} \rfloor-1)\div2+(n\%5+1)\times\lfloor \frac{n}{5} \rfloor\)

同理，1!~n!中能被25整除的个数为\(25\times\lfloor \frac{n}{25}\rfloor\times(\lfloor \frac{n}{25} \rfloor-1)\div2+(n\%25+1)\times\lfloor \frac{n}{25} \rfloor\)，以此类推。

for(int i = 5; i <= n; i *= 5) {
	ans += i * (n / i) * (n / i - 1) >> 1;
	ans += (n % i + 1) * (n / i);
}

n!!的后缀0

还是计算\(n!\)的思路，但是得判断其奇偶性进行操作后再除2。

for(int i = 5; i <= n; i *= 5) {
	ans += (n / i + n % 2) / 2;
}

(n!!)!的后缀0

C-idol!!_2023牛客暑期多校训练营6 (nowcoder.com)

~~这破题卡我一天~~

暴力，复杂度为\(O(nlogn)\)。

for(ll i = 5; i <= n; i *= 5) {
	for(ll j = n; j > 0; j -= 2) {
		ans += j / i;
	}
}

我的代码，复杂度为\(O(logn)\)。

for(i128 f = 5; f <= n; f *= 5) {
	i128 a1 = f / 2 + (n & 1);
	i128 d = f * 2;
	i128 cnt = (n + 1) / (f * 2);
	if(2 * f < n) {	
		ans += a1 * cnt + cnt * (cnt - 1) * d / 2;
	}
	i128 lst = n / f;
	i128 cnt0 = ((n + 1) % (cnt * f * 2) + 1) / 2;
	if(lst % 2 == 0) {
		ans += cnt0 * lst;
	} else {
		ans += (f - a1) * (lst - 1);
		ans += (cnt0 - f + a1) * lst;
	}
}

别人的简洁代码，复杂度为\(O(logn)\)。

for(int k = 5; k <= n; k *= 5){
	int cnt = n / k;
    ans += (n * cnt - k * (cnt + 1) * cnt / 2 + cnt + (cnt + (n & 1)) / 2) / 2;
}