文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载本文讲解 cp-algorithms 仓库src/algebra/factorial-divisors.md中一个基础而重要的数论问题给定正整数 $n$ 与 $k$求最大的整数 $x$ 使得 $k^x$ 整除 $n!$即求 $k$ 在 $n!$ 的素因子分解中的指数。文章完整覆盖素数 $k$ 与合数 $k$ 两种情形的推导、C 实现与复杂度分析并结合仓库中 阶乘模 p、整数分解、二项式系数 等关联文档说明其实际应用。读完你将掌握该算法的证明思路、$O(\log_k n)$ 的实现以及它在一系列组合计数问题中的用途。问题定义与核心思路问题描述输入两个整数 $n$ 和 $k$找出最大的整数 $x$满足$$k^x \mid n!$$其中 $n! 1 \cdot 2 \cdot 3 \cdots (n-1) \cdot n$。一个显然但低效的暴力做法是算出 $n!$ 后不断除以 $k$。但这在 $n$ 稍大时就会因整数溢出或阶乘增长过快而不可行。本问题的正确解法不需要展开阶乘而是直接统计 $k$ 的每个素因子在 $n!$ 中出现了多少次。这也是本题被归入仓库src/algebra/目录的原因——它和 阶乘模 p、二进制幂 等一样是从阶乘与素因子角度解决数论与组合问题的基本工具。素数 $k$ 的情形Legendre 公式先考虑最简单也最核心的情形$k$ 是素数。此时问题等价于求素数 $k$ 在 $n!$ 的素因子分解中的指数。观察阶乘的显式展开$$n! 1 \cdot 2 \cdot 3 \ldots (n-1) \cdot n$$逐项统计 $k$ 的贡献第一轮统计乘积中每个 $k$ 的倍数都贡献一个因子 $k$即给答案 $1$。这样的元素共有 $\left\lfloor \dfrac{n}{k} \right\rfloor$ 个。第二轮统计每个 $k^2$ 的倍数都贡献第二个因子 $k$第一个因子 $k$ 已在上一轮被计入再给答案 $1$。这样的元素共有 $\left\lfloor \dfrac{n}{k^2} \right\rfloor$ 个。以此类推对每个 $i$每个 $k^i$ 的倍数额外贡献一个因子 $k$数量为 $\left\lfloor \dfrac{n}{k^i} \right\rfloor$ 个。把各轮贡献累加起来最终答案即著名的Legendre 公式$$\left\lfloor \dfrac{n}{k} \right\rfloor \left\lfloor \dfrac{n}{k^2} \right\rfloor \ldots \left\lfloor \dfrac{n}{k^i} \right\rfloor \ldots$$几点关键性质级数必然有限当 $k^i n$ 时$\left\lfloor \dfrac{n}{k^i} \right\rfloor 0$因此只需累加大约前 $\log_k n$ 项。时间复杂度$O(\log_k n)$。该公式正是 阶乘模 p 中计算素数 $p$ 在 $n!$ 中重数multiplicity所用方法的来源见下文算法在仓库中的关联实现一节。素数 $k$ 的实现上述累加过程可以写成一个极简的循环每次把 $n$ 除以 $k$把商累加到结果中。int fact_pow (int n, int k) { int res 0; while (n) { n / k; res n; } return res; }实现要点循环变量res依次累加 $\lfloor n/k \rfloor,\ \lfloor n/k^2 \rfloor,\ \lfloor n/k^3 \rfloor,\dots$当 $n$ 变为 $0$ 时自然终止。由于n在每次迭代中至少除以 $k \ge 2$迭代次数不超过 $\log_2 n$循环必然快速收敛。参数k在该函数中要求是素数若传入合数本函数计算的是某个因子被整除次数的中间量不能直接作为最终答案见下一节。手工演算示例以 $n 10,\ k 2$ 为例$10! 3628800 2^8 \cdot 3^4 \cdot 5^2 \cdot 7$所以最大 $x$ 应为 $8$。用公式验证$$\lfloor 10/2 \rfloor \lfloor 10/4 \rfloor \lfloor 10/8 \rfloor \lfloor 10/16 \rfloor \cdots 5 2 1 0 \cdots 8$$结果一致。合数 $k$ 的情形分解后取最小当 $k$ 是合数时不能把上一节的想法直接套用。原因在于$n!$ 中可能包含大量 $k$ 的某个素因子但包含另一个素因子的数量却很少此时 $k^x$ 中 $x$ 的大小受限于最稀缺的那个素因子。因此正确做法是先把 $k$ 分解为素因子幂的乘积$$k k_1^{p_1} \cdot k_2^{p_2} \cdots k_m^{p_m}$$记号中 $k_i$ 为互不相同的素数$p_i$ 为对应指数然后对每个素因子 $k_i$用上一节的算法求出它在 $n!$ 中出现的次数记作 $a_i$。此时$k_i^{p_i}$ 总共需要 $p_i \cdot x$ 个 $k_i$ 的因子才能整除 $k^x$于是对每个 $i$ 都要有$$p_i \cdot x \le a_i$$最终答案取所有素因子约束的下界$$\min_{i1 \ldots m} \left\lfloor \dfrac{a_i}{p_i} \right\rfloor$$文档中给出的公式为 $\min_{i1 \ldots m} \dfrac{a_i}{p_i}$由于 $a_i$ 是整数且 $k_i^{p_i} \mid k^x$ 要求 $x \le a_i / p_i$实际取整意义上的下界即为向下取整。完整流程示例求最大的 $x$ 使 $12^x \mid 20!$。分解 $k 12 2^2 \cdot 3^1$。求 $a_1$$2$ 在 $20!$ 中的指数 $ \lfloor 20/2 \rfloor \lfloor 20/4 \rfloor \lfloor 20/8 \rfloor \lfloor 20/16 \rfloor 10 5 2 1 18$。求 $a_2$$3$ 在 $20!$ 中的指数 $ \lfloor 20/3 \rfloor \lfloor 20/9 \rfloor 6 2 8$。取最小$\min(18/2,\ 8/1) \min(9,\ 8) 8$。即最大的 $x 8$。从结构上看是因子 $3$ 的稀缺性$8$ 个先触顶制约了 $x$。分解 $k$ 的实现方式合数情形需要把 $k$ 做素因子分解。这一步可使用仓库 整数分解 一文中的试除法trial divisionvectorlong long trial_division1(long long n) { vectorlong long factorization; for (long long d 2; d * d n; d) { while (n % d 0) { factorization.push_back(d); n / d; } } if (n 1) factorization.push_back(n); return factorization; }对返回的因子序列去重并统计每个素因子的指数 $p_i$随后对每个不同的素因子调用一次fact_pow(n, k_i)得到 $a_i$最后对所有 $i$ 计算 $\lfloor a_i / p_i \rfloor$ 并取最小值即可。复杂度与数值边界分析素数 $k$fact_pow每轮将 $n$ 缩小 $k$ 倍循环次数为 $\lfloor \log_k n \rfloor 1$时间复杂度 $O(\log_k n)$空间 $O(1)$。合数 $k$设 $k$ 有 $m$ 个不同素因子则总代价为 $O\left(m \cdot \log_k n\right)$ 加上分解 $k$ 的开销。当 $k \le 10^{18}$ 量级时$m$ 至多为十几个分解成本通常可忽略或使用更快的 Pollard rho 算法仓库src/algebra/factorization.md中提供了brent等实现。数值边界提醒上述 C 实现使用int。当 $n$ 较大时$\lfloor n/k \rfloor \lfloor n/k^2 \rfloor \cdots$ 的累加值可能超过 $2^{31}-1$此时应改用long long。仓库 阶乘模 p 中的multiplicity_factorial实现也给出了同样结构的循环写法。算法在仓库中的关联实现与应用与阶乘模 p 的关系本问题的核心公式正是 阶乘模 p 中计算素数 $p$ 在 $n!$ 中的重数所用的 Legendre 公式。该文档给出的实现如下int multiplicity_factorial(int n, int p) { int count 0; do { n / p; count n; } while (n); return count; }这与fact_pow逻辑等价用do-while先除后累加。在组合计数问题中修改后的阶乘 $n!_{%p}$即去掉所有因子 $p$ 后的乘积模 $p$与本问题的重数计算是配套使用的两个量前者给出模 $p$ 下的值后者给出 $p$ 的指数二者合起来才能正确处理带阶乘的分数表达式模素数幂。在组合数模素数幂计算中的应用仓库 二项式系数 的 Binomial coefficient modulo prime power 一节直接使用了本问题的方法对每个 $x!$记 $c(x)$ 为满足 $p^c \mid x!$ 的最大指数即 $c(x)$ 正是用 Legendre 公式计算出的 $\nu_p(x!)$。随后利用$$\binom{n}{k} \frac{g(n)}{g(k),g(n-k)},p^{,c(n) - c(k) - c(n-k)}$$把 $p$ 的因子部分从组合数中剥离出来其中 $g(x) x! / p^{c(x)}$ 与模数互素可求逆元。特别地若 $c(n) - c(k) - c(n-k) \ge b$则组合数模 $p^b$ 为 $0$。由此可以看出本问题是计算 $\binom{n}{k} \bmod p^b$、乃至模任意合数再配合 中国剩余定理的基石。典型应用场景汇总求末尾连续零的个数$10 2 \cdot 5$ 且 $5$ 在阶乘中的指数始终小于等于 $2$ 的指数因此 $n!$ 末尾零的个数就是 $\nu_5(n!)$用一次fact_pow(n, 5)即得。判断整除关系判断 $k^x \mid n!$ 是否成立即判断 $x$ 是否不超过上文算出的最大值。组合数模素数幂见 二项式系数 中的 $c(x)$ 计算。阶乘模 p 的配套计算见 阶乘模 p 中Multiplicity of $p$一节。仓库代码的组织与测试方式本仓库的 Markdown 文档中嵌入了大量可编译的代码块。以test/extract_snippets.py提取以 {.cpp file...} 标记的代码段并生成.h头文件再由test/test.sh用g -stdc17 -fsanitizeundefined编译并运行test/*.cpp测试。因此文档中的fact_pow等函数在设计上应保持为独立、无外部依赖的自包含函数这样既能被文档读者直接复制也能被测试体系无缝提取验证。这一约定对所有src/algebra/下的文档代码同样适用。扩展阅读阶乘模 p与本文公式互补讲解 $n! \bmod p$ 的计算及素数重数的应用。整数分解合数情形分解 $k$ 所需的方法含试除法与 Pollard rho 算法。二项式系数Legendre 公式在组合数模素数幂中的直接应用。二进制幂组合数模计算中求逆元所需的快速幂工具。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐OpenArk开源 Anti-Rootkit 工具实战OpenArk开源 Anti Rootkit 工具实战 上次排查一台有幽灵端口的机器端口表里有连到陌生外网 IP 的 TCP 连接任务管理器却找不到对文档教程知识库量子计算Shor算法大数分解的量子优势与经典算法对比量子计算Shor算法大数分解的量子优势与经典算法对比 量子计算Shor算法是量子计算领域最具革命性的突破之一它能够在多项式时间内分解大整数对现代密码学特文档教程知识库终极指南3种简单方法彻底解决Windows 10 PL2303驱动不兼容问题终极指南3种简单方法彻底解决Windows 10 PL2303驱动不兼容问题 还在为Windows 10系统下PL2303 USB转串口设备无法识别而烦恼吗文档教程知识库上一篇Spring Data MongoDB GeoJSON 应用实践指南下一篇Suricata异常策略配置详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
cp-algorithms 中阶乘素因子计数：用 Legendre 公式求 n! 中 k 的最大幂
文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载本文讲解 cp-algorithms 仓库src/algebra/factorial-divisors.md中一个基础而重要的数论问题给定正整数 $n$ 与 $k$求最大的整数 $x$ 使得 $k^x$ 整除 $n!$即求 $k$ 在 $n!$ 的素因子分解中的指数。文章完整覆盖素数 $k$ 与合数 $k$ 两种情形的推导、C 实现与复杂度分析并结合仓库中 阶乘模 p、整数分解、二项式系数 等关联文档说明其实际应用。读完你将掌握该算法的证明思路、$O(\log_k n)$ 的实现以及它在一系列组合计数问题中的用途。问题定义与核心思路问题描述输入两个整数 $n$ 和 $k$找出最大的整数 $x$满足$$k^x \mid n!$$其中 $n! 1 \cdot 2 \cdot 3 \cdots (n-1) \cdot n$。一个显然但低效的暴力做法是算出 $n!$ 后不断除以 $k$。但这在 $n$ 稍大时就会因整数溢出或阶乘增长过快而不可行。本问题的正确解法不需要展开阶乘而是直接统计 $k$ 的每个素因子在 $n!$ 中出现了多少次。这也是本题被归入仓库src/algebra/目录的原因——它和 阶乘模 p、二进制幂 等一样是从阶乘与素因子角度解决数论与组合问题的基本工具。素数 $k$ 的情形Legendre 公式先考虑最简单也最核心的情形$k$ 是素数。此时问题等价于求素数 $k$ 在 $n!$ 的素因子分解中的指数。观察阶乘的显式展开$$n! 1 \cdot 2 \cdot 3 \ldots (n-1) \cdot n$$逐项统计 $k$ 的贡献第一轮统计乘积中每个 $k$ 的倍数都贡献一个因子 $k$即给答案 $1$。这样的元素共有 $\left\lfloor \dfrac{n}{k} \right\rfloor$ 个。第二轮统计每个 $k^2$ 的倍数都贡献第二个因子 $k$第一个因子 $k$ 已在上一轮被计入再给答案 $1$。这样的元素共有 $\left\lfloor \dfrac{n}{k^2} \right\rfloor$ 个。以此类推对每个 $i$每个 $k^i$ 的倍数额外贡献一个因子 $k$数量为 $\left\lfloor \dfrac{n}{k^i} \right\rfloor$ 个。把各轮贡献累加起来最终答案即著名的Legendre 公式$$\left\lfloor \dfrac{n}{k} \right\rfloor \left\lfloor \dfrac{n}{k^2} \right\rfloor \ldots \left\lfloor \dfrac{n}{k^i} \right\rfloor \ldots$$几点关键性质级数必然有限当 $k^i n$ 时$\left\lfloor \dfrac{n}{k^i} \right\rfloor 0$因此只需累加大约前 $\log_k n$ 项。时间复杂度$O(\log_k n)$。该公式正是 阶乘模 p 中计算素数 $p$ 在 $n!$ 中重数multiplicity所用方法的来源见下文算法在仓库中的关联实现一节。素数 $k$ 的实现上述累加过程可以写成一个极简的循环每次把 $n$ 除以 $k$把商累加到结果中。int fact_pow (int n, int k) { int res 0; while (n) { n / k; res n; } return res; }实现要点循环变量res依次累加 $\lfloor n/k \rfloor,\ \lfloor n/k^2 \rfloor,\ \lfloor n/k^3 \rfloor,\dots$当 $n$ 变为 $0$ 时自然终止。由于n在每次迭代中至少除以 $k \ge 2$迭代次数不超过 $\log_2 n$循环必然快速收敛。参数k在该函数中要求是素数若传入合数本函数计算的是某个因子被整除次数的中间量不能直接作为最终答案见下一节。手工演算示例以 $n 10,\ k 2$ 为例$10! 3628800 2^8 \cdot 3^4 \cdot 5^2 \cdot 7$所以最大 $x$ 应为 $8$。用公式验证$$\lfloor 10/2 \rfloor \lfloor 10/4 \rfloor \lfloor 10/8 \rfloor \lfloor 10/16 \rfloor \cdots 5 2 1 0 \cdots 8$$结果一致。合数 $k$ 的情形分解后取最小当 $k$ 是合数时不能把上一节的想法直接套用。原因在于$n!$ 中可能包含大量 $k$ 的某个素因子但包含另一个素因子的数量却很少此时 $k^x$ 中 $x$ 的大小受限于最稀缺的那个素因子。因此正确做法是先把 $k$ 分解为素因子幂的乘积$$k k_1^{p_1} \cdot k_2^{p_2} \cdots k_m^{p_m}$$记号中 $k_i$ 为互不相同的素数$p_i$ 为对应指数然后对每个素因子 $k_i$用上一节的算法求出它在 $n!$ 中出现的次数记作 $a_i$。此时$k_i^{p_i}$ 总共需要 $p_i \cdot x$ 个 $k_i$ 的因子才能整除 $k^x$于是对每个 $i$ 都要有$$p_i \cdot x \le a_i$$最终答案取所有素因子约束的下界$$\min_{i1 \ldots m} \left\lfloor \dfrac{a_i}{p_i} \right\rfloor$$文档中给出的公式为 $\min_{i1 \ldots m} \dfrac{a_i}{p_i}$由于 $a_i$ 是整数且 $k_i^{p_i} \mid k^x$ 要求 $x \le a_i / p_i$实际取整意义上的下界即为向下取整。完整流程示例求最大的 $x$ 使 $12^x \mid 20!$。分解 $k 12 2^2 \cdot 3^1$。求 $a_1$$2$ 在 $20!$ 中的指数 $ \lfloor 20/2 \rfloor \lfloor 20/4 \rfloor \lfloor 20/8 \rfloor \lfloor 20/16 \rfloor 10 5 2 1 18$。求 $a_2$$3$ 在 $20!$ 中的指数 $ \lfloor 20/3 \rfloor \lfloor 20/9 \rfloor 6 2 8$。取最小$\min(18/2,\ 8/1) \min(9,\ 8) 8$。即最大的 $x 8$。从结构上看是因子 $3$ 的稀缺性$8$ 个先触顶制约了 $x$。分解 $k$ 的实现方式合数情形需要把 $k$ 做素因子分解。这一步可使用仓库 整数分解 一文中的试除法trial divisionvectorlong long trial_division1(long long n) { vectorlong long factorization; for (long long d 2; d * d n; d) { while (n % d 0) { factorization.push_back(d); n / d; } } if (n 1) factorization.push_back(n); return factorization; }对返回的因子序列去重并统计每个素因子的指数 $p_i$随后对每个不同的素因子调用一次fact_pow(n, k_i)得到 $a_i$最后对所有 $i$ 计算 $\lfloor a_i / p_i \rfloor$ 并取最小值即可。复杂度与数值边界分析素数 $k$fact_pow每轮将 $n$ 缩小 $k$ 倍循环次数为 $\lfloor \log_k n \rfloor 1$时间复杂度 $O(\log_k n)$空间 $O(1)$。合数 $k$设 $k$ 有 $m$ 个不同素因子则总代价为 $O\left(m \cdot \log_k n\right)$ 加上分解 $k$ 的开销。当 $k \le 10^{18}$ 量级时$m$ 至多为十几个分解成本通常可忽略或使用更快的 Pollard rho 算法仓库src/algebra/factorization.md中提供了brent等实现。数值边界提醒上述 C 实现使用int。当 $n$ 较大时$\lfloor n/k \rfloor \lfloor n/k^2 \rfloor \cdots$ 的累加值可能超过 $2^{31}-1$此时应改用long long。仓库 阶乘模 p 中的multiplicity_factorial实现也给出了同样结构的循环写法。算法在仓库中的关联实现与应用与阶乘模 p 的关系本问题的核心公式正是 阶乘模 p 中计算素数 $p$ 在 $n!$ 中的重数所用的 Legendre 公式。该文档给出的实现如下int multiplicity_factorial(int n, int p) { int count 0; do { n / p; count n; } while (n); return count; }这与fact_pow逻辑等价用do-while先除后累加。在组合计数问题中修改后的阶乘 $n!_{%p}$即去掉所有因子 $p$ 后的乘积模 $p$与本问题的重数计算是配套使用的两个量前者给出模 $p$ 下的值后者给出 $p$ 的指数二者合起来才能正确处理带阶乘的分数表达式模素数幂。在组合数模素数幂计算中的应用仓库 二项式系数 的 Binomial coefficient modulo prime power 一节直接使用了本问题的方法对每个 $x!$记 $c(x)$ 为满足 $p^c \mid x!$ 的最大指数即 $c(x)$ 正是用 Legendre 公式计算出的 $\nu_p(x!)$。随后利用$$\binom{n}{k} \frac{g(n)}{g(k),g(n-k)},p^{,c(n) - c(k) - c(n-k)}$$把 $p$ 的因子部分从组合数中剥离出来其中 $g(x) x! / p^{c(x)}$ 与模数互素可求逆元。特别地若 $c(n) - c(k) - c(n-k) \ge b$则组合数模 $p^b$ 为 $0$。由此可以看出本问题是计算 $\binom{n}{k} \bmod p^b$、乃至模任意合数再配合 中国剩余定理的基石。典型应用场景汇总求末尾连续零的个数$10 2 \cdot 5$ 且 $5$ 在阶乘中的指数始终小于等于 $2$ 的指数因此 $n!$ 末尾零的个数就是 $\nu_5(n!)$用一次fact_pow(n, 5)即得。判断整除关系判断 $k^x \mid n!$ 是否成立即判断 $x$ 是否不超过上文算出的最大值。组合数模素数幂见 二项式系数 中的 $c(x)$ 计算。阶乘模 p 的配套计算见 阶乘模 p 中Multiplicity of $p$一节。仓库代码的组织与测试方式本仓库的 Markdown 文档中嵌入了大量可编译的代码块。以test/extract_snippets.py提取以 {.cpp file...} 标记的代码段并生成.h头文件再由test/test.sh用g -stdc17 -fsanitizeundefined编译并运行test/*.cpp测试。因此文档中的fact_pow等函数在设计上应保持为独立、无外部依赖的自包含函数这样既能被文档读者直接复制也能被测试体系无缝提取验证。这一约定对所有src/algebra/下的文档代码同样适用。扩展阅读阶乘模 p与本文公式互补讲解 $n! \bmod p$ 的计算及素数重数的应用。整数分解合数情形分解 $k$ 所需的方法含试除法与 Pollard rho 算法。二项式系数Legendre 公式在组合数模素数幂中的直接应用。二进制幂组合数模计算中求逆元所需的快速幂工具。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐OpenArk开源 Anti-Rootkit 工具实战OpenArk开源 Anti Rootkit 工具实战 上次排查一台有幽灵端口的机器端口表里有连到陌生外网 IP 的 TCP 连接任务管理器却找不到对文档教程知识库量子计算Shor算法大数分解的量子优势与经典算法对比量子计算Shor算法大数分解的量子优势与经典算法对比 量子计算Shor算法是量子计算领域最具革命性的突破之一它能够在多项式时间内分解大整数对现代密码学特文档教程知识库终极指南3种简单方法彻底解决Windows 10 PL2303驱动不兼容问题终极指南3种简单方法彻底解决Windows 10 PL2303驱动不兼容问题 还在为Windows 10系统下PL2303 USB转串口设备无法识别而烦恼吗文档教程知识库上一篇Spring Data MongoDB GeoJSON 应用实践指南下一篇Suricata异常策略配置详解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
