题解 | #小苯的因子查询#

核心思路

1. 因子总数： 首先需要知道 的因子总数 。
2. 奇数因子总数： 其次需要知道 的奇数因子总数 。
3. 概率： 所求概率即为：
4. 模运算： 最终结果需要以 的形式输出，其中 。

1. 阶乘的质因数分解

首先，将 进行标准质因数分解： 其中 是小于等于 的最大质数。

指数 的计算： 根据 Legendre's Formula（勒让德公式），质数 在 的分解中的指数 为：

2. 因子总数

的任意一个因子 都可以表示为： 其中 。

因子总数 为每个指数选择方案数的乘积：

3. 奇数因子总数

一个数是奇数，当且仅当它不能被 2 整除。 对于 的因子 要是奇数，它的质因数分解中 的指数 必须为 。 其中 (只有 1 种选择)，且对于所有奇质数 ，仍有 。

因此，奇数因子总数 为：

4. 概率计算

所求概率 为：

代入 ，我们得到：

最终结果：

其中 是质数 2 在 的质因数分解中的指数，即：

实施步骤与优化

1. 预处理 ： 对于每个给定的 ，我们需要计算 。这个求和只需要计算到 为止。

   • 且 。
   • 预先计算所有 的 是不现实的，因为 很大。
   • 优化： 随 单调不减，且 ，其中 是 中因子 2 的个数。
     • 的上界是 ，我们可以用前缀和的思想，线性预处理 直到 。

2. 预处理逆元： 答案是 。我们需要计算 。

   • 由于 是一个质数，我们可以使用费马小定理计算乘法逆元：
   • 由于 ，最大的 约为 。
   • 在每次查询时使用快速幂计算逆元即可。

代码实现

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

constexpr static ll LIMIT = 1e6;
constexpr static ll MOD = 998244353;

ll power(ll a, ll b) {
    ll ans = 1LL;
    a %= MOD;
    while (b > 0) {
        if (b & 1) {
            ans = (ans * a) % MOD;
        }
        a = (a * a) % MOD;
        b >>= 1;
    }

    return ans;
}

ll modInv(ll a) {
    return power(a, MOD - 2);
}

int main() {
    int T;
    cin >> T;

    // 预处理
    vector<ll> E(LIMIT + 1);
    E[0] = 0;
    for (ll i = 1; i <= LIMIT; i++) {
        ll temp = i;
        ll v2 = 0;
        while (temp > 0 && (temp % 2) == 0) {
            v2++;
            temp /= 2;
        }
        E[i] = E[i - 1] + v2;
    }

    while (T--) {
        ll n;
        cin >> n;
        ll ans = modInv(E[n] + 1);
        cout << ans << " ";
    }
    cout << endl;
}