题目描述

给定一个 $n$ 个点，$n$ 条边的环，有 $n$ 种颜色，给每个顶点染色，问有多少种本质不同的染色方案，答案对 $10^9+7$ 取模。

注意本题的本质不同，定义为：只需要不能通过旋转与别的染色方案相同。

输入格式

第一行输入一个 $t$，表示有 $t$ 组数据

第二行开始，一共 $t$ 行，每行一个整数 $n$，意思如题所示。

输出格式

共$t$行，每行一个数字，表示染色方案数对 $10^9+7$ 取模后的结果

5
1 
2 
3 
4 
5 

1
3
11
70
629

提示

$$n \leq 10^9$$ $$t \leq 10^3$$

---

---

🥇 NOI教练辅导笔记：解题思路与草稿纸推演

作为你的教练，我不会直接把满分代码拍在你脸上，而是要教你怎么在考场上的草稿纸把这道题“盘”出来。

1. 预备知识点扫描

要拿下这道纯数学模板题，你的武器库里需要装配以下子模块：

• 核心定理：Burnside 引理与 Pólya 定理（解决旋转/对称同构计数）。
• 数论基础：
  • 欧拉函数（Euler's totient function, $\varphi$） 的定义及 $O(\sqrt{X})$ 求解方法。
  • 费马小定理（Fermat's Little Theorem） 及 乘法逆元（Modular Multiplicative Inverse）（解决除法的取模问题）。
• 算法技巧：快速幂（$O(\log N)$ 算 $A^B \bmod P$）、约数枚举。

2. 读题题眼（关键词拆解）

在考场上读到以下关键词，你的大脑应该迅速建立映射关系：

• 🔑 “$n$个点的环”、“不能通过旋转完全相同” $\rightarrow$ 这是一个大小为 $n$ 的循环群 $G$，操作为顺时针旋转 $0, 1, 2, \dots, n-1$ 步。
• 🔑 “本质不同” $\rightarrow$ 目标是求置换群下的等价类数量，即轨道数。
• 🔑 “$n$种颜色且无限制染色” $\rightarrow$ 满足各个位置颜色独立，可以直接使用 Pólya 定理 的快捷公式 $m^{c(g)}$（这里 $m=n$）。

3. 启发式推导演练（请拿出草稿纸）

第一步：写下最原始的 Pólya 公式 根据题意，$n$ 个顶点的环有 $n$ 种旋转置换（转 $k$ 步，$k \in[1, n]$）。对于旋转 $k$ 步的置换，它会将环分解成 $\gcd(k, n)$ 个循环。 因为有 $n$ 种颜色，所以不动点个数是 $n^{\gcd(k, n)}$。 代入公式，我们在纸上写下：

$$Ans = \frac{1}{n} \sum_{k=1}^n n^{\gcd(k, n)}$$

第二步：发现性能瓶颈（时间复杂度分析） 如果我们直接按照上面这个公式写一个循环：

• 遍历 $k$ 从 $1$ 到 $n$，求 $\gcd$，算快速幂。
• 复杂度灾难：单次计算 $O(n \log n)$。题目 $n \le 10^9$，$t \le 10^3$。总运算量直接突破 $10^{12}$，必定 TLE 爆零。

第三步：数学降维打击（转换枚举对象） 教练提示你：“既然里面有很多 $\gcd(k, n)$ 算出来的值是一样的，我们能不能把相同的值打包一起算？”

• 令 $d = \gcd(k, n)$，显然 $d$ 一定是 $n$ 的约数（即 $d|n$）。
• 那么原式变为：$Ans = \frac{1}{n} \sum_{d|n} (\text{有多少个 } k \text{ 满足 } \gcd(k, n) = d) \times n^d$
• 什么样的 $k$ 满足 $\gcd(k, n) = d$ 呢？ 两边同时除以 $d$，得到 $\gcd(k/d, n/d) = 1$。 由于 $k \le n$，所以 $k/d \le n/d$。
• 顿悟时刻：这不就是欧拉函数 $\varphi(n/d)$ 的定义吗！（在 $1 \sim n/d$ 中与 $n/d$ 互质的数的个数）

于是你在草稿纸上写下了最终优化公式：

$$Ans = \frac{1}{n} \sum_{d|n} \varphi\left(\frac{n}{d}\right) \times n^d $$

第四步：优化后的时间复杂度分析

• 枚举 $n$ 的约数 $d$：只需遍历到 $\sqrt{n}$，即 $O(\sqrt{n})$。
• 计算单次 $\varphi(n/d)$：也是 $O(\sqrt{n/d})$ 级别。
• 整体单次查询复杂度：严格分析约为 $O(\sqrt{n})$（因为除最大素因子外的计算量迅速衰减）。
• 乘上测试组数 $t$，$10^3 \times \sqrt{10^9} \approx 3 \times 10^7$ 次运算。在 $1$ 秒的时限内，完美通过！

4. 伪代码与逻辑流（Mermaid 流程图）

代码结构非常清晰，但要注意两个细节：

1. $n$ 极大，运算过程中的累加必须时刻 % 1000000007。
2. 最后的除以 $n$，在模意义下必须转为 乘以 $n$ 的乘法逆元（由于 $10^9+7$ 是质数，根据费马小定理，逆元为 $n^{10^9+5} \pmod{10^9+7}$）。

由于竞赛中伪代码需要极高的逻辑严密性，请参考以下代码流程逻辑：

graph TD
    Start(程序开始) --> ReadT(读入测试组数 T)
    ReadT --> CheckT{T 大于 0 吗}
    CheckT -- 否 --> End(程序结束)
    CheckT -- 是 --> ReadN(读入 n)
    ReadN --> InitAns(初始化 ans = 0)
    InitAns --> LoopI(枚举 i 从 1 到 根号n)
    
    LoopI --> CheckDiv(判断 i 是否是 n 的约数)
    CheckDiv -- 是 --> DoD1(处理约数 d1 等于 i)
    
    DoD1 --> CalcPhi1(计算 EulerPhi 传入 n除以d1)
    CalcPhi1 --> CalcPow1(计算 n 的 d1 次方模 P)
    CalcPow1 --> AddAns1(ans 累加 EulerPhi 乘 Pow 模 P)
    AddAns1 --> CheckSquare(判断 i 的平方是否不等于 n)
    
    CheckSquare -- 是 --> DoD2(处理成对的约数 d2 等于 n除以i)
    DoD2 --> CalcPhi2(计算 EulerPhi 传入 n除以d2)
    CalcPhi2 --> CalcPow2(计算 n 的 d2 次方模 P)
    CalcPow2 --> AddAns2(ans 累加 EulerPhi 乘 Pow 模 P)
    AddAns2 --> NextI(i 自增)
    
    CheckSquare -- 否 --> NextI
    CheckDiv -- 否 --> NextI
    
    NextI --> CheckIBound{i 是否大于 根号n}
    CheckIBound -- 否 --> CheckDiv
    
    CheckIBound -- 是 --> CalcInv(使用费马小定理计算 n 的逆元 invN)
    CalcInv --> FinalAns(ans 等于 ans 乘以 invN 模 P)
    FinalAns --> Output(输出 ans)
    Output --> DecT(T 自减 1)
    DecT --> CheckT

教练嘱咐：照着流程图，自己用 C++14 把 qpow() 和 phi() 这两个基础函数敲出来，拼接到主逻辑里，这道题的 AC 就是你的囊中之物了！如果在实现 phi() 函数提取质因子时遇到困难，随时来找我。