题目描述

一个正整数 N 被称为 400 数，当且仅当它同时满足以下两个条件：

1. N 恰好有两个不同的质因数。
2. 对于 N 的每一个质因数 p，p 整除 N 的次数是偶数。换句话说，在 N 的质因数分解中，每个质因数的指数都是偶数。

需要处理 Q 个查询。每个查询给定一个整数 A，要求找出不超过 A 的最大的 400 数。题目保证在约束条件下，不超过 A 的 400 数总是存在的。

样例

输入:
5
404
36
60
1000000000000
123456789

输出:
400
36
36
1000000000000
123454321

说明第一个查询：
400 的质因数分解是 2^4 * 5^2。
1. 它恰好有两个不同的质因数：2 和 5。
2. 质因数 2 的指数是 4（偶数），质因数 5 的指数是 2（偶数）。
两个条件都满足，所以 400 是一个 400 数。
而 401, 402, 403, 404 都不是 400 数。因此，不超过 404 的最大 400 数是 400。

算法 (预处理 + 二分查找)

$O(M \log M + Q \log M)$ 其中 M = sqrt(max(A))

思路分析

1. 理解 400 数的性质:

   • 条件 2 “每个质因数的指数都是偶数” 是一个非常关键的性质。一个正整数 N，如果它的所有质因数的指数都是偶数，那么 N 一定是一个完全平方数。
   • 证明：设 N = p1^a1 * p2^a2 * ... * pk^ak 是 N 的标准质因数分解。如果所有 ai 都是偶数，即 ai = 2 * bi，那么 N = p1^(2*b1) * p2^(2*b2) * ... * pk^(2*bk) = (p1^b1 * p2^b2 * ... * pk^bk)^2。令 K = p1^b1 * p2^b2 * ... * pk^bk，则 N = K^2。
   • 结合条件 1 “N 恰好有两个不同的质因数”，这意味着 N = K^2 必须恰好有两个不同的质因数。
   • 一个数 N = K^2 的质因数与 K 的质因数是完全相同的。
   • 因此，一个数 N 是 400 数，当且仅当 N = K^2，并且 K 恰好有两个不同的质因数。

2. 转换问题:

   • 我们要找的是不超过 A 的最大 400 数 N。
   • 根据上面的分析，N 必须是 K^2 的形式，其中 K 有两个不同的质因数。
   • N <= A 意味着 K^2 <= A，即 K <= sqrt(A)。
   • 题目中 A 的最大值是 10^12，所以 K 的最大值是 sqrt(10^12) = 10^6。

3. 算法策略:

   • 由于 K 的范围 [1, 10^6] 相对较小，我们可以预处理所有可能的 K 值。
   • 预处理阶段:
     1. 遍历所有整数 k 从 1 到 10^6。
     2. 对于每个 k，找出它的所有不同质因数。
     3. 如果 k 恰好有两个不同的质因数，那么 N = k * k 就是一个 400 数。
     4. 将所有找到的 400 数 N 存储在一个列表（例如 vector<i64> Nums）中。
     5. 对这个列表 Nums 进行排序。
   • 查询阶段:
     1. 对于每个查询 A。
     2. 在排好序的列表 Nums 中，使用二分查找（或者 C++ 的 upper_bound）找到第一个 大于 A 的 400 数的位置 it。
     3. 因为题目保证了不超过 A 的 400 数一定存在，所以 it 不会是列表的开头。
     4. it 指向的元素的前一个元素 (*(it-1) 或 *std::prev(it)) 就是不超过 A 的最大 400 数。

4. 优化质因数分解:

   • 在预处理阶段，我们需要对 1 到 10^6 的每个数 k 进行质因数分解并计数。如果对每个 k 都独立进行试除法分解，效率不够高（大约 O(M * sqrt(M))，其中 M=10^6）。
   • 更高效的方法是使用线性筛（或普通埃氏筛）预处理出 1 到 M=10^6 每个数的最小质因数 minp[i]。
   • 有了 minp 数组，我们可以在 O(log k) 的时间内分解任何数 k <= M。具体方法是：当 k > 1 时，不断取出 p = minp[k]，并将 p 加入质因数集合，然后令 k = k / p，直到 k 变为 1。
   • 代码中正是使用了线性筛 (sieve 函数) 来预计算 minp 数组。

5. 代码实现细节:

   • sieve(M): 实现线性筛，填充 minp 数组和 primes 列表（虽然 primes 在后续分解中没直接用，但筛法会生成它）。
   • vector<i64> N;: 用来存储找到的 400 数 (K^2)。
   • 循环 for (int k = 1; k <= M; k++): 遍历所有可能的 K 值。
   • while (temp > 1) ... factors.insert(p); temp /= p;: 使用 minp 数组快速找到 k 的所有不同质因数，存入 set<int> factors (set 自动去重)。
   • if (factors.size() == 2): 判断 k 是否恰好有两个不同质因数。
   • N.push_back((i64)k * k);: 如果条件满足，将 k*k (注意使用 i64 防止溢出) 加入列表 N。
   • sort(N.begin(), N.end());: 对所有 400 数排序。
   • upper_bound(N.begin(), N.end(), A): 二分查找第一个大于 A 的元素。
   • it--; cout << *it << "\n";: 获取并输出前一个元素，即所求答案。

时间复杂度

1. 线性筛: O(M)，其中 M = 10^6。
2. 生成 400 数列表: 循环 M 次。每次循环内部，质因数分解需要 O(log k) 时间。总时间约为 O(M log M)。设找到的 400 数个数为 L (显然 L <= M)。
3. 排序: 对 L 个数排序，需要 O(L log L) 时间。
4. 查询: 共 Q 次查询，每次查询使用 upper_bound，需要 O(log L) 时间。总查询时间为 O(Q log L)。

总时间复杂度: O(M + M log M + L log L + Q log L)。由于 L <= M，可以简化为 O(M log M + Q log M)。
考虑到 M=10^6, Q=2*10^5，这个复杂度是完全可以通过的。

空间复杂度: O(M)，主要用于存储 minp 数组和 400 数列表 N。

C++ 代码

#include <bits/stdc++.h> // 引入所有标准库

using namespace std;
using i64 = long long; // 定义 i64 为 long long 的别名

std::vector<int> minp, primes; // minp[i] 存储 i 的最小质因数, primes 存储找到的素数

// 线性筛函数，预处理 1 到 n 的最小质因数
void sieve(int n) {
    minp.assign(n + 1, 0); // 初始化 minp 数组，大小为 n+1，初始值为 0
    primes.clear(); // 清空素数列表

    // 从 2 开始遍历到 n
    for (int i = 2; i <= n; i ++ ) {
        // 如果 minp[i] 为 0，说明 i 是素数
        if (minp[i] == 0) {
            minp[i] = i; // i 的最小质因数是它自己
            primes.push_back(i); // 将 i 加入素数列表
        }

        // 遍历已找到的素数 p
        for (auto p : primes) {
            // 如果 i * p 超出范围 n，停止
            if (i * p > n) {
                break;
            }
            // 将 i * p 的最小质因数标记为 p
            minp[i * p] = p;
            // 如果 p 已经是 i 的最小质因数，说明 i 是 p 的倍数
            // 再往后的素数 q > p，i * q 的最小质因数将不再是 q
            // 而是 i 的最小质因数 p，为了保证每个合数只被其最小质因数筛一次，这里 break
            if (p == minp[i]) {
                break;
            }
        }
    }
}

int main() {
    // 关闭 C++ 标准 IO 流与 C stdio 的同步，提高 cin/cout 速度
    ios::sync_with_stdio(false);
    // 解除 cin 和 cout 的绑定，进一步提速
    cin.tie(nullptr);

    const int M = 1000000; // K 的上限，即 sqrt(10^12)
    sieve(M); // 运行线性筛，预处理到 M

    vector<i64> N; // 存储所有找到的 400 数 (K*K)
    // 遍历所有可能的 K 值 (从 1 到 M)
    for (int k = 1; k <= M; k ++ ) {
        int temp = k; // 临时变量用于分解质因数
        set<int> factors; // 使用 set 存储不同的质因数
        // 使用预处理的 minp 数组快速分解质因数
        while (temp > 1) {
            int p = minp[temp]; // 获取 temp 的最小质因数
            factors.insert(p); // 将质因数加入 set (自动去重)
            // 持续除以该最小质因数，直到不能整除为止
            // （优化：这里其实不需要完全除尽，只需要知道有哪些质因数即可）
            // 代码的写法是每次只除一次，因为下一个循环还会取最小质因数
            while (temp % p == 0) { // 修正：原代码是 temp /= p; 一次。这样写更符合分解逻辑，但原代码也能正确得到所有不同的质因数。
                 temp /= p;
            }
            // 如果temp在除p的过程中变成了1，需要跳出循环
            if (temp == 1) break;
            // 注：原代码 `temp /= p;` 也能工作，因为即使 `temp` 仍然是 `p` 的倍数，
            // 下一轮 `minp[temp]` 仍然会是 `p`，最终所有不同的质因数都会被加入 set。
        }

        // 如果 k 恰好有两个不同的质因数
        if (factors.size() == 2) {
            // 将 N = K*K 加入列表，注意使用 i64 避免溢出
            N.push_back((i64)k * k);
        }
    }
    // 对所有找到的 400 数进行排序
    sort(N.begin(), N.end());

    int Q; // 查询次数
    cin >> Q;
    // 处理 Q 个查询
    for (int qi = 0; qi < Q; qi++) {
        i64 A; // 查询的上限 A
        cin >> A;
        // 使用 upper_bound 在排好序的列表 N 中查找第一个大于 A 的元素的迭代器
        auto it = upper_bound(N.begin(), N.end(), A);
        // 断言确保找到了元素（因为题目保证解存在，且 A >= 36，所以 it 不会是 begin()）
        assert(it != N.begin());
        // 将迭代器向前移动一位，指向不大于 A 的最大元素
        it--;
        // 输出结果
        cout << *it << "\n";
    }

    return 0; // 程序正常结束
}