Legendre定理 | #小苯的因子查询#

令 设 表示 的完全质因数分解后得到的 的指数。

则有： 其中 表示 的整数部分，可以理解为下取整。

—— 勒让德定理（Legendre） - 知乎

由于 的一个因子可以表示为其质因数的质数幂之积，当且仅当该因子关于2的幂为0时，该因子为奇数，否则该因子为偶数。那么只需要根据上式求出 ，那么任意因子关于 2 的质数应当在 之间，由于是均匀随机取数，因此所有情况概率相等，所以 即为答案，搭配线性求逆复杂度为

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    constexpr int N = 1E6 + 7, mod = 998244353;
  
    //线性求逆元
    vector<int> inv(N);
    inv[0] = inv[1] = 1;
    for (int i = 2; i < N; i++) {
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
    }

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int ans = 0;
      
        //分解 n! 关于 2 的指数
        for (int i = 2; i <= n; i <<= 1) {
            ans += n / i;
        }
        cout << inv[ans + 1] << ' ';
    }cout << '\n';

}