题目简述
定义 \(\operatorname{count}(num)\) 表示 \(num\) 末尾 \(0\) 的个数。给出 \(n\)（\(n \leq 10^{18}\)），求 \(\sum \limits _ {i = 0} ^ {n} [2 \mid \operatorname{count}(i!)]\)。
题目分析
对于一个 \(i\)，以下记成 \(n\)。
\(n!\) 末尾 \(0\) 的个数取决于 \(1 \sim n\) 中 \(2\) 的幂次之和和 \(5\) 的幂次之和的最小值。又由于 \(2\) 的幂次肯定超过 \(5\) 的幂次之和，参见以下证明：
证明：
\(1 \sim n\) 中，\(2\) 的倍数都至少贡献了 \(1\)，\(4\) 的倍数在此基础上，又多贡献了一个 \(1\)，以此类推。于是，\(1 \sim n\) 中，\(2\) 的幂次之和为：
\[\sum _ {i = 1} ^ {\infty} \Big \lfloor \cfrac{n}{2 ^ i} \Big \rfloor \]对于 \(5\) 同理：
\[\sum _ {i = 1} ^ {\infty} \Big \lfloor \cfrac{n}{5 ^ i} \Big \rfloor \]对于每一位考虑。\(\forall i\)，\(\Big \lfloor \cfrac{n}{2 ^ i} \Big \rfloor \geq \Big \lfloor \cfrac{n}{5 ^ i} \Big \rfloor\)，所以 \(\sum \limits _ {i = 1} ^ {\infty} \Big \lfloor \cfrac{n}{2 ^ i} \Big \rfloor \geq \sum \limits _ {i = 1} ^ {\infty} \Big \lfloor \cfrac{n}{5 ^ i} \Big \rfloor\)。证毕。
那么，末尾 \(0\) 的个数等于 \(1 \sim n\) 中 \(5\) 的幂次之和。
\[\operatorname{count}(n!) = \sum _ {i = 1} ^ {\infty} \Big \lfloor \cfrac{n}{5 ^ i} \Big \rfloor \]那么答案有：
\[ans = \sum _ {i = 0} ^ {n} \Bigg [ 2 \mid \sum _ {j = 1} ^ {\infty} \Big \lfloor \cfrac{i}{5 ^ j} \Big \rfloor \Bigg ] \]发现把 \(i\) 用 \(5\) 进制表示成 \(i = \overline{x_mx_{m-1}\ldots x_0}\)，那么 \(\Big \lfloor \cfrac{}{5^j} \Big \rfloor\) 就是 \(5\) 进制下的移位。也即 \(\Big \lfloor \cfrac{i}{5^j} \Big \rfloor = \overline{x_mx_{m-1}\ldots x_j}\)。我们只关心这个式子的奇偶性。拆开：\(\overline{x_mx_{m-1}\ldots x_j} = \sum \limits _ {k = j} ^ {m} 5 ^ {k - j} x_k\)，而 \(5 \perp 2\)，故上式与 \(\sum \limits _ {k = j} ^ {m} x_k\) 同奇偶。接下来继续化式子。
\[\begin{aligned} ans &= \sum _ {i = 0} ^ {n} \Bigg [ 2 \mid \sum _ {j = 1} ^ {\infty} \Big \lfloor \cfrac{i}{5 ^ j} \Big \rfloor \Bigg ] \\ &= \sum _ {i = 0} ^ {n} \Bigg [ 2 \mid \sum _ {j = 1} ^ {m} \sum \limits _ {k = j} ^ {m} x_k \Bigg ] \\ &= \sum _ {i = 0} ^ {n} \Bigg [ 2 \mid \sum _ {j = 1} ^ {m} x_j \times j \Bigg ] \\ &= \sum _ {i = 0} ^ {n} \Bigg [ 2 \mid \sum _ {j = 1 \land j \bmod 2 = 1} ^ {m} x_j \Bigg ] \\ \end{aligned} \]也即，\(n!\) 某位有偶数个 \(0\)，等价于其在 \(5\) 进制表示下，奇数位的和能否被 \(2\) 整除。答案就是 \(0 \sim n\) 中，在 \(5\) 进制表示下，奇数位的和能被 \(2\) 整除的数字的个数。这个使用数位 DP 即可。状态记录剩余几位、目前奇数位的和被 \(2\) 除的余数。
代码
#include <cstdio>
long long n, f[30][2];
int yzh[30], len;
long long dp(int len, bool limit, bool sum) {
if (!~len) return !sum;
if (!limit && f[len][sum]) return f[len][sum];
long long res = 0;
for (int i = limit ? yzh[len] : 4; ~i; --i)
res += dp(len - 1, limit && i == yzh[len], (len & 1) ? (sum ^ (i & 1)) : sum);
if (!limit) f[len][sum] = res;
return res;
}
inline long long solve() {
for (len = -1; n; yzh[++len] = n % 5, n /= 5);
return dp(len, true, 0);
}
signed main() {
while (scanf("%lld", &n), ~n) printf("%lld\n", solve());
return 0;
}