题目

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

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

题解

对于一个置换 $\tau_k=\begin{pmatrix} 1 & 2 & \dots & n-k & n-k+1 & n-k+2 & \dots & n\\ k+1 & k+2 & \dots & n & 1 & 2 & \dots & k \end{pmatrix}$ 。

把环分割，每块长度 $d$ 。考虑旋转后相同，可知 $d$ 的最小值为 $\gcd(n,k)$ 。那么循环个数 $c(\tau_k)=\gcd(n,k)$ 。

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

然后欧拉函数性质搞搞。

代码

const int N = 0, mod = 1e9 + 7;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	int add(int a, int b) { return a + b > mod? a + b - mod: a + b; }
	int dec(int a, int b) { return a - b < 0? a - b + mod: a - b; }
	int mul(int a, int b) { return 1ll * a * b % mod; }
	int qpow (int a, ll b) {
		int ans = 1;
		for (; b; b >>= 1, a = mul(a, a))
			if (b & 1) ans = mul(ans, a);
		return ans;
	}
	int phi(int x) {
		int ans = x;
		for (int i = 2; i * i <= x; ++i) {
			if (x % i) continue;
			ans = ans - ans / i;
			for (; x % i == 0; x /= i);
		}
		if (x != 1) ans = ans - ans / x;
		return ans;
	}
	int main () {
		for (int T = Read(); T--; ) {
			n = Read();
			int ans = 0;
			for (int i = 1; i * i <= n; i++) {
				if (n % i) continue;
				int p1 = phi(i), f1 = qpow(n, n / i);
				ans = add(ans, mul(f1, p1));
				if (i * i != n) {
					int p2 = phi(n / i), f2 = qpow(n, i);
					ans = add(ans, mul(f2, p2));
				}
			}
			printf ("%d\n", mul(ans, qpow(n, mod - 2)));
		}
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}