C++如何判断一个整数是否为阶乘数-C++-PHP中文网

阶乘数是等于某个非负整数k的阶乘（k!）的正整数，如1、2、6、24等；因64位long long最大支持20!（约2.4e18），故只需预计算0!至20!共21个值存入哈希集合，配合溢出防护（如用llong_max/k检查）实现o(1)判定。

c++如何判断一个整数是否为阶乘数

什么是阶乘数，以及为什么不能直接暴力枚举所有阶乘

阶乘数是指某个正整数 n 满足存在整数 k ≥ 0，使得 n == k!。比如 1（= 0! 或 1!）、2（= 2!）、6（= 3!）、24（= 4!）都是阶乘数；而 5、7、10 不是。

看似可以预计算所有可能的 k! 存进集合再查，但要注意：64 位有符号整数最大值约是 9.2e18，而 21! 已经超过 5.1e19，20! 是 2432902008176640000（约 2.4e18），刚好在 long long 范围内；21! 会溢出。所以实际只需预生成 0! 到 20! 共 21 个数——再多就不是 long long 能表示的合法输入了。

用预计算 + unordered_set 快速判断

最实用的方法是把所有不溢出的阶乘值预先算好、存进 std::unordered_set<long long></long>，然后用 count() 查。时间复杂度 O(1)，且避免运行时重复计算或溢出风险。

常见错误是边循环边算阶乘、不检查溢出，导致未定义行为（比如 21! 计算时整数溢出，结果变成负数或零，后续误判）。

预计算必须在编译期或程序启动时完成，且每一步都要检查乘法是否溢出
推荐用 std::numeric_limits<long long>::max()</long> 做除法检查：if (current > LLONG_MAX / next_k) break;
0! 和 1! 都是 1，但只存一次即可；集合自动去重
注意：输入可能是负数，阶乘数定义域是自然数，负数直接返回 false

static const std::unordered_set<long long> factorial_set = []{
    std::unordered_set<long long> s;
    long long f = 1;
    s.insert(f); // 0! = 1
    for (int k = 1; k  LLONG_MAX / k) break; // 溢出防护
        f *= k;
        s.insert(f);
    }
    return s;
}();</long></long>

手写迭代验证（适合不想用哈希表的场景）

如果输入范围受限（比如已知 n 在 [0, 1e18] 内），或者你只想写一个纯函数、避免全局状态，可以用迭代方式从 k = 0 开始累乘，边算边比：

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

先特判 n → false
n == 1 → true（对应 0! 和 1!）
从 k = 2 开始，维护当前阶乘值 fact，每次 fact *= k，若 fact == n 返回 true，若 fact > n 就停止（因为阶乘严格递增）
必须在乘法前检查溢出，否则 fact * k 溢出后比较失效

示例逻辑：

bool isFactorial(long long n) {
    if (n  n / k) return false; // 防溢出：fact * k > n ⇒ 不可能匹配
        fact *= k;
        if (fact == n) return true;
        if (fact > n) return false;
    }
}

注意 int 和 long long 的边界差异

如果函数签名用的是 int，那最多只用算到 12! = 479001600（13! 超过 INT_MAX ≈ 2.1e9）。此时预计算集合只需 14 个元素（0! 到 13!），但 13! 已溢出，所以实际有效上限是 12!。

关键点在于：**判断类型决定安全阶乘上限**：

int：安全上限 k = 12（12! = 479001600）
long long：安全上限 k = 20（20! = 2432902008176640000）
别假设 unsigned long long 能多撑几轮——21! 仍超其范围（约 1.4e19 > 1.8e19？错，ULLONG_MAX 是 1.8e19，但 21! 是 5.1e19，照样溢出）