NC229685 - 模板题【线性筛求积性函数】

题意

求正整数的所有正因数个数，次询问

数据范围

思路

不然发现一个正整数的正因数个数就是一个积性函数，那么我们可以预处理每个数字的正因数个数即可，

用上欧拉筛求积性函数来预处理

代码中表示这个数字的第一个质因数出现几次

或者也可以直接求，而不需要预处理（详情情况代码中的Solution 1）

代码

/**
 *    author: andif
 *    created: 29.09.2023 15:52:32
**/
#include<bits/stdc++.h>
using namespace std;

#define de(x) cerr << #x << " = " << x << endl
#define dd(x) cerr << #x << " = " << x << " "
#define rep(i, a, b) for(int i = a; i < b; ++i)
#define per(i, a, b) for(int i = a; i > b; --i)
#define mt(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)a.size()
#define fi first
#define se second
#define qc ios_base::sync_with_stdio(0);cin.tie(0)
#define eb emplace_back
#define all(a) a.begin(), a.end()
using ll = long long;
using db = double;
using pii = pair<int, int>;
using pdd = pair<db, db>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
const db eps = 1e-9;
const int N = 1e7 + 3;

int kpow(int a, int b) {
    int ret = 1;
    while(b) {
        if (b & 1) ret = ret * a;
        a = a * a;
        b >>= 1;
    }
    return ret;
}

int calc_f(int p, int a) { // 计算f[p ^ a]
    return a + 1;
}

void init(vi& f) {
    vi primes, is_primes(N, 1);
    vi cnt(N);
    is_primes[1] = 0;
    f[1] = 1; cnt[1] = 0;
    for (int i = 2; i < N; ++i) {
        if (is_primes[i]) {
            primes.eb(i);
            cnt[i] = 1;
            f[i] = 2;
        }
        for (int j = 0; j < sz(primes) && i * primes[j] < N; ++j) {
            is_primes[i * primes[j]] = 0;
            if (i % primes[j] == 0) {
                cnt[i * primes[j]] = cnt[i] + 1;
                f[i * primes[j]] = f[i] / calc_f(primes[j], cnt[i]) * calc_f(primes[j], cnt[i * primes[j]]);
                // int pa = kpow(primes[j], cnt[i * primes[j]]);
                // if (pa == i * primes[j]) {
                //     f[pa] = f[pa / primes[j]] + 1;
                // } else {
                //     f[i * primes[j]] = f[pa] * f[i * primes[j] / pa];
                // }
                break;
            }
            f[i * primes[j]] = f[i] * f[primes[j]];
            cnt[i * primes[j]] = 1;
        }
    }
}

int main() {
    qc;
    // solution 1
    // int q; cin >> q;
    // while(q--) {
    //     int n; cin >> n;
    //     int ans = 1;
    //     for (int i = 2; i * i <= n; ++i) {
    //         if (n % i == 0) {
    //             int c = 0;
    //             while(n % i == 0) {
    //                 c++;
    //                 n /= i;
    //             }
    //             ans *= (c + 1);
    //         }
    //     }
    //     if (n > 1) ans *= 2;
    //     cout << ans << '\n';
    // }
    // solution 2
    int q; cin >> q;
    vi f(N);
    init(f);
    while(q--) {
        int n; cin >> n;
        cout << f[n] << '\n';
    }
    return 0;
}