CSP 202012 题解

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

阅读更多

快速傅里叶变换

定义

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

阅读更多

初等数论

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

阅读更多

BSGS算法

定义

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} \]

阅读更多

类欧几里得算法

定义

给定\(a,b,c,n\)求对应函数的值:

\(f(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor\)

\(g(a,b,c,n)=\sum_{i=0}^n i\lfloor\frac{ai+b}{c}\rfloor\)

\(h(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{ai+b}{c}\rfloor^2\)

阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×