题解 | 小苯的因子查询

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
using ll = long long;
using vi = vector<int>;
const ll mod = 998244353;

ll ksm(ll x, ll n) {
    ll ans = 1;
    while (n > 0) {
        if (n & 1) {
            ans = ans * x % mod;
        }
        x = x * x % mod;
        n >>= 1;
    }
    return ans;
}
ll ny(ll x) {
    return ksm(x, mod - 2);
}

vi ans(1e6 + 10);

void solve() {
    int n;cin >> n;
    cout << ny(ans[n]) << " ";
}

/*

*/


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t = 1;
    cin >> t;
    ans[1] = 1;
    for (int i = 2;i <= 1e6;i++) {
        int ii = i;
        int cnt = 0;
        while (ii % 2 == 0) {
            ii /= 2;
            cnt++;
        }
        ans[i] = ans[i - 1] + cnt;
    }
    for (int i = 1; i <= t; i++) {
        //cout << "----Test " << i << "----" << endl;
        solve();
    }
    return 0;
}

规律题，打表1到20的逆元，可以看出样例1 2 3 4 5 6 7 8 9 10，分别对应1/1,1/2,1/2,1/4,1/4,1/5,1/5,1/8,1/8,1/9,可以看出只在偶数的时候分母会增加，奇数不变，再细看2，4，6，10增加了1，4增加了2，8增加了3，猜一个跟2的因子数有关，于是先预处理1e6的分母，然后通过逆元得到答案