题目大意：给一个$n$个点的环染色，有$n$中颜色，问有多少种涂色方案是的旋转后本质不同
题解：$burnside$引理：$ans=\dfrac1{|G|}\sum\limits_{g\in G}A_g$
对于环，有$Polya$定理：$ans=\dfrac1{|G|}\sum\limits_{g\in G}m^{c(g)}$（$m$为颜色数，在这道题中$m=n$，$c(g)$为置换$g$中循环个数）
因为是循环相同，所以$|G|=n$，当$g=\left(
\begin{smallmatrix}
1&2&\cdots&n-k&n-k+1&\cdots&n\\
k+1&k+2&\cdots&n&1&\cdots&k
\end{smallmatrix}
\right)$时，$c(g)=\gcd(k,n)$
$$
\begin{align*}
ans&=\dfrac1{|G|}\sum\limits_{g\in G}m^{c(g)}\\
&=\dfrac1n\sum\limits_{i=1}^nn^{(i,n)}\\
&=\dfrac1n\sum\limits_{d|n}n^d\sum\limits_{i=1}^n[(i,n)=d]\\
&=\dfrac1n\sum\limits_{d|n}n^d\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}[(i\cdot d,n)=d]\\
&=\dfrac1n\sum\limits_{d|n}n^d\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}[(i,\dfrac nd)=1]\\
&=\dfrac1n\sum\limits_{d|n}n^d\varphi(\dfrac nd)
\end{align*}
$$
虽然是多组询问，但是依然可以$O(\sqrt n)$求$\varphi$，复杂度$O(Tn^{\frac34})$，当然，正确的方法是求出质因数后递归求出每个因数的$\varphi$，复杂度$O(T\sqrt n)$
卡点：无
C++ Code：
#include <cstdio>
const int mod = 1e9 + 7; namespace Math {
inline int getphi(int x) {
int res = x;
for (register int 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;
} inline int pw(int base, int p) {
static int res;
for (res = 1; p; p >>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;
return res;
}
inline int inv(int x) { return pw(x, mod - 2); }
} inline void reduce(int &x) { x += x >> 31 & mod; } int Tim, n, ans;
inline int get(int d) {
return static_cast<long long> (Math::pw(n, d)) * Math::getphi(n / d) % mod;
} int main() {
scanf("%d", &Tim);
while (Tim --> 0) {
scanf("%d", &n);
ans = 0;
for (int i = 1; i * i <= n; ++i) if (n % i == 0) {
reduce(ans += get(i) - mod);
if (i != n / i) reduce(ans += get(n / i) - mod);
}
printf("%lld\n", static_cast<long long> (ans) * Math::inv(n) % mod);
}
return 0;
}