正题
题目链接:https://www.luogu.com.cn/problem/P4980
题目大意
(n)个物品图上(m)种颜色，求在可以旋转的情况下本质不同的涂色方案。
解题思路
既然是群论基本题就顺便写一下刚刚了解到的相关知识把（顺便消磨一下时间
一个群((G, imes ))定义为一个在运算( imes)下满足以下条件的集合
- 封闭性：若存在(a,bin G)那么有(a imes bin G)
- 交换律：若有(a,b,cin G)那么有((a imes b) imes c=a imes (b imes c))
- 单位元：群中(exists ein G)满足(forall xin G)都有(x imes e=x)
- 逆元：对于(forall xin G)都有一个唯一元素(yin G)且(x imes y=e)
然后中间一些东西很多很杂这里不多说了，直接到置换部分。
一般来说规定置换第一行为((1,2,3...))，那么定义一个置换(sigma=(g_1,g_2,g_3,...))。如果一个置换作用与一个排列(a)，一般写为(sigma(a)=b)的话，就有(b_i=a_{g_i})。需要注意的是对于一个置换两次后相当与使用了另一个置换。（也就是置换只能生效一次
然后就是( ext{Burnside})引理了，对于一个置换群(G)，若(G)作用与一个集合(X)时，集合(X)中本质不同的元素个数为
[frac{1}{|G|}sum_{fin G}C(f)
]
其中(C(f))表示(X)的所有元素中对于置换(f)的不动点数量。
而( ext{Polya})定理就是建立在( ext{Burnside})引理上的，对于一个置换(f)，定义它的循环节数量为(T(f))，用(m)种颜色染色时方本质不同的染色方案数就是
[frac{1}{|G|}sum_{fin G}m^{T(f)}
]
也就是(m^{T(f)}=C(f))，这个很显然，因为每个循环节涂成一种颜色就是一个不动点。
回到这题的旋转来，我们可以将其视为(n)个不同的置换构成的一个置换群。对于旋转(i)步，它的循环节数量就是(gcd(n,i))，也就是我们要求
[frac{1}{n}sum_{i=0}^{n-1}m^{gcd(n,i)}
]
枚举一下(gcd(n,i))
[frac{1}{n}sum_{d|n}m^dsum_{i=1}^{frac{n}{d}}[gcd(frac{n}{d},i)==1]
]
哦对啊好像有(m=n)
[frac{1}{n}sum_{d|n}n^dvarphi(frac{n}{d})=sum_{d|n}n^{d-1}varphi(frac{n}{d})
]
这个时间复杂度大概是(O(Tn^{frac{3}{4}}))的，但是因为约数个数远到不了(sqrt n)所以你可以把它视为常数比较大的(O(Tsqrt n))？
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll P=1e9+7;
ll T,n,ans;
ll power(ll x,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*x%P;
x=x*x%P;b>>=1;
}
return ans;
}
ll phi(ll x){
ll ans=x;
for(ll i=2;i*i<=x;i++){
if(x%i)continue;
while(x%i==0)x/=i;
ans=ans/i*(i-1);
}
if(x>1)ans=ans/x*(x-1);
return ans;
}
ll calc(ll x)
{return phi(x)*power(n,n/x-1)%P;}
signed main()
{
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);ans=0;
for(ll i=1;i*i<=n;i++){
if(n%i)continue;
ans=(ans+calc(i))%P;
if(i*i!=n)ans=(ans+calc(n/i))%P;
}
printf("%lld
",ans);
}
return 0;
}