洛谷P2388 阶乘之乘 题解
题目链接:P2388 阶乘之乘
题意:
求出 \(1!\times 2!\times 3!\times 4!\times \cdots \times n!\) 的末尾有几个零。
输入格式:
一行,一个整数 \(n(n\le 10^8)\)。
输出格式:
输出答案,表示零的个数。
很经典的一道题,先说一下 \(\mathcal{O}(n)\) 的小学生解法:
注意到 \(n!\) 中 \(5\) 的个数显然小于 \(2^i\) 的个数,于是我们只需要统计每个阶乘里有多少个 \(5\) 即可
scanf("%lld",&n);
for(int i=1; i<=n; i++)
{
int tmp=i;
while(tmp%5==0)sum++,tmp/=5;
ans+=sum;
}
printf("%lld\n",ans); // 本代码写于 2021-03-08
下面说一下更快的解法。考虑把刚才的结论写成式子。
令 \(f(n)=\sum_{i=1}^{\infty}\left\lfloor\frac{n}{5^i}\right\rfloor\) ,则 \[ \mathrm{Ans}(n) = \sum_{i=1}^n f(i)=\sum_{i=1}^n \sum_{j=1}^{\infty}\left\lfloor\frac{i}{5^j}\right\rfloor=\sum_{j=1}^{\infty} \sum_{i=1}^n\left\lfloor\frac{i}{5^j}\right\rfloor=\sum_{j=1}^{\infty}\left(5^j \sum_{i=1}^{\left\lfloor\frac{n}{5^j}\right\rfloor-1} i+\left\lfloor\frac{n}{5^j}\right\rfloor \cdot\left(n \bmod 5^j+1\right)\right) \] 时间复杂度 \(\mathcal{O}(\log n)\)
主要代码:
int n, res = 0; cin >> n;
for(int j = 5; j <= n; j *= 5)
{
res += j * (n / j) * (n / j - 1) / 2;
res += (n / j) * (n % j + 1);
}
cout << res << '\n';
参考文献: