问题分析

我们需要找到最大的非负整数 $x$，使得 $n!$ 能被 $k^x$ 整除。即：

$$n! \equiv 0 \pmod{k^x}$$

这是一个经典的数论问题，涉及阶乘的质因数分解和整除性。

算法思路

核心思想：勒让德公式 + 质因数分解

利用勒让德公式计算 $n!$ 中每个质因数的指数，然后根据 $k$ 的质因数分解来确定最大的 $x$。

关键数学原理

1. 质因数分解：将 $k$ 分解为质因数的乘积

   $$k = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$$

2. 勒让德公式：$n!$ 中质数 $p$ 的指数为

   $$v_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots $$

3. 最大指数：对于每个质因数 $p_i$，$n!$ 中最多能提供 $\frac{v_{p_i}(n!)}{e_i}$ 个 $k$ 的因子

最终答案

$$x_{\text{max}} = \min_{1 \leq i \leq r} \left\lfloor \frac{v_{p_i}(n!)}{e_i} \right\rfloor $$

代码详解

1. 主循环框架

for (; ~scanf("%lld%lld", &N, &K);) {
    ans = N;  // 初始化答案为n，这是x的最大可能值
    
    Int k = K;
    // 对k进行质因数分解
    for (Int p = 2; p * p <= k; ++p)
        if (k % p == 0) {
            Int e = 0;
            // 计算质因数p的指数
            do {
                ++e;
                k /= p;
            } while (k % p == 0);
            
            check(p, e);  // 检查该质因数对答案的限制
        }
    
    // 处理剩余的质因数（k本身是质数的情况）
    if (k > 1) {
        check(k, 1);
    }
    
    printf("%lld\n", ans);
}

2. 核心函数 check

void check(Int p, Int e) {
    Int val = 0;
    // 计算n!中质因数p的指数（勒让德公式）
    for (Int n = N; n /= p;)
        val += n;
    
    // 更新答案：取最小值
    chmin(ans, val / e);
}

勒让德公式的实现技巧：

for (Int n = N; n /= p;)
    val += n;

这等价于：

$$val = \left\lfloor \frac{N}{p} \right\rfloor + \left\lfloor \frac{N}{p^2} \right\rfloor + \left\lfloor \frac{N}{p^3} \right\rfloor + \cdots $$

算法正确性

数学证明

设 $k = \prod p_i^{e_i}$，那么：

$$k^x = \prod p_i^{e_i x}$$

$n!$ 能被 $k^x$ 整除的充要条件是对于每个质因数 $p_i$：

$$v_{p_i}(n!) \geq e_i x$$

因此：

$$x \leq \frac{v_{p_i}(n!)}{e_i} \quad \text{对所有} i$$

取最小值得到最大可能的 $x$。

边界情况处理

1. $k = 1$：题目保证 $k > 1$
2. $n < k$：算法自然处理，答案可能为0
3. 大数运算：使用 long long 避免溢出

复杂度分析

时间复杂度

• 质因数分解：$O(\sqrt{k})$，由于 $k \leq 10^{13}$，$\sqrt{k} \leq 10^{6.5}$，可以接受
• 勒让德公式计算：对于每个质因数 $p$，需要 $O(\log_p n)$ 次除法
• 总复杂度：在数据范围内完全可行

空间复杂度

• $O(1)$：只需要常数个变量

算法优化

1. 质因数分解优化

• 只需要试除到 $\sqrt{k}$
• 使用 p * p <= k 避免浮点数运算

2. 勒让德公式计算优化

• 使用整数除法，避免浮点精度问题
• 循环 while (n /= p) 简洁高效

3. 内存优化

• 不需要存储所有质因数，实时处理

总结

本题通过结合质因数分解和勒让德公式，优雅地解决了阶乘整除性问题。算法的核心优势在于：

1. 数学严谨：基于数论经典公式
2. 高效实现：复杂度在数据范围内完全可行
3. 代码简洁：核心算法只有十几行代码
4. 鲁棒性强：正确处理各种边界情况

该解法体现了数论知识在算法竞赛中的重要作用，展示了如何将数学理论转化为高效的程序实现。