你好！我是你的OI教练。

为了在OJ（在线评测系统）上完美地区分出**“暴力解法”、“部分优化解法”和“正解”**，测试数据的梯度设计至关重要。

以下我为你编写的 C++ 数据生成器。它将一次性生成 1.in ~ 10.in 以及对应的标准答案 1.out ~ 10.out。

🎯 测试数据梯度设计思路（区分度分析）

• Test 1 ~ 2：$t \le 100,\ n \le 100$。极小数据，用来白给，连最暴力的 $O(N \log N)$ 都能以 0.001s 跑过。
• Test 3 ~ 4：$t \le 1000,\ n \le 2000$。小数据，暴力 $O(N)$ 解法总运算量约 $2 \times 10^6$，可以轻松拿分。
• Test 5 ~ 6：$t \le 1000,\ n \le 10^5$。中等数据，此时暴力算法的总运算量达到 $10^8$，对于常数较大的 $O(N \log N)$ （青铜版代码）可能会开始 TLE，拿部分分。
• Test 7 ~ 8：$t \le 1000,\ n \le 10^9$。随机大数据，青铜版必 TLE，只有 $O(\sqrt{N})$ 的金牌版正解可以通过。
• Test 9：包含大量靠近 $10^9$ 的大质数（如 $999999937$），专门卡那些在求 $\varphi$ 或求约数时没有写到 $\sqrt{n}$ 提前 break 的冗余代码。
• Test 10：边界与极端极限数据（Anti-Heuristic）。包含 $n=1$、$n=10^9$、$n=2^{29}$、以及 $10^9$ 以内约数最多的高合成数（如 $735134400$，有 1344 个约数），专门测试正解在最坏情况下的时间复杂度表现和取模防溢出能力。

💻 C++14 数据生成器完整代码

请将以下代码保存为 data_generator.cpp，并在同一目录下编译运行。它会自动生成 20 个文件，且所有文件大小加起来不超过 500 KB，远低于 2MB 的要求。

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>

using namespace std;

const long long MOD = 1e9 + 7;

// ==================== 核心标程算法区 (用于生成 .out) ====================

// 快速幂
long long qpow(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

// 求解单个数 x 的欧拉函数 phi(x)
long long get_phi(long long x) {
    long long res = x;
    for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}

// 金牌版最优复杂度 $O(\sqrt{n})$ 求解核心
long long solve_for_n(long long n) {
    long long ans = 0;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            // 约数 d1 = i
            long long d1 = i;
            long long term1 = (get_phi(n / d1) % MOD) * qpow(n, d1) % MOD;
            ans = (ans + term1) % MOD;
            
            // 约数 d2 = n / i (防重复)
            long long d2 = n / i;
            if (d1 != d2) {
                long long term2 = (get_phi(n / d2) % MOD) * qpow(n, d2) % MOD;
                ans = (ans + term2) % MOD;
            }
        }
    }
    long long invN = qpow(n, MOD - 2);
    ans = (ans * invN) % MOD;
    return ans;
}

// ==================== 数据生成器控制区 ====================

// 生成指定范围内的随机长整数
long long rand_ll(long long l, long long r, mt19937_64& rng) {
    uniform_int_distribution<long long> dist(l, r);
    return dist(rng);
}

// 根据测试点编号生成 T 的大小
int get_t(int test_id) {
    if (test_id == 1) return 10;
    if (test_id == 2) return 100;
    if (test_id == 3) return 100;
    if (test_id == 5) return 500;
    return 1000; // 其他所有测试点 T=1000 以达到最大计算量压力
}

// 根据测试点编号和当前是第 i 个查询，生成具体的 n
long long get_n(int test_id, int i, mt19937_64& rng) {
    if (test_id == 1) { // 极小数据，必须包含边界 1, 2, 3
        if (i <= 3) return i; 
        return rand_ll(4, 20, rng);
    }
    if (test_id == 2) return rand_ll(20, 100, rng);
    if (test_id == 3) return rand_ll(100, 1000, rng);
    if (test_id == 4) return rand_ll(1000, 2000, rng); // 暴力分界线
    if (test_id == 5) return rand_ll(10000, 50000, rng); // 暴力开始 TLE
    if (test_id == 6) return rand_ll(50000, 100000, rng);
    if (test_id == 7) return rand_ll(100000000, 1000000000, rng); // 随机大数据
    if (test_id == 8) return rand_ll(500000000, 1000000000, rng); // 随机大数据
    
    if (test_id == 9) { // 包含大量大质数，卡不够优秀的欧拉函数求法
        if (i % 5 == 0) return 999999937; // 10^9以内的最大质数
        if (i % 5 == 1) return 999999929;
        return rand_ll(100000000, 1000000000, rng);
    }
    
    if (test_id == 10) { // 极端边界与 Anti-Heuristic 构造数据
        vector<long long> special = {
            1, 2, 3, 
            1000000000,              // 最大上界
            999999937,               // 大质数
            735134400,               // 10^9内约数最多的数 (1344个约数)
            897581056,               // 约数同样极多
            536870912,               // 2^29 (全是2的质因子)
            999999999,               // 多个质因子组合 3^4 * 37 * 333667
            1000000000 - 7           // 接近 MOD 的值
        };
        if (i <= special.size()) return special[i - 1];
        return rand_ll(800000000, 1000000000, rng);
    }
    
    return 1;
}

// 生成单个测试点文件的总流程
void generate_test_point(int test_id, mt19937_64& rng) {
    string in_name = to_string(test_id) + ".in";
    string out_name = to_string(test_id) + ".out";
    
    ofstream fout_in(in_name);
    ofstream fout_out(out_name);
    
    if (!fout_in.is_open() || !fout_out.is_open()) {
        cerr << "Error opening file for test point " << test_id << "!\n";
        return;
    }
    
    int t = get_t(test_id);
    fout_in << t << "\n";
    
    for (int i = 1; i <= t; i++) {
        long long n = get_n(test_id, i, rng);
        fout_in << n << "\n";
        
        // 算出标准答案
        long long ans = solve_for_n(n);
        fout_out << ans << "\n";
    }
    
    fout_in.close();
    fout_out.close();
    
    cout << "Test point " << test_id << " generated successfully. (T = " << t << ")\n";
}

int main() {
    // 固化随机种子，保证每次运行生成的数据完全一致（符合竞赛造数据标准）
    mt19937_64 rng(19260817); 
    
    cout << "Start generating data for P4980 (Polya Theorem)..." << "\n\n";
    
    for (int test_id = 1; test_id <= 10; test_id++) {
        generate_test_point(test_id, rng);
    }
    
    cout << "\nAll 10 test points generated completely!\n";
    return 0;
}

💡 教练的造数据小贴士：

1. 防止除 0：在数学题的数据生成中，边界 0 很容易导致运行时错误。题目的数据范围暗示了 $n \ge 1$，因此在生成逻辑中通过 special 数组或 l=1 的边界严格限制了不会出现 0，避免了你在求 n/d 时出现 Division by zero Exception。
2. 栈溢出保护：本数据生成器的所有逻辑（包括标准答案计算）均采用了**迭代式（非递归）**的写法，杜绝了爆栈的可能。
3. 确定性随机（Seeded RNG）：我刻意传入了 mt19937_64 rng(19260817); 固化随机种子。在算法竞赛造数据时，固定种子是一个非常好的习惯。这能保证如果后续你想调整部分数据的生成规则时，未改动的部分生成的内容是稳定一致的，方便你在 OJ 上重测（Rejudge）。