对于一个集合 \(S\) 和定义在这个集合上的二元运算 \(*\) , 满足:
封闭性。 \(\forall a \in S,b \in S\) ,\(a*b \in S\)
结合律。 \(a*b*c=a*(b*c)\)
单位元。 \(\exists \epsilon \in S\) , \(a*\epsilon = \epsilon * a=a\)
逆元。 \(\forall a \in S\) , \(\exists b \in S\) , \(a * b = \epsilon\) , 记作 \(a'\)
那么称 \((S,*)\) 为一个群。
值得注意的是,一个群的单位元和逆元都是唯一的。
若 \(G(S,*)\) 为一个群,若 \(T \subseteq S\) ,且 \(H(T,*)\) 也为一个群,那么称 \(H\) 为 \(G\) 的子群,记作 \(H \le G\)
左陪集:若群 \(H\) 为群 \(G\) 的一个子群,且对于 \(g \in G\),\(gH=\{gh|h \in H \}\)。
同样可以定义右陪集。
注意陪集可能不包含单位元,不一定是群。
陪集的性质:
\([G:H]\): \(G\) 中 \(H\) 不同陪集的数量
\(G~/~H~\): \(G\) 中所有 \(H\) 的左陪集
有:
证明:由陪集的性质 1、5、6 显然。
对于集合 \(S=\{a_1,a_2 \dots a_n\}\) , 一个置换 \(f\) 可表示为:
\(p\) 为 \(1\sim n\) 的排列,意义为将 \(a_i\) 映射为 \(a_{p_i}\)。
称为置换的乘法。
一种特殊的置换,其中:
任意一个置换都可以表示为若干不相交的循环置换的乘积,例如
将一个置换 \(f\) 拆分的循环置换个数记为 \(c(f)\)
若 \(S\) 包含所有的 \(n!\) 个不同 \(n\) 元置换,\(G(S,\times)\) 为一个群,证明如下:
\(G\) 的子群称作置换群。
对于作用在集合 \(X\) 上的群 \(G\) 和集合 \(X\) 的一个元素 \(x\)
\(x\) 的轨道:\(G(x)=\{ g(x) | g \in G\}\)
\(x\) 的稳定子:\(G^x=\{ g \in G| g(x)=x\}\)
这里 \(g(x)\) 为群作用的函数,例如上文提到的置换。
\(G^x\) 为 \(G\) 的子群。
证明:
\(|G(x)|=[G:G^x]\)
证明:
对于 \(f(x)=g(x)\) , \(f \times g^{-1}=\epsilon\)
若有两个 \(f(x)=g(x),f \times g^{-1} = x = \epsilon(x)\) ,所以 \(f \times g^{-1} \in G^x\) , \(\Rightarrow fG^x = gG^x\) , 反之亦然。
即不同的 \(g\) 对应不同的陪集。
所以对于 \(G(x)\) 中的 \(g\) , 构造对应陪集为 \(gG^x\)。
感觉在伪证。
轨道稳定子定理:
证明:
因为 \(G^x\) 为 \(G\) 的子群,由拉格朗日定理得:
由性质2得:
证毕。
若一个置换群 \(G\) 作用于 \(X\) , \(X/G\) 表示在群 \(G\) 作用下 \(X\) 的所有等价类的集合。(注意每个等价类也是一个集合,若两个元素在 \(G\) 作用下可以转化则属于同一个等价类)
\(X^g\) 表示在 \(g\) 的作用下不变的 \(X\) 中元素的集合。
那么有:
证明:
即:
可以参考 oi-wiki 的例子。
证明:
由 burnside 引理发现,在 \(g\) 作用下的不动点的充要条件是每一个循环置换里元素同色。
那么式子就很显然了。
首先置换群 \(G\) 包含的元素分别为: 旋转 \(1\) 个点,旋转 \(2\) 个点...旋转 \(n\) 个点
不难发现,旋转 \(k\) 个点的 \(c(g)=\gcd(n,k)\),原因如下:
所有循环置换所包含的元素个数相同,均为 \(\frac{\text{lcm(n,k)}}{k}\)。(旋转次数/旋转步长)
那么循环置换的个数便为 \(\frac{n}{\frac{\text{lcm}(n,k)}{k}}=\gcd(n,k)\)
由 polya 定理得:
化简可得:
直接计算即可,复杂度 \(\mathcal{O(n^{\frac{3}{4}})}\)
#include <cstdio>
const int Mod = 1e9 + 7;
int Add( int x , int y ) { x += y; return x >= Mod ? x - Mod : x; }
int Sub( int x , int y ) { x -= y; return x < 0 ? x + Mod : x; }
int Mul( int x , int y ) { return 1ll * x * y % Mod; }
int Quick_pow( int x , int po ) { int Ans = 1; for( ; po ; po >>= 1 , x = Mul( x , x ) ) if( po & 1 ) Ans = Mul( Ans , x ); return Ans; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }
int Div( int x , int y ) { return 1ll * x * Inv( y ) % Mod; }
int phi( int n ) {
int Ans = n;
for( int i = 2 ; i * i <= n ; i ++ )
if( n % i == 0 ) {
Ans = Ans / i * ( i - 1 );
while( n % i == 0 ) n /= i;
}
if( n > 1 ) Ans = Ans / n * ( n - 1 );
return Ans;
}
int T , n;
int main( ) {
scanf("%d",&T);
while( T -- ) {
scanf("%d",&n);
int Ans = 0;
for( int i = 1 ; i * i <= n ; i ++ )
if( n % i == 0 ) {
Ans = Add( Ans , Mul( Quick_pow( n , i ) , phi( n / i ) ) );
if( i * i != n )
Ans = Add( Ans , Mul( Quick_pow( n , n / i ) , phi( i ) ) );
}
printf("%d\n", Div( Ans , n ) );
}
return 0;
}
联系客服