同余方程及扩欧求逆元
Morning_Glory
2018-11-05 12:32:41
* ## 同余
* ### 前置知识 ————扩展欧几里得定理
* ### 什么是同余
#### 对于两个数a,b,它们对于p取模结果相同,那么就称a和b在对p取模意义下同余
* ### 公式表达 $\color{red}{a≡b(mod)p}$
* ### 如何求一个数的同余
#### 利用扩展欧几里得定理
**我们将该公式转化一下 -> a%p == b%p **
**再变一下 -> a%p - b%p == 0**
**再变一下 -> a%p + (-b%p) ==0 **
**诶,这个时候我们可以发现这个和扩欧的公式好像啊(ax+by==c)**
**那么是不是将其看成扩欧就可以解决了呢**
**事实是————是的**
**但是我们知道可以用扩欧求出一个同余来了,但是好像还是不知道怎么求,也不知道同余可以干什么啊**
**事实上,在平常的写题中没有系数的同余都是很少出现的,一般同余是这么出现的-----**
**ax≡b%p 它会告诉你一个系数再让你去求解**
**更特殊的,b会等于1,这个时候,就扯到逆元上了**
* ## 逆元
* ### 什么是逆元
**形如ax≡1%p的x我们就称x是a的一个逆元,即a乘以x后mod p的答案是1**
* ### 逆元有什么用
**在部分对一个很大的数字取模防止答案爆long long以至于表达不出来的题目中,有时会发现会用到除法,可是用整数除法会有问题啊,那怎么办呢~~又是那怎么办呢~~? **
**这个时候逆元就派上用场了**
**我们发现,ax mod p ==1 时,这个x等于 $\frac{1}{a}$时就是一个最明显的满足条件的逆元,可是$\frac{1}{a}$不是一个整数啊,那怎么办呢?**
**实际上,一个数对于另一个数取模时,它的逆元是有无数个的,只不过$\frac{1}{a}$是最小的一个,也就是说,还会有ay mod p == 1的存在,
而这个时候,由于要对p取模,那么我们的a乘以x和乘以y的效果都是一样的,所以$\frac{1}{a}$可以被另一个常数y所代替,再想开一点,是不是所有的常数在对p取模时乘以$\frac{1}{a}$时都可以被y所代替呢, 由于p是不变的,所以这个结论是正确的**
* ### 如何求逆元
**求逆元有三种方式**
** 前面说过,有一种是可以用ex_gcd来求的**
**另外两种分别是费马小定理(有局限性,但是非常简单)和[线性推逆元](https://www.cnblogs.com/Morning-Glory/p/9892808.html)(线性的去求逆元,适用于大规模求逆元)**
* #### ax ≡ 1 mod b
* #### ax % b == 1
* #### ax - ax/b*b == 1
* #### 设y为ax/b,ax + (b(-y)) == 1
* #### 以下y为-y
* #### ax + by == gcd(a,b)
* #### gcd(a,b) == gcd(b,a%b) == gcd(b,a-a/b*b)
* #### ax + by == gcd(b,a-a/b*b) == bx'+(a-a/b*b)y'
* #### ax + by == bx' + ay' - a/b*by'
* #### ax + by == ay' + b(x'-a/b*by)
* #### x = y',y = x' - ab / by
**由此,我们可以得出求一个数的逆元的公式了**
### code:
```cpp
void ex_gcd(int a,int b,int &x,int &y)
{
if (b==0){x=1,y=0;return;}
ex_gcd(b,a%b,x,y);
int tmp=x;
x=y,y=tmp-a/b*y;
}
```
* ### 总结
* **同余是当两个数都模一个p它们的余数相同,那么我们就称这两个数同余**
* ** 逆元是同余的一种常见特殊情况 **
* **对于求逆元,首先要知道逆元有什么用:**
* ** 逆元是在取模运算中可以用乘法代替除法的巧妙工具**