CPC

定义

一个整数$x$对另一个整数$p$的二次剩余，指$x^2$模$p$的余数。

我们称整数$d$为模$p$的二次剩余当且仅当$\exists x \in \mathbb{Z} \text{ s.t. } x^2 \equiv d \pmod p$；反之，称$d$为模$p$的非二次剩余。

上下文无歧义的情况下可以简称为剩余和非剩余。

置换

置换即$[\![1, n]\!] \triangleq \{1, 2, \dots, n\}$到自身的1-1变换：$[\![1, n]\!] \rightarrow [\![1, n]\!]$

$p: i \rightarrow a_i, (a_i \neq a_j, i \neq j)$，

其中$a_1, a_2, \dots, a_n$是$[\![1, n]\!]$的一个全排列，

称此置换为$n$阶置换，记为：

$$ p = \left( \begin{matrix} 1 & 2 & \cdots & n \\ a_1 & a_2 & \cdots & a_n \end{matrix} \right) $$

$n$阶置换共有$n!$个。

中国剩余定理可用于解一元线性方程组： $$ \begin{cases} x \equiv a_1 \pmod {m_1}\\ x \equiv a_2 \pmod {m_2}\\ \quad \vdots\\ x \equiv a_n \pmod {m_n} \end{cases} $$