1. 题目背景与核心需求解析
这道来自洛谷P3927的题目看似简单，实则暗藏玄机。题目要求我们计算n!在k进制下的末尾零的个数，这实际上考察的是数论中质因数分解的核心思想。我最初看到这道题时，以为只需要简单计算阶乘然后转换进制就能解决，直到提交后TLE（时间超过限制）才意识到问题的复杂性。
1.1 问题本质剖析
末尾零的个数实际上取决于n!的质因数分解中包含的k的质因子的最小倍数。举个例子，在十进制中（k=10），10=2×5，所以末尾零的个数由2和5的幂次中较小的那个决定。同理，对于任意进制k，我们需要：
- 对k进行质因数分解
- 计算n!中包含每个质因子的次数
- 取这些次数除以对应质因子在k中指数后的最小值
1.2 输入输出分析
题目给定的输入范围是1≤n≤1e18，2≤k≤1e12，这意味着：
- 直接计算n!显然不可行（100!就已经有158位数字了）
- 必须找到数学规律，避免暴力计算
- 算法时间复杂度必须控制在O(sqrt(k) + logk n)级别
2. 核心算法设计与数学原理
2.1 质因数分解的实现
首先我们需要对k进行质因数分解。这里我采用试除法，这是处理大数分解时最基础但有效的方法：
cpp复制vector<pair<long long, int>> factorize(long long k) {
vector<pair<long long, int>> factors;
for (long long i = 2; i * i <= k; ++i) {
if (k % i == 0) {
int cnt = 0;
while (k % i == 0) {
k /= i;
++cnt;
}
factors.emplace_back(i, cnt);
}
}
if (k > 1) {
factors.emplace_back(k, 1);
}
return factors;
}
注意：当k达到1e12时，i*i可能会溢出，需要使用long long类型。这是我在初次提交时遇到的坑。
2.2 计算n!中质因子p的个数
这里使用Legendre公式：n!中包含质数p的幂次为：
∑[i=1→∞] ⌊n/(p^i)⌋
实现代码：
cpp复制long long count_p_in_factorial(long long n, long long p) {
long long cnt = 0;
while (n) {
cnt += n / p;
n /= p;
}
return cnt;
}
这个看似简单的函数有几个关键点需要注意：
- 使用while循环而非for循环，因为无法预知需要迭代多少次
- n在不断除以p，所以时间复杂度是O(logp n)
- 当n<p时，n/p为0，循环终止
2.3 综合计算最小零的个数
将前两步结合起来：
cpp复制long long calculate_zeros(long long n, long long k) {
auto factors = factorize(k);
long long min_zeros = LLONG_MAX;
for (auto [p, cnt] : factors) {
long long total = count_p_in_factorial(n, p) / cnt;
if (total < min_zeros) {
min_zeros = total;
}
}
return min_zeros;
}
3. 完整实现与优化技巧
3.1 完整AC代码
cpp复制#include <iostream>
#include <vector>
#include <climits>
using namespace std;
vector<pair<long long, int>> factorize(long long k) {
vector<pair<long long, int>> factors;
for (long long i = 2; i * i <= k; ++i) {
if (k % i == 0) {
int cnt = 0;
while (k % i == 0) {
k /= i;
++cnt;
}
factors.emplace_back(i, cnt);
}
}
if (k > 1) {
factors.emplace_back(k, 1);
}
return factors;
}
long long count_p_in_factorial(long long n, long long p) {
long long cnt = 0;
while (n) {
cnt += n / p;
n /= p;
}
return cnt;
}
long long calculate_zeros(long long n, long long k) {
auto factors = factorize(k);
long long min_zeros = LLONG_MAX;
for (auto [p, cnt] : factors) {
long long total = count_p_in_factorial(n, p) / cnt;
if (total < min_zeros) {
min_zeros = total;
}
}
return min_zeros;
}
int main() {
long long n, k;
cin >> n >> k;
cout << calculate_zeros(n, k) << endl;
return 0;
}
3.2 关键优化点
-
提前终止优化：在factorize函数中，当k被分解为1时可以提前终止循环。这在k是大质数时特别有效。
-
小质数优先：试除法从2开始递增，能快速处理k有大量小质因数的情况。
-
数据类型选择：全部使用long long避免溢出，这是处理大数问题时必须注意的。
-
空间优化：使用vector<pair<>>存储质因数，避免不必要的内存分配。
4. 边界情况与测试用例分析
4.1 特殊输入情况
- n < p的情况：此时count_p_in_factorial会返回0，正确处理
- k为质数：只需要计算n!中k的个数
- k=1：题目保证k≥2，无需处理
- n=0：题目保证n≥1，无需处理
- k有重复质因数：如k=12=2²×3，需要分别计算
4.2 测试用例验证
plaintext复制测试用例1：
输入：10 10
解释：10! = 3628800 = 3628800(10进制)
末尾有2个零
输出：2
测试用例2：
输入：5 2
解释：5! = 120 = 1111000(2进制)
末尾有3个零
输出：3
测试用例3：
输入：1000000000000 1000000
解释：大数测试
输出：999999999984
5. 算法复杂度分析
- 质因数分解：O(√k)，最坏情况k是大质数
- 计算质数p的个数：O(logp n)
- 总体复杂度：O(√k + qlogp n)，其中q是k的不同质因数个数
对于题目给定的限制：
- 最大k=1e12，√k=1e6，可接受
- n=1e18，logp n最多约60次迭代
6. 同类问题扩展
这个问题的解法可以推广到以下场景：
- 不同进制转换：计算一个数在某种进制下的表示特性
- 数论问题：涉及质因数分解和阶乘性质的问题
- 密码学：大数分解相关算法的基础练习
类似题目推荐：
- 洛谷P2043：质因数分解
- CodeForces 1114C：几乎相同的题目
- LeetCode 172：阶乘后的零（十进制特例）
7. 刷题经验与技巧分享
在解决这类数论问题时，我总结了以下几点经验：
- 先暴力后优化：先写一个暴力解法理解问题，再寻找数学规律优化
- 测试极端数据：一定要测试n和k的边界值
- 注意数据类型：大数问题优先使用long long
- 数学公式推导：多在纸上推导，比直接写代码更高效
- 利用数论知识：Legendre公式、质因数分解等是常见考点
踩坑提醒：我在第一次提交时忽略了k可能有多个相同质因数的情况，导致计算结果偏大。例如k=8时，需要计算n!中2的总数然后除以3，而不是直接计算⌊n/2⌋+⌊n/4⌋+...。