勒让德公式

定义

---

勒让德公式

勒让德公式（Legendre’s Formula）主要指在数论中用于计算正整数 $n!$中某个质数 $p$ 的最高幂指数的公式。
对于任意质数 $p$ 和正整数 $n$，在 $n!$ 的质因数分解中，$p$ 的幂次 $E_p(n!)$ 为：
$E_p(n!)={\sum }_{k=1}^{\infty }\lfloor \frac{n}{p^k}\rfloor =\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +\lfloor \frac{n}{p^3}\rfloor +\dots$

样例

---

计算 $n!=1\times 2\times 3\times \cdots \times n$ 中包含多少个质因子 $p$：

• 第一项 $\lfloor \frac{n}{p}\rfloor$ 统计了 $1$ 到 $n$ 中能被 $p$ 整除的数的个数。
• 第二项 $\lfloor \frac{n}{p^2}\rfloor$ 统计了能被 $p^2$ 整除的数（这些数在第一步中只被计入了一次 $p$，现在需要补上第二个 $p$）。
• 以此类推，直到 $p^k$ 超过 $n$。

应用

---

计算末尾0的个数

判定 $n!$ 末尾有多少个 $0$，等价于计算 $n!$ 中因子 $10$ 的幂次，即 $\min (E_2(n!),E_5(n!))$。由于 $5$ 比 $2$ 大，所以只需计算 $E_5(n!)$。

实现

using ll = long long;
 
ll count(ll n, ll p)
{
	ll res = 0;
	while(n > 0)
	{
		res += n / 5;
		n /= 5;
	}
	return res;
}

题目

2145. 求阶乘