这是一个功能完备的数据生成器，用于为 P10720 [GESP202406 五级] 小杨的幸运数字 题目生成测试数据。

功能说明

1. 自动生成：运行程序后，会在当前目录下生成 1.in ~ 10.in 以及对应的标准答案 1.out ~ 10.out。
2. 数据覆盖：
   • Case 1-4：针对子任务 1（$N \le 100, a_i \le 10^5$），覆盖样例、随机、特定构造（幸运数、非幸运数）。
   • Case 5-10：针对子任务 2（$N \le 10^4, a_i \le 10^6$），覆盖大数据随机、全质数、全合数、多质因子、边界值等情况。
3. 算法正确性：内置了标准的试除法求解器，确保生成的 .out 文件准确无误。

C++ 数据生成器代码

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <random>
#include <ctime>
#include <set>

using namespace std;

// ==========================================
// 1. 核心解题逻辑 (用于生成 .out 文件)
// ==========================================
bool isLucky(int x) {
    int cnt = 0;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            cnt++;
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) cnt++;
    return cnt == 2;
}

// 读取输入文件，计算结果并写入输出文件
void solve(string inPath, string outPath) {
    ifstream fin(inPath);
    ofstream fout(outPath);
    
    if (!fin.is_open() || !fout.is_open()) {
        cerr << "Error opening files: " << inPath << " or " << outPath << endl;
        return;
    }

    int n;
    if (fin >> n) {
        while (n--) {
            int a;
            fin >> a;
            if (isLucky(a)) {
                fout << 1 << "\n";
            } else {
                fout << 0 << "\n";
            }
        }
    }
    
    fin.close();
    fout.close();
}

// ==========================================
// 2. 数据生成辅助工具
// ==========================================
const int MAX_VAL_LIMIT = 1000000;
vector<int> primes;
bool is_prime[MAX_VAL_LIMIT + 1];

// 线性筛预处理质数
void sieve() {
    fill(is_prime, is_prime + MAX_VAL_LIMIT + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= MAX_VAL_LIMIT; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (int p : primes) {
            if (i * p > MAX_VAL_LIMIT) break;
            is_prime[i * p] = false;
            if (i % p == 0) break;
        }
    }
}

mt19937 rng(time(0));

int rand_int(int l, int r) {
    uniform_int_distribution<int> dist(l, r);
    return dist(rng);
}

// 构造一个恰好有 2 个不同质因子的数 (幸运数字)
int gen_lucky(int limit) {
    while (true) {
        int p1 = primes[rand_int(0, primes.size() - 1)];
        if (p1 >= limit) continue;
        int p2 = primes[rand_int(0, primes.size() - 1)];
        if (p1 == p2) continue; // 必须不同
        
        long long res = (long long)p1 * p2;
        if (res > limit) continue;
        
        // 随机乘上 p1 或 p2 的幂次，增加多样性
        if (rand_int(0, 1)) {
            while (res * p1 <= limit && rand_int(0, 1)) res *= p1;
        } else {
            while (res * p2 <= limit && rand_int(0, 1)) res *= p2;
        }
        return (int)res;
    }
}

// 构造只有 1 个质因子的数 (质数或质数的幂)
int gen_single_factor(int limit) {
    int p = primes[rand_int(0, primes.size() - 1)];
    long long res = p;
    // 随机变为幂次
    while (res * p <= limit && rand_int(0, 2) > 0) {
        res *= p;
    }
    if (res > limit) return p;
    return (int)res;
}

// 构造有 >= 3 个不同质因子的数
int gen_multi_factor(int limit) {
    if (limit < 30) return 30; // 最小的 3 因子数是 2*3*5=30
    while (true) {
        // 选取较小的质数以保证乘积不溢出
        int idx1 = rand_int(0, 20); 
        int idx2 = rand_int(0, 20);
        int idx3 = rand_int(0, 20);
        int p1 = primes[idx1];
        int p2 = primes[idx2];
        int p3 = primes[idx3];
        
        if (p1 == p2 || p1 == p3 || p2 == p3) continue;
        
        long long res = (long long)p1 * p2 * p3;
        if (res <= limit) return (int)res;
    }
}

