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

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

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

能过 10810^8 我只能赞美评测机了 \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');
}