Warning: session_start(): open(/tmp/sess_e5a261a3af49b702d39687ecebc3732f, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== polya定理 ======
===== 概念 =====
设 $G=\{P_1,P_2,...,P_g\}$ 是n个对象的一个置换群， $C(P_k)$ 是置换 $P_k$ 的循环个数。用 $m$ 种颜色对 $n$ 个对象着色，着色方案数为 $\frac{1}{|G|}(m^{C(P_1)}+m^{C(P_2)}+...+m^{C(P_g)})$
===== 例题 =====
[[https://www.luogu.com.cn/problem/P4980|洛谷p4980]]
首先由polya定理，首先存在 $n$ 个置换群，分别对应着旋转0个，旋转1个….旋转 $n-1$ 个。然后我们不难得知，若旋转 $k$ 个所对应的置换群为 $P_k$ ，那么 $C(P_k)=gcd(k,n)$
所以答案就是 $\frac{1}{n}\sum_{k=1}^{n}n^{\gcd(k,n)}$
转变成枚举 $gcd(k,n)$ ，上式可化为 $\frac{1}{n}\sum_{d|n}n^d\phi(\frac{n}{d})$
时间复杂度 $O(Tn^{\frac{3}{4}})$
===== 代码 =====
#include
#include
#include
#define mod 1000000007
using namespace std;
inline long long fast_pow(long long a,long long b)
{
long long an=1;
long long now=a;
for (;b;b>>=1,now=(now*now)%mod)
if (b&1)
an=(an*now)%mod;
return an;
}
int phi(int x)
{
int ans=x;
for (int i=2;i<=sqrt(x);i++)
if (x%i==0)
{
ans-=ans/i;
while (x%i==0) x/=i;
}
if (x!=1) ans-=ans/x;
return ans;
}
int main()
{
int T;
scanf("%d",&T);
while (T--)
{
long long ans=0;
int n;
scanf("%d",&n);
int cnt=sqrt(n);
for (int i=1;i<=cnt;i++)
if (n%i==0)
{
ans+=(fast_pow(n,n/i)*phi(i))%mod;
ans%=mod;
if (i*i!=n)
{
ans+=(fast_pow(n,i)*phi(n/i))%mod;
ans%=mod;
}
}
cout<<(1LL*ans*fast_pow(n,mod-2))%mod<