1. 题目背景与核心需求
这道来自洛谷P3927的题目"SAC E#1 - 一道中档题 Factorial"看似简单，实则暗藏玄机。题目要求我们计算一个数N的阶乘在K进制表示下末尾有多少个连续的零。举个例子，5! = 120（十进制），末尾有1个零；而5!在二进制下是1111000，末尾有3个零。
这个问题的实际意义在于考察我们对数制转换和质因数分解的深入理解。在编程竞赛中，类似的问题经常作为考察数学思维和算法优化的经典题型出现。直接计算N!再转换进制显然不可行，因为当N较大时（比如1e18），不仅会溢出，计算时间也无法接受。
2. 数学原理剖析
2.1 进制与质因数的关系
任何进制K都可以表示为质因数的乘积。例如：
- 10 = 2 × 5
- 8 = 2³
- 12 = 2² × 3
在K进制下，末尾零的数量取决于N!的质因数分解中包含多少个完整的K的质因数组合。例如在十进制中，我们需要计算min(2的数量,5的数量)，因为10=2×5。
2.2 阶乘的质因数分解
对于一个质数p，N!中包含p的次数的计算公式是：
count = ⌊N/p⌋ + ⌊N/p²⌋ + ⌊N/p³⌋ + ...
这个公式的原理是：每隔p个数有一个p的倍数，每隔p²个数有一个p²的倍数（额外贡献一个p因子），以此类推。
2.3 问题转化步骤
- 对K进行质因数分解，得到所有质因数及其指数
- 对每个质因数p，计算它在N!中的出现次数count_p
- 对于K的每个质因数p，用count_p除以它在K中的指数，取最小值
3. C++实现详解
3.1 质因数分解实现
cpp复制vector<pair<long long, int>> prime_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;
}
这个函数的时间复杂度是O(√K)，对于K≤1e12的情况完全够用。注意处理k=1的特殊情况（虽然题目中k≥2）。
3.2 计算阶乘中质因数的个数
cpp复制long long count_factor(long long n, long long p) {
long long count = 0;
while (n > 0) {
n /= p;
count += n;
}
return count;
}
这个简洁的循环实现了我们前面提到的公式。例如count_factor(10,2)的计算过程：
- 第一轮：n=10/2=5, count=5
- 第二轮：n=5/2=2, count=5+2=7
- 第三轮：n=2/2=1, count=7+1=8
- 第四轮：n=1/2=0, 结束
3.3 主逻辑实现
cpp复制long long solve(long long n, long long k) {
auto factors = prime_factorize(k);
long long ans = LLONG_MAX;
for (auto [p, cnt] : factors) {
long long temp = count_factor(n, p) / cnt;
if (temp < ans) {
ans = temp;
}
}
return ans;
}
这里使用LLONG_MAX作为初始值，确保能找到最小值。对于每个质因数，我们计算其在N!中的出现次数除以它在K中的指数，取所有结果的最小值。
4. 边界情况与优化技巧
4.1 特殊情况的处理
- K=1：虽然题目保证k≥2，但好的习惯是处理边界
- N=0或1：0!和1!都等于1，任何进制下末尾零都是0
- K是质数：此时只需要计算N!中K的个数
- K=p^m：当K是单一质数的幂时，直接计算count/p的指数
4.2 性能优化
- 提前终止循环：在质因数分解时，当k变为1时可以提前终止
- 二分搜索上界：对于极大的N和小的p，可以二分搜索最大的m使得p^m≤N
- 记忆化：如果需要多次计算，可以缓存质因数分解结果
4.3 常见错误与调试
- 整数溢出：使用long long而非int，特别是N和K可能很大
- 循环条件错误：质因数分解时i*i<=k而非i<=k
- 最小值初始化：ans应初始化为足够大的值而非0
- 除零错误：确保cnt不为零（质因数分解保证）
5. 完整AC代码实现
cpp复制#include <iostream>
#include <vector>
#include <climits>
using namespace std;
vector<pair<long long, int>> prime_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_factor(long long n, long long p) {
long long count = 0;
while (n > 0) {
n /= p;
count += n;
}
return count;
}
long long solve(long long n, long long k) {
auto factors = prime_factorize(k);
long long ans = LLONG_MAX;
for (auto [p, cnt] : factors) {
long long temp = count_factor(n, p) / cnt;
if (temp < ans) {
ans = temp;
}
}
return ans;
}
int main() {
long long n, k;
cin >> n >> k;
cout << solve(n, k) << endl;
return 0;
}
6. 算法复杂度分析
- 质因数分解：O(√K)
- 计算每个质因数的个数：O(log_p N) 对每个质因数p
- 总体复杂度：O(√K + π(K) * log N)，其中π(K)是K的不同质因数个数
对于K≤1e12，N≤1e18的典型数据范围，这个算法完全可以在O(1)秒内完成计算。
7. 同类问题扩展
掌握了这道题的解法后，可以解决许多类似问题：
- 十进制下的阶乘末尾零：即K=10的特殊情况
- 改变进制求零的个数：如十六进制(K=16=2⁴)
- 组合数末尾零：计算C(n,m)在K进制下的末尾零
- 乘积末尾零：给定数组，计算乘积在K进制下的末尾零
提示：在竞赛中遇到类似问题时，先考虑将问题转化为质因数分解的形式，再寻找高效的计算方法，避免直接计算大数。
这道题教会我们的不仅是具体的解法，更重要的是一种将复杂问题分解为质因数相关子问题的思维方式。在实际编程竞赛中，这种数学思维往往比单纯的编程技巧更为关键。