输出 𝑛 ! 的不同因子的个数？ 输入 一个整数 𝑛 输出 输出 𝑛 ! 的因子个数 样例输入 复制 3 样例输出 复制 4 提示 1 <= 𝑛 <= 10 5 对于50%的数据，答案不超过longlong

要计算 \( n! \) 的因子个数，需要先对 \( n! \) 进行质因数分解。 设 \( n! \) 的质因数分解为： \[ n! = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k} \] 其中 \( p_i \) 是质数，\( a_i \) 是 \( p_i \) 在 \( n! \) 中的指数。 因子个数公式： \[ d(n!) = (a_1 + 1) \times (a_2 + 1) \times \dots \times (a_k + 1) \] 计算 \( a_i \)（勒让德公式）： \[ a_i = \left\lfloor \frac{n}{p_i} \right\rfloor + \left\lfloor \frac{n}{p_i^2} \right\rfloor + \left\lfloor \frac{n}{p_i^3} \right\rfloor + \dots \] 直到 \( p_i^t > n \)。 步骤： 1. 用筛法找出所有不超过 \( n \) 的质数。 2. 对每个质数 \( p \)，用勒让德公式计算指数 \( a \)。 3. 将所有 \( (a+1) \) 相乘得到答案。 注意： - \( n \) 最大为 \( 10^5 \)，答案可能很大，需要用 `long long` 或大整数。 - 对于 50% 的数据，答案在 `long long` 范围内。 C++ 代码实现： ```cpp #include <iostream> #include <vector> using namespace std; const int MOD = 1e9 + 7; // 如果要求模，可以加上 vector<int> getPrimes(int n) { vector<bool> isPrime(n + 1, true); vector<int> primes; for (int i = 2; i <= n; i++) { if (isPrime[i]) { primes.push_back(i); for (int j = i * 2; j <= n; j += i) { isPrime[j] = false; } } } return primes; } int main() { int n; cin >> n; vector<int> primes = getPrimes(n); long long ans = 1; for (int p : primes) { long long cnt = 0; long long power = p; while (power <= n) { cnt += n / power; power *= p; } ans *= (cnt + 1); // 如果取模： ans = ans * (cnt + 1) % MOD; } cout << ans << endl; return 0; } ``` 样例解释： 输入 `n = 3`， \( 3! = 6 = 2^1 \times 3^1 \) 因子个数 = \( (1+1) \times (1+1) = 4 \) 输出 `4`。 [2026-01-11 17:34:08 | AI问答 | 685点数解答]