关于数学

对于“同余方程”“扩展欧几里得”“贝祖定理”“乘法逆元”以及“费马小定理” ### 同余方程

只是一个方程，形如\(a\times x\equiv c \pmod b\)

扩展欧几里得

是求解形如 \(a\times x+b\times y= \gcd(a,b)\)的\(x,y\)的解

贝祖定理

对于数\(a,b\) 一定存在一对\(x,y\) 使得 \(a\times x+b \times y=\gcd(a,b)\)

乘法逆元

若\(a\times x \equiv 1 \pmod b\) 并且\(a,b\) 互质.我们就称\(x\) 为 \(a\) 在\(\pmod b\)意义下的乘法逆元,记为\(a^{-1}\)

费马小定理

若 \(p\) 是素数, \(a\) 是正整数,且\(a,p\) 互质

则\(a^{p-1}\equiv 1\pmod p\)

通俗的讲，扩展欧几里得是为了求解同余方程这种类型的题目而产生的，而贝祖定理（也叫裴蜀定理）证明了扩展欧几里得算法的正确性（证明其一定有解）

而乘法逆元是为了处理计算机不能很好的对除法进行运算，没法取倒数，而产生的一个新定义，在数学里面看起来就像是一个数的倒数，但是在计算机里面，这就是一个新定义，乘法逆元的符号就是\(a^{-1}\)

并且求解乘法逆元用扩展欧几里得就好

即同余方程中 \(c\) 等于 \(1\) 的情况

---

8.31 update:

求解乘法逆元较多的是快速幂与乘法逆元，其中快速幂必须保证a，p互质

//线性：
inv[1] = 1;
for(int i = 2; i < p; ++ i)
   inv[i] = (p - p / i) * inv[p % i] % p;
//快速幂
for (; b; b >>= 1)
{
   if (b & 1) res = res * a % mod;
   a = a * a % mod;
}
return res;


ksm(a, p-2, p);