作为板子题，先上公式：
\[|X/G|=\frac 1{|G|}\sum_{g\in G} |B|^{c(g)} \]显然，\(|G|=n\)
用 \(g_i\) 表示旋转 \(i\) 个的置换，则 \(c(g_i)=(n,i)\)
我们要算下式：
\[\begin{aligned} &\frac 1n\sum_{i=1}^n n^{(n,i)} \\ =&\frac 1n\sum_ {d\mid n} n^d\cdot \sum_{i=1}^n [(n,i)=d] \\ =&\frac 1n\sum_{d\mid n} n^d\cdot \varphi(\frac nd) \end{aligned}\]本题中直接暴力计算 \(\varphi\) 可以通过。
分析复杂度可参见本文
复杂度 \(\mathcal O(Tn^{\frac 34})\)
或者考虑利用该博客中的法二计算。
但考虑到实际上 \(d(n)\) 远小于 \(\sqrt n\)（当 \(n\) 足够大时，\(d(n)\cdot \log n\) 也小于 \(\sqrt n\)），所以法二的单次复杂度就是 \(\mathcal O(\sqrt n)\) 的。
我的程序使用方法二，复杂度 \(\mathcal O(T\sqrt n)\)
$\textsf {View Code}$
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
char buf[1<<14],*p1=buf,*p2=buf;
#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)
struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in,_tp &x){
x=0;int w=0;char c=GetC();
for(;!isdigit(c);w|=c=='-',c=GetC());
for(;isdigit(c);x=x*10+(c^'0'),c=GetC());
if(w) x=-x;
return in;
}
const int mod=1e9+7,N=30;
using ll=long long;
ll qpow(ll a,int b){
ll ans=1;
while(b){
if(b&1) ans=ans*a%mod;
b=b>>1;a=a*a%mod;
}
return ans;
}
int q[N],num[N],cnt;
int ans,n;
void dfs(int stp,int d,int phi){
if(stp>cnt){
ans=(ans+qpow(n,n/d)*phi%mod)%mod;
return ;
}
dfs(stp+1,d,phi);
int t=1;
for(int i=1;i<=num[stp];++i){
dfs(stp+1,d*t*q[stp],phi*t*(q[stp]-1));
t*=q[stp];
}
}
int main(){
int T;io>>T;
while(T--){
io>>n;
cnt=0;
int tmp=n;
for(int i=2;1ll*i*i<=n;++i){
if(n%i==0){
q[++cnt]=i;
num[cnt]=0;
while(n%i==0) n/=i,++num[cnt];
}
}
if(n>1){
q[++cnt]=n;num[cnt]=1;
}
n=tmp;
dfs(1,1,1);
printf("%lld\n",(ll)ans*qpow(n,mod-2)%mod);
ans=0;
}
return 0;
}