数学不如小学生。数论质数判断试除法Miller–Rabin质数筛埃氏筛欧拉筛质因数分解试除法PollardRho算法最大公约数欧几里得算法裴蜀定理积性函数同余同余的基本性质同余定理欧拉定理费马小定理线性同余方程乘法逆元扩展欧几里得算法线性同余方程组CRTex

前言关于高次同余方程，有\(a^x\equivb(\text{mod}\p)\)和\(x^a\equivb(\text{mod}\p)\)两种类型，后者计算起来较为麻烦，下文就分别记述这两种高次同余方程。离散对数问题离散对数问题是在模\(p\)意义下求解\(\log_ab\)，这等价于形如\[a^x\equivb(\text{mod}\p)

这里我们先讨论一般情况(但一点也不简单,有很多厉害的定理),二次剩余之后再说.1.一元同余方程的具体解法我们考虑一般的一元同余方程\(f(x)\equiv0\pmodm\),容易

高次数学期望—OSUOSU!题目描述osu是一款群众喜闻乐见的休闲软件。我们可以把osu的规则简化与改编成以下的样子:一共有\(n\)次操作，每次操作只有成功与失败之分，成

求解\(a^x\equivb(\modp)\).大步小步算法，BSGS（baby-stepgiant-step），要求\(gcd(a,p)=1\)，可在\(O(\sqrtp)\)时间复杂度内求解。在\(p<=10^{16}\)时没有大问题。方