// ==========================================
// 3. 测试点生成逻辑
// ==========================================
void generate_case(int id, int n, int max_val, int mode) {
    string inName = to_string(id) + ".in";
    string outName = to_string(id) + ".out";
    ofstream fout(inName);
    
    fout << n << "\n";
    
    for (int i = 0; i < n; i++) {
        int val;
        
        // mode 0: 纯随机
        if (mode == 0) {
            val = rand_int(2, max_val);
        }
        // mode 1: 混合样例/边界
        else if (mode == 1) {
            int r = rand_int(0, 10);
            if (r < 2) val = 7; // 1个因子
            else if (r < 4) val = 12; // 2个因子
            else if (r < 6) val = 30; // 3个因子
            else if (r < 8) val = 2; // 最小边界
            else val = rand_int(2, max_val);
        }
        // mode 2: 主要是幸运数字
        else if (mode == 2) {
            if (rand_int(0, 10) < 9) val = gen_lucky(max_val);
            else val = rand_int(2, max_val);
        }
        // mode 3: 主要是单质因子 (质数或幂)
        else if (mode == 3) {
            if (rand_int(0, 10) < 9) val = gen_single_factor(max_val);
            else val = rand_int(2, max_val);
        }
        // mode 4: 主要是多质因子 (>=3)
        else if (mode == 4) {
            if (rand_int(0, 10) < 9) val = gen_multi_factor(max_val);
            else val = rand_int(2, max_val);
        }
        
        fout << val << "\n";
    }
    
    fout.close();
    solve(inName, outName);
    cout << "Generated Case " << id << ": N=" << n << ", Val<=" << max_val << endl;
}

int main() {
    sieve(); // 预处理质数
    
    // --- Subtask 1 (40%): N <= 100, Val <= 10^5 ---
    
    // Case 1: 极小 N，包含样例和边界
    generate_case(1, 10, 100, 1); 
    
    // Case 2: 随机小数据
    generate_case(2, 100, 100000, 0);
    
    // Case 3: 主要是幸运数字 (2因子)
    generate_case(3, 100, 100000, 2);
    
    // Case 4: 主要是非幸运数字 (1因子或多因子)
    generate_case(4, 100, 100000, 3); 

    // --- Subtask 2 (60%): N <= 10^4, Val <= 10^6 ---
    
    // Case 5: 随机中等数据
    generate_case(5, 1000, 1000000, 0);
    
    // Case 6: 最大 N，完全随机
    generate_case(6, 10000, 1000000, 0);
    
    // Case 7: 最大 N，大量幸运数字 (压力测试 true 的情况)
    generate_case(7, 10000, 1000000, 2);
    
    // Case 8: 最大 N，大量单因子数 (压力测试 false 的情况 - 质数/幂)
    generate_case(8, 10000, 1000000, 3);
    
    // Case 9: 最大 N，大量多因子数 (压力测试 false 的情况 - 合数)
    generate_case(9, 10000, 1000000, 4);
    
    // Case 10: 最大 N，混合边界 (如 10^6, 999999 等)
    // 这里使用纯随机，但在大范围内会有一定概率碰到边界，也可以手动加强
    generate_case(10, 10000, 1000000, 0); 

    return 0;
}

使用方法

1. 将上述代码保存为 generator.cpp。
2. 使用 C++ 编译器编译：g++ generator.cpp -o generator -O2。
3. 运行生成的可执行文件：./generator（Windows 下是 generator.exe）。
4. 程序运行结束后，当前目录下会出现 1.in ~ 10.in 和 1.out ~ 10.out。

测试点详细设计

