题解：AT_abc400_e [ABC400E] Ringo's Favorite Numbers 3

2huk · 2025-04-06 09:12:45 · 题解

幸运数字一定能被表示成 p^{2a}q^{2b} 的形式，其中 p,q 是质数。

注意到这东西等于 (p^aq^b)^2。那很好了，p^{2a}q^{2b} \le n 转化成了 p^aq^b \le \sqrt n，也就是说幸运数字的数量是 \sqrt n 级别的。

首先把质数筛出来。枚举质数 p_i，枚举指数 a，将所有这样的不超过 10^6 的 p_i^a 存起来。

将存起来的 p_i^a 排序得到序列 A。注意到序列 A 中没有重复数字，且每个数都不超过 10^6，所以 A 的长度不超过 10^6，所以上面操作的复杂度是正确的。

枚举 i<j，将不超过 10^6 的 A_i \times A_j 存起来。

将存起来的 A_i \times A_j 排序得到序列 B。注意到序列 B 中没有重复数字，且每个数都不超过 10^6，所以 B 的长度不超过 10^6，所以上面操作的复杂度是正确的。

一个小问题是 B 中可能存在 8,16 这种不对劲的数字。这是因为 A_i \times A_j 中 A_i,A_j 可能对应同一个质数底数 p_i。而这样错误的 B_i 肯定也在 A 中出现过，那很好了，判断一下删掉即可。

然后查询时在 B 中二分就做完了。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e6 + 10;

int p[N], cnt;
bool st[N];
vector<int> vec;
vector<int> res;
set<int> S;

void init() {
    for (int i = 2; i < N; ++ i ) {
        if (!st[i]) p[ ++ cnt] = i;
        for (int j = 1; p[j] <= (N - 1) / i; ++ j ) {
            st[p[j] * i] = true;
            if (i % p[j] == 0) break;
        }
    }

    for (int i = 1; i <= cnt; ++ i ) {
        for (int x = p[i]; x < N; x *= p[i]) {
            vec.push_back(x);
            S.insert(x);
        }
    }

    sort(vec.begin(), vec.end());

    for (int i = 0; i < vec.size(); ++ i )
        for (int j = i + 1; j < vec.size(); ++ j ) {
            int x = vec[i] * vec[j];
            if (x < N) {
                if (!S.count(x)) res.push_back(x);
            } else break;
        }

    sort(res.begin(), res.end());
}

int solve() {
    int x;
    cin >> x;
    x = sqrtl(x);
    int ans = *(upper_bound(res.begin(), res.end(), x) - 1);
    return ans * ans;
}

signed main() {
    init();
    int T;
    cin >> T;
    while (T -- ) cout << solve() << '\n';
    return 0;
}