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