xqmmcqs’s Blogs

题目链接 http://www.lydsy.com/JudgeOnline/problem.php?id=2045

题目链接 http://www.lydsy.com/JudgeOnline/problem.php?id=2301

题目链接 http://www.lydsy.com/JudgeOnline/problem.php?id=2818

题目链接 http://www.lydsy.com/JudgeOnline/problem.php?id=2190

使用官方反代，编辑插件，将google-captcha.php和script.js中所有google.com替换成recaptcha.net即可正常使用。 注意每次升级插件后都要重新修改。

定义 对于只有整数参与的多项式运算，使用快速数论变换（Number-Theoretic Transform，NTT）可以减小精度误差。

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

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

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

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

定义 对于整数\(a\)和素数\(p\)，如果存在一个整数\(x\)使得\(x^2\equiv a\quad(mod\ p)\)，那么称\(a\)是模\(p\)的二次剩余；如果对于任意\(x\)，\(x^2\equiv a\quad(mod\ p)\)都不成立，则称\(a\)是模\(p\)的二次非剩余。

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

定义 Pollard_rho算法是一种快速分解大整数的随机化算法。

定义 Miller_Rabin算法是一种随机化素数测试算法。

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