CS 保研机试复习记录

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

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

定义

对于只有整数参与的多项式运算，使用快速数论变换（Number-Theoretic Transform，NTT）可以避免浮点运算带来的精度误差。

定义

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

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

定义

线性筛用于在\(O(n)\)的时间复杂度内求出\(1\ldots n\)的积性函数值。

定义

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

定义

对于整数 \(a\) 和奇素数 \(p\)，若存在整数 \(x\) 使 \(x^2 \equiv a \pmod p\)，则称 \(a\) 是模 \(p\) 的二次剩余；否则称 \(a\) 是模 \(p\) 的二次非剩余。

定义

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