题解 | 牛牛的k合因子数

#include<iostream>
#include<vector>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> pri;    // 质数表
    vector<bool>f(n+1); // f[i]=true 表示 i不是质数
    vector<int> d(n+1), p(n+1), e(n+1), ans(n+1);
    // d[i] -> i的因子个数（包含1）
    // p[i] -> i的质因子个数
    // e[i] -> i的最小质因子指数
    p[1] = e[1] = 0;
    f[1] = true;
    d[1] = 1; 
    
    // 线性筛（欧拉筛）
    for (int i = 2; i <= n; i++) {
        if (!f[i]) {
            pri.push_back(i);
            p[i] = e[i] = 1;
            d[i] = 2;
        }

        int k = d[i] - p[i] - 1;  // i的合数因子个数
        ans[k]++;

        for (int q : pri) {
            if (1LL*i*q > n) break;
            int x = i*q;
            f[x] = true;
            if (i % q == 0) {  // 找出 i 的最小质因子，此时也是 i*q 的最小质因子
                p[x] = p[i];
                e[x] = e[i] + 1;
                d[x] = d[i] / (e[i]+1) * (e[i]+2);
                break;  // 大于最小质因子的质数都无需处理
            }
            // 当 q 小于 i 的最小质因子时才会进入下列语句，说明 q 是 i*q 的最小质因子
            e[x] = 1;
            p[x] = p[i] + 1;
            d[x] = d[i] * 2;
        }
    }

    for (int i = 1, k; i <= m; i++)
        cin >> k, cout << ans[k] << '\n';
    return 0;
}