你好！我是你的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）。

你好！我是你的OI教练。看到你顺利理清了思路，画出了流程图，现在是我们“真枪实弹”上代码的时候了。

在NOI/NOIP竞赛中，直接写出正解固然好，但**“从暴力到正解的推演”**是检验你是否真正吃透这个算法的唯一标准。很多时候，考场上的对拍（验证程序正确性）也需要你写出一个绝对正确的暴力程序。

接下来，我会给你两份符合 C++14 竞赛标准、完整且可独立运行的代码。一份是最原始暴力的（青铜版），一份是经过数论优化的正解（金牌版）。请准备好你的编辑器，我们一起看看代码里的“坑”在哪里。

版本一：青铜版（最原始的 Pólya 公式直译）

这个版本是我们在草稿纸上写下的第一步：$Ans = \frac{1}{n} \sum_{i=1}^n n^{\gcd(i, n)} \pmod{10^9+7}$。 没有任何花里胡哨，直接枚举 $i$。

💻 C++14 完整代码

#include <iostream>
using namespace std;

const long long MOD = 1e9 + 7;

// 快速幂计算 (base^exp) % MOD，非常基础且常用的模板
long long qpow(long long base, long long exp) {
    long long res = 1;
    base %= MOD; // 易错点1：底数进来先取模，防止溢出
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

// 辗转相除法求最大公约数
long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

void solve() {
    long long n;
    cin >> n;
    
    long long ans = 0;
    // 直接暴力枚举转动步数 i，从 1 到 n
    for (long long i = 1; i <= n; i++) {
        long long d = gcd(i, n);               // 算出循环的个数 d
        long long term = qpow(n, d);           // 每个循环可以独立选 n 种颜色
        ans = (ans + term) % MOD;              // 易错点2：每次加法都要取模
    }
    
    // 易错点3：除以 n 在模意义下等价于乘以 n 的乘法逆元
    // 因为 1e9+7 是质数，根据费马小定理，n 的逆元就是 n^(MOD - 2)
    long long invN = qpow(n, MOD - 2);
    ans = (ans * invN) % MOD;
    
    cout << ans << "\n";
}

int main() {
    // 竞赛必备：解绑输入输出流，加速读写
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

📊 复杂度分析与思考（版本一）

• 时间复杂度：每一组测试数据中，我们需要循环 $n$ 次。循环内部求 gcd 大约需要 $O(\log n)$ 的时间，求 qpow 也需要 $O(\log n)$ 的时间。所以单次查询的时间复杂度为 $O(n \log n)$。总时间复杂度为 $O(t \cdot n \log n)$。
• 空间复杂度：由于只用了常数个变量，空间复杂度为 $O(1)$。
• 教练的评估与优化建议：这组代码逻辑严密、绝对正确，但面对本题 $n \le 10^9$ 的数据范围，必定会超时（Time Limit Exceeded）。优化突破口：我们发现 gcd(i, n) 的结果一定只有那几个（$n$ 的约数），大量的 gcd 和 qpow 被重复计算了。我们需要把枚举对象从“转动步数 $i$”优化为“最大公约数 $d$”。

版本二：金牌版（约数枚举 + 欧拉函数优化）

这就是我们推导出来的终极公式：$Ans = \frac{1}{n} \sum_{d|n} \varphi\left(\frac{n}{d}\right) \times n^d \pmod{10^9+7}$。 这个版本可以稳稳地在1秒内通过 $10^9$ 的数据。

💻 C++14 完整代码

#include <iostream>
using namespace std;

const long long MOD = 1e9 + 7;

// 快速幂计算 (base^exp) % MOD
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)
// 含义：在 [1, x] 中与 x 互质的数的个数
long long get_phi(long long x) {
    long long res = x;
    // 技巧：枚举 x 的质因子，只需枚举到 sqrt(x)
    for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            res = res / i * (i - 1); // 欧拉函数计算公式：res = res * (1 - 1/p)
            while (x % i == 0) {     // 把当前质因子 p 除干净
                x /= i;
            }
        }
    }
    // 易错点4：如果最后 x 还不为 1，说明它本身就是一个大于 sqrt(x) 的质因子
    if (x > 1) {
        res = res / x * (x - 1);
    }
    return res;
}

void solve() {
    long long n;
    cin >> n;
    
    long long ans = 0;
    
    // 核心优化：只枚举 n 的约数 d
    // 技巧：只需枚举到 sqrt(n)，约数总是成对出现的 (i 和 n/i)
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) { // 如果 i 是 n 的约数
            
            // 处理第一个约数：d = i
            long long d1 = i;
            long long phi1 = get_phi(n / d1) % MOD;     // 与 n/d1 互质的个数
            long long term1 = (phi1 * qpow(n, d1)) % MOD; // 方案数累加
            ans = (ans + term1) % MOD;
            
            // 处理第二个配对约数：d = n / i
            // 易错点5：要防止 i * i == n 时，同一个约数被计算两次
            long long d2 = n / i;
            if (d1 != d2) {
                long long phi2 = get_phi(n / d2) % MOD;
                long long term2 = (phi2 * qpow(n, d2)) % MOD;
                ans = (ans + term2) % MOD;
            }
        }
    }
    
    // 最后除以 n，即乘以逆元
    long long invN = qpow(n, MOD - 2);
    ans = (ans * invN) % MOD;
    
    cout << ans << "\n";
}

int main() {
    // 竞赛必备：解绑输入输出流
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

📊 复杂度分析与思考（版本二）

• 时间复杂度：
  • 外层循环枚举 $n$ 的约数，循环到 $\sqrt{n}$，即 $O(\sqrt{n})$。
  • 在循环内部，我们需要计算欧拉函数 get_phi(x)，最坏情况下内部循环到 $\sqrt{x}$（这里的 $x$ 最大是 $n$），似乎是 $O(\sqrt{n})$。
  • 看起来单次时间复杂度是 $O(\sqrt{n} \times \sqrt{n}) = O(n)$？不是的！。实际上一个数的约数个数是非常有限的（$10^9$ 内约数个数最多的数只有 1344 个）。结合严密的数学分析，求所有约数的 $\varphi$ 值的总代价远小于 $O(n)$，实际约为 $O(\sqrt{n})$ 级别。
  • 整体时间复杂度可以稳过 $t \times \sqrt{n}$ 的运算量。本题 $t \le 10^3, \sqrt{n} \approx 3.16 \times 10^4$，总运算大概只有 $3 \times 10^7$ 次左右。
• 空间复杂度：由于只是存储了几个 long long 的中间变量，空间复杂度完美保持为 $O(1)$。
• 进阶拓展（给想要冲刺国家集训队选手的加餐）：如果数据范围变得更变态，比如 $n \le 10^{14}$ 呢？这个时候即便是 $O(\sqrt{n})$ 也会超时。那就需要用到 Pollard-Rho 算法（随机化大整数分解） 来 $O(n^{1/4})$ 求约数，配合预处理质数去算欧拉函数。但在一般的省选或 NOI 考场上，掌握目前的版本（试除法）就已经足够拿到满分了！

教练的最后嘱咐： 这两份代码，不要光看，一定要自己手敲一遍。重点体会 get_phi() 函数中 x > 1 的特判，以及 处理配对约数时 d1 != d2 的去重判断，这两个地方是历届学生上机时最容易栽跟头的地方。祝你AC！