UVa 11802 All Your Bases Belong to Us

题目描述

给定两个非负整数 $n$ 和 $k$，求有多少个不同的进制 $b$（$b\ge 2$），使得 $n!$ 在 $b$ 进制下末尾恰好有 $k$ 个零。

输入格式

输入第一行包含一个正整数 $T$（$T\le 10000$），表示测试用例数。
接下来 $T$ 行，每行两个整数 $n$ 和 $k$，满足 $n\le 10^{15}$，$1\le k\le 10^{15}$，并且保证 $n/k<500$。

输出格式

对于每个测试用例，输出一行，格式为 Case X: Y，其中 $X$ 是测试用例编号（从 $1$ 开始），$Y$ 是答案对 $1000000007$ 取模后的值。

样例

输入

5
10 2
10 3
10 4
10 5
10 8

输出

Case 1: 24
Case 2: 0
Case 3: 4
Case 4: 0
Case 5: 1

题目分析

本题是经典问题“阶乘末尾零”的逆向版本。已知 $n!$ 在十进制下的末尾零个数由因子 $10=2\times 5$ 决定，更一般地，在进制 $b$ 中，若 $b=\prod p_i^{e_i}$，则 $n!$ 在 $b$ 进制下末尾零的个数为

$$\underset{i}{\min }\lfloor \frac{v_{p_i}(n!)}{e_i}\rfloor ,$$

其中 $v_p(n!)$ 表示 $n!$ 中质因子 $p$ 的指数。题目要求这个最小值恰好等于 $k$。

直接枚举 $b$ 的范围显然不可行（$b$ 可以大到 $n!$ 本身）。需要利用 $n/k<500$ 这一关键条件。因为若某个质数 $p>n/k+1$，则 $v_p(n!)\le n/(p-1)<k$，这样的质数不可能在 $b$ 中出现（否则指数 $e_i\ge 1$ 会导致最小值小于 $k$）。因此，只需考虑所有不超过 $500$ 的质数，问题规模大幅缩小。

解题思路

定义与符号

设 $v_p=v_p(n!)$。对于任意正整数 $K$，定义 $f(K)$ 为满足“末尾零个数至少为 $K$”的进制数（包括 $b=1$ 这个平凡情况）的个数。根据上述最小值的条件，$b$ 的质因数分解中，每个质因子 $p$ 的指数 $e_p$ 必须满足

$$\lfloor \frac{v_p}{e_p}\rfloor \ge K⟺e_p\le \lfloor \frac{v_p}{K}\rfloor .$$

因此，每个 $p$ 可选的指数范围为 $0,1,\dots ,\lfloor v_p/K\rfloor$，其中 $0$ 表示该质因子不出现。独立选择各质因子的指数即可确定一个 $b$（注意 $b=1$ 对应所有指数均为 $0$），所以

$$f(K)=\prod _{p:v_p\ge K}\left(\lfloor \frac{v_p}{K}\rfloor +1\right).$$

这里乘积中仅包含满足 $v_p\ge K$ 的质数，因为若 $v_p<K$，则 $\lfloor v_p/K\rfloor =0$，只有指数 $0$ 可选，因子为 $1$，不贡献。

容斥求恰好 $k$ 个零

令 $g(K)$ 表示满足“末尾零个数恰好为 $K$”的进制数（$b\ge 2$）。显然，恰好为 $k$ 的个数等于至少为 $k$ 的个数减去至少为 $k+1$ 的个数：

$$g(k)=\left(f(k)-1\right)-\left(f(k+1)-1\right)=f(k)-f(k+1).$$

因为 $f(K)$ 包含了 $b=1$，而题目要求 $b\ge 2$，减去 $1$ 后相减抵消，故答案即 $f(k)-f(k+1)$。

计算 $v_p(n!)$

利用勒让德公式：

$$v_p(n!)=\sum _{j\ge 1}\lfloor \frac{n}{p^j}\rfloor .$$

由于 $p\le 500$ 且 $n\le 10^{15}$，直接用循环累除计算即可，复杂度极小。

算法步骤

正确性证明

由上述分析，$f(K)$ 的计算正确反映了所有满足至少 $K$ 个零的进制数（包括 $b=1$）。由于 $b=1$ 在所有 $K$ 下都被计入，容斥后恰好得到 $b\ge 2$ 的个数。同时，由于 $n/k<500$，所有可能影响结果的质数都被覆盖，遗漏的质数不会改变乘积（其对应因子为 $1$）。

复杂度分析

• 预处理质数：$O(500\log \log 500)$。
• 每个测试用例：遍历不超过 $500$ 的质数个数（约 $95$ 个），每次计算 $v_p(n!)$ 的循环次数为 ${\log }_{p}n\le {\log }_{2}10^{15}\approx 50$。总操作量约为 $T\times 95\times 50$，当 $T=10000$ 时约为 $4.75\times 10^7$，完全可以接受。
• 时间复杂度：$O(T\cdot \pi (500)\cdot \log n)$，空间复杂度 $O(1)$。

代码实现

// All Your Bases Belong to Us
// UVa ID: 11802
// Verdict: Accepted
// Submission Date: 2026-06-20
// UVa Run Time: 0.050s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

typedef long long int64;
const int MOD = 1000000007;
const int MAXP = 500;

vector<int> getPrimes(int limit) {
vector<bool> isComp(limit + 1, false);
vector<int> primes;
for (int i = 2; i <= limit; ++i) {
if (!isComp[i]) {
primes.push_back(i);
if ((int64)i * i <= limit)
for (int j = i * i; j <= limit; j += i) isComp[j] = true;
}
}
return primes;
}

int main() {
vector<int> primes = getPrimes(MAXP);
int T;
scanf("%d", &T);
for (int caseNo = 1; caseNo <= T; ++caseNo) {
int64 n, k;
scanf("%lld %lld", &n, &k);
int64 prod1 = 1; // 对应 K = k
int64 prod2 = 1; // 对应 K = k+1
for (int p : primes) {
if (p > n) break;
int64 m = 0;
int64 tmp = n;
while (tmp) {
tmp /= p;
m += tmp;
}
if (m >= k) {
int64 cnt = m / k + 1;
prod1 = prod1 * (cnt % MOD) % MOD;
}
if (m >= k + 1) {
int64 cnt = m / (k + 1) + 1;
prod2 = prod2 * (cnt % MOD) % MOD;
}
}
int64 ans = (prod1 – prod2 + MOD) % MOD;
printf("Case %d: %lld\\n", caseNo, ans);
}
return 0;
}

总结

本题的关键在于利用 $n/k<500$ 的条件将需要考虑的质数范围缩小到 $500$ 以内，从而避免了枚举所有可能的进制 $b$。通过容斥原理，将“恰好为 $k$”转化为两个“至少为 $K$”的计数相减，而后者可以通过质因数分解和乘法原理轻松求出。

该解法体现了以下技巧：

• 缩小规模：利用数据范围限制过滤无关质数。
• 容斥转换：将精确条件转化为两个下界条件的差。
• 模运算：注意取模，避免溢出。

此方法对同类问题（如求阶乘在给定进制下末尾零个数的逆向问题）具有通用性，值得借鉴。