【题目描述】
一串项链上有$n$颗珠子,用$n$种颜色给它们染色(不一定都要用到),有多少种方案?通过已有方案进行旋转得到的染色方案不算。答案对$p$取模。

【输入格式】
两个整数$n,p$。

【输出格式】
一行一个整数表示总方案数模$p$。

$n\le 10^9$

题解

$\operatorname{Burnside}$引理

设$A$和$B$为有限集合,$X$表示所有从$A$到$B$的映射集合(着色方案集合)。$G$是一个置换群,$X/G$表示$X$所有元素的轨道的集合(去重),$X^g$表示$X$中在某个$G$中置换$g$作用下的不动元素集合,则有$$|X/G|=\frac{1}{|G|}\sum\limits_{g\in G}|X^g|$$

看不懂没关系 用人话解释一下

比如给一个正方形的4个顶点染2种颜色

$X$是着色方案集合 这里先不考虑重复 每个点都有两种颜色可染 所以着色方案有$2^4=16$种 这里我们可以把这个正方形旋转0°,90°,180°或270°,所以$G$就是{旋转0°,旋转90°,旋转180°,旋转270°}。

先算一下$X^{g_1}$也就是旋转0°后 16种方案里有多少种4个角的颜色相对没变的

然而旋转0°也就是不旋转 16种都不会变

$X^{g_2}$旋转90°呢 只有2种 就是4个顶点颜色都一样的2种

$X^{g_3}=4$旋转180°时$\texttt{RRRR}\quad\texttt{BBBB}\quad\texttt{RBRB}\quad\texttt{BRBR}$都是合法的

$X^{g_4}$同$X^{g_2}$。

所以此题答案是$\frac{1}{4}(16+2+4+2)=6$!!!

但是集合$G$的大小是$n$级别的 集合$X$的大小更是指数级的 我们也不知道怎么计算$X^g$

于是我们需要用到$\operatorname{Polya}$定理

先简单介绍一下什么是置换

$$\begin{pmatrix}1 & 2 & 3 & 4 \ 3 & 1 & 2 & 4 \end{pmatrix}$$

这个置换是上下对应的 表示把$1$的颜色给$3$,把$2$的颜色给$1$,把$3$的颜色给$2$,把$4$的颜色给$4$。

所以如果把正方形的四个顶点顺时针顺序标为$1,2,3,4$

那么顺时针旋转90°就对应这样的一个置换:

$$\begin{pmatrix}1 & 2 & 3 & 4 \ 2 & 3 & 4 & 1 \end{pmatrix}$$

任意一个置换都能分解成若干个循环置换的乘积

什么又是循环置换?(不想写了放张图)

嗯$\begin{pmatrix}1 & 2 & 3 & 4 & 5 \ 3 & 1 & 2 & 5 & 4 \end{pmatrix}$就是这两个循环置换合在一起

这个循环置换$\begin{pmatrix}1 & 3 & 2 \ 3 & 2 & 1 \end{pmatrix}$按顺序排一下也就是$\begin{pmatrix}1 & 2 & 3 \ 3 & 1 & 2 \end{pmatrix}$
和这个循环置换$\begin{pmatrix}4 & 5 \ 5 & 4 \end{pmatrix}$

然后回到刚才那个引理 一个置换$g$可以表示为若干个循环置换的乘积 然而对于每个循环置换 这个循环置换里的每个元素 的颜色 必须全部一样 才能保证经过置换后每个元素的颜色都不变(这个不好理解)

设$m$是颜色种类数$c(g)$是$g$最多被分解成几个循环置换的乘积 那么有$|X^g|=m^{c(g)}$

把这个代入刚才那个$\operatorname{Burnside}$引理

得到$\operatorname{Polya}$定理:

$$|X/G|=\frac{1}{|G|}\sum\limits_{g\in G}m^{c(g)}$$

看一下刚才那个正方形的例子
$g_1$是$\begin{pmatrix}1 & 2 & 3 & 4 \ 1 & 2 & 3 & 4 \end{pmatrix}$
那么$c(g_1)$是$4$总之自己算一下得到$c(g_2)=1$,$c(g_3)=2$,$c(g_4)=1$
答案就和刚才一样$\frac{1}{4}(2^4+2^1+2^2+2^1)=6$

那么这题怎么办呢 集合$G$很容易找 就是顺时针旋转过$1\sim n$个珠子(旋转过$n$个就是没旋转) 所以$|G|=n$。

找找规律 发现顺时针旋转$i$个珠子得到的置换最多能被分解成$\gcd(i,n)$个循环置换(原因我也忘了)

所以枚举$n$的因数$d$表示$\gcd(i,n)=d$那么一定有$\gcd(\frac{i}{d},\frac{n}{d})=1$且$\frac{i}{d}\le \frac{n}{d}$

所以$\gcd(i,n)=d$的$1\le i\le n$的个数就是$\varphi(\frac{n}{d})$(欧拉函数)

答案就是$$\frac{1}{n}\sum\limits_{d|n}n^d\varphi(\frac{n}{d})$$

预处理一下质数 时间复杂度据说是$O(n^{0.75})$?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int ttt, n, mod, tot;
int prime[40005], pr;
bool np[40005];

inline int read() {
int x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return x * f;
}

void write(int x) {
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}

inline void getprime() {
for (int i = 2; i <= 36000; i++) {
if (!np[i]) {
prime[++pr] = i;
}
for (int j = 1; j <= pr && (i * prime[j] <= 36000); j++) {
np[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}

inline int getphi(int x) {
int ret = x;
for (int i = 1; prime[i] * prime[i] <= x; i++) {
if (x % prime[i] == 0) {
ret = ret - ret / prime[i];
while (x % prime[i] == 0) x /= prime[i];
}
}
if (x > 1) {
ret = ret - ret / x;
}
return ret % mod;
}

inline int fpow(int x, int t) {
int ret = 1; x %= mod;
for (; t; t >>= 1, x = x * x % mod) if (t & 1) ret = ret * x % mod;
return ret;
}

inline int solve(int x) {
int ret = 0;
for (int i = 1; i * i <= x; i++) {
if (x % i == 0) {
ret = (ret + fpow(x, i - 1) * getphi(x / i) % mod) % mod;
if (x != i * i) {
ret = (ret + fpow(x, x / i - 1) * getphi(i) % mod) % mod;
}
}
}
return ret;
}

int main() {
ttt = read();
getprime();
while (ttt--) {
n = read(); mod = read();
write(solve(n)); puts("");
}
return 0;
}

评论