题解 | #阶乘(factorial)#

考虑 $x!\to (x+1)!x!\backslash rightarrow\; (x+1)!$ 有什么贡献。

首先 $(x+1)!(x+1)!$ 一定包含了 $x!x!$ 中所有的 $55$，也就是说直接把 $x+1x+1$ 自己里面的 $55$ 加入到答案即可。

时间复杂度不会算，但显然大于 $O(n)O(n)$。

能过 $10^{8}10^8$ 我只能赞美评测机了 $\sim \backslash sim$

#include<cstdio>
#define int long long
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
signed main(){
	int n = init(), ans = 0, x = 0;
	for (int i = 5; i <= n; ++i) {
		int y = i;
		while (y % 5 == 0) { ++x; y /= 5; } // 每多一个 5 就多叠一层 buff
		ans += x;
	}
	print(ans), putchar('\n');
}