• Case 1: $N=10$, 值域很小，包含 $2, 7, 12, 30$ 等典型样例，用于基础逻辑验证。
• Case 2: $N=100$, 值域 $10^5$，标准随机数据，符合 Subtask 1。
• Case 3: $N=100$，构造大量幸运数字（如 $6, 10, 12, 72$ 等），测试判 true 的逻辑。
• Case 4: $N=100$，构造大量非幸运数字（主要是质数 $p$ 或幂 $p^k$），测试判 false 的逻辑。
• Case 5: $N=1000$, 值域 $10^6$，中等规模随机。
• Case 6: $N=10000$, 值域 $10^6$，Subtask 2 的满数据随机测试。
• Case 7: $N=10000$，针对性测试：主要是幸运数字，考察大量分解质因数的效率。
• Case 8: $N=10000$，针对性测试：主要是质数或其幂次方（如 $2^{10}$），考察对单质因子的识别。
• Case 9: $N=10000$，针对性测试：主要是 $2 \times 3 \times 5$ 这类多因子数，考察对超过2个质因子的识别。
• Case 10: $N=10000$，综合压力测试。

题目分析

1. 题目要求 题目要求判断给定的正整数 $a_i$ 是否恰好拥有 两个不同的质因子。 例如：

• $12 = 2 \times 2 \times 3$，质因子为 $2, 3$，共 2 个不同质因子。是幸运数字。
• $30 = 2 \times 3 \times 5$，质因子为 $2, 3, 5$，共 3 个不同质因子。不是幸运数字。
• $7 = 7$，质因子为 $7$，共 1 个不同质因子。不是幸运数字。

2. 核心思路：分解质因数 我们需要统计一个数的不同质因子个数。最常用的方法是试除法。 对于每个查询的数 $x$：

1. 定义一个计数器 cnt = 0。
2. 从 $i=2$ 开始枚举，直到 $i \times i \le x$：
   • 如果 $i$ 能整除 $x$（即 x % i == 0），说明 $i$ 是 $x$ 的一个质因子。
   • 此时计数器 cnt 加 1。
   • 然后用 while 循环将 $x$ 中所有的因子 $i$ 除尽（即 x /= i），以保证后续找到的因子都是不同的质数。
3. 循环结束后，如果 $x > 1$，说明剩下的 $x$ 本身也是一个质因子（且比 $\sqrt{\text{原}x}$ 大），计数器 cnt 再加 1。
4. 最后判断 cnt 是否等于 2。

3. 时间复杂度分析

• 单次查询：试除法的时间复杂度为 $O(\sqrt{a_i})$。
• 数据范围：$a_i \le 10^6$，所以 $\sqrt{a_i} \le 1000$。
• 查询次数：$n \le 10^4$。
• 总运算量：大约 $10^4 \times 1000 = 10^7$ 次运算。
• C++ 一般能在 1 秒内处理约 $10^8$ 次运算，因此该算法在时间限制内非常安全。

C++ 参考代码

#include <iostream>
using namespace std;

// 判断是否为幸运数字的函数
bool isLucky(int x) {
    int cnt = 0; // 记录不同质因子的个数
    
    // 从 2 开始枚举因子，直到 sqrt(x)
    for (int i = 2; i * i <= x; i++) {
        // 如果 i 是 x 的因子
        if (x % i == 0) {
            cnt++; // 发现一个新的质因子
            
            // 将 x 中所有的 i 因子除尽
            // 这样能保证后面遇到的因子都是质数，且不会重复统计
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    
    // 如果循环结束后 x 仍然大于 1，说明剩下的 x 本身就是一个质因子
    if (x > 1) {
        cnt++;
    }
    
    // 判断是否恰好有两个不同的质因子
    return cnt == 2;
}

int main() {
    // 优化输入输出速度
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    if (cin >> n) {
        while (n--) {
            int a;
            cin >> a;
            if (isLucky(a)) {
                cout << 1 << "\n";
            } else {
                cout << 0 << "\n";
            }
        }
    }
    return 0;
}