CS 保研机试复习记录

这次 T3 T4 都很简单，可惜没有把握住。

突发奇想刷了刷去年 CSP 的题，这几年难度真是越来越高了

定义

快速傅里叶变换（Fast Fourier Transform，FFT）用于在\(O(n\log n)\)时间内求解多项式乘法。

数论是纯粹数学的分支之一，主要研究整数的性质。

定义

BSGS 算法用于求解关于\(x\)的方程\(a^x\equiv b\pmod p\)的解。

定义

素数筛用于求出\([2,n]\)范围内的质数。

定义

给出一个线性同余方程组：\(\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\ \ldots \\x\equiv a_n\pmod{m_n}\end{cases}\)，其中\(m_i\)两两互质，中国剩余定理用于求这样的方程组的解。

定义

乘法逆元通常用于在同余式中进行除法运算，其内容为：若\(ax\equiv 1\pmod p\)， 则称\(a\)在模\(p\)意义下的乘法逆元为\(x\)。

莫比乌斯函数

定义

根据唯一分解定理，\(n=\prod_{i=1}^{k} p_i^{a_i}\)。 \(\mu\)定义为 \[\mu(n)=\begin{cases}\mu(1)=1\\ \mu(n)=(-1)^k,\quad \forall a_i=1\\ \mu(n)=0,\quad \exists a_i>1\end{cases} \]