同余

• 前置知识 ————扩展欧几里得定理

• 什么是同余

  对于两个数a,b,它们对于p取模结果相同，那么就称a和b在对p取模意义下同余

• 公式表达

  $a\equiv b\left(mod\right)p$a≡b(mod)p

• 如何求一个数的同余

  利用扩展欧几里得定理
  我们将该公式转化一下 -> $a\%p==b\%p$a%p==b%p
  再变一下 -> $a\%p-b\%p==0$a%p−b%p==0
  再变一下 -> $a\%p+(-b\%p)==0$a%p+(−b%p)==0
  诶，这个时候我们可以发现这个和扩欧的公式好像啊 $(ax+by==c)$(ax+by==c)
  那么是不是将其看成扩欧就可以解决了呢
  事实是————是的
  但是我们知道可以用扩欧求出一个同余来了，但是好像还是不知道怎么求，也不知道同余可以干什么啊
  事实上，在平常的写题中没有系数的同余都是很少出现的，一般同余是这么出现的-----
  $ax\equiv b\%p$ax≡b%p 它会告诉你一个系数再让你去求解
  更特殊的， $b$b会等于1，这个时候，就扯到逆元上了

逆元

• 什么是逆元

形如 $ax\equiv 1modp$ax≡1 mod p的 $x$x我们就称 $x$x是 $a$a在 $modp$mod p意义下的一个逆元，即 $a$a乘以 $x$x后 $modp$mod p的答案是1

• 逆元有什么用

  在部分对一个很大的数字取模防止答案爆 $longlong$longlong以至于表达不出来的题目中，有时会发现会用到除法，可是用整数除法会有问题啊，那怎么办呢又是那怎么办呢？
  这个时候逆元就派上用场了
  我们发现， $axmodp==1$ax mod p==1 时，这个x等于 $\frac{1}{a}$a1​时就是一个最明显的满足条件的逆元，可是 $\frac{1}{a}$a1​不是一个整数啊，那怎么办呢？
  实际上，一个数对于另一个数取模时，它的逆元是有无数个的，只不过 $\frac{1}{a}$a1​是最小的一个，也就是说，还会有 aymodp==1的存在，
  而这个时候，由于要对p取模，那么我们的a乘以x和乘以y的效果都是一样的，所以 $\frac{1}{a}$a1​可以被另一个常数y所代替，再想开一点，是不是所有的常数在对p取模时乘以 $\frac{1}{a}$a1​时都可以被y所代替呢， 由于p是不变的，所以这个结论是正确的

• 如何求逆元

  • 求逆元有三种方式
    前面说过，有一种是可以用 $ex\_gcd$ex_gcd来求的
    另外两种分别是费马小定理（有局限性，但是非常简单）和线性推逆元(线性的去求逆元，适用于大规模求逆元)
    • $ax\equiv 1modb$ax≡1mod b
    • $ax\%b==1$ax%b==1
    • $ax-ax/b\ast b==1$ax−ax/b∗b==1
    • $设y为ax/b,ax+\left(b\right(-y\left)\right)==1$设y为ax/b,ax+(b(−y))==1
    • $以下y为-y$以下y为−y
    • $ax+by==gcd(a,b)$ax+by==gcd(a,b)
    • 这个公式就可以套用扩欧了，下面再推一次扩欧
      $gcd(a,b)==gcd(b,a\%b)==gcd(b,a-a/b\ast b)$gcd(a,b)==gcd(b,a%b)==gcd(b,a−a/b∗b)
      $ax+by==gcd(b,a-a/b\ast b)==b{x}^{\prime }+(a-a/b\ast b)y^{\prime }$ax+by==gcd(b,a−a/b∗b)==bx′+(a−a/b∗b)y′
      $ax+by==b{x}^{\prime }+a{y}^{\prime }-a/b\ast y^{\prime }$ax+by==bx′+ay′−a/b∗y′
      $ax+by==a{y}^{\prime }+b(x^{\prime }-a/b\ast y)$ax+by==ay′+b(x′−a/b∗y)
      $x=y^{\prime },y=x^{\prime }-a/b\ast y$x=y′,y=x′−a/b∗y

  由此，我们可以得出求一个数的逆元的公式了
  $ex\_gcd(a,mod,ni,x)$ex_gcd(a,mod,ni,x)// $a$a为要求的数的逆元， $mod$mod为模数， $ni$ni为逆元， $x$x什么都不是
  $ni=(ni+mod)\%mod$ni=(ni+mod)%mod;//防止负数

总结

• 同余是当两个数都模一个p它们的余数相同，那么我们就称这两个数同余
• 逆元是同余的一种常见特殊情况
• 对于求逆元，首先要知道逆元有什么用：
• 逆元是在取模运算中可以用乘法代替除法的巧妙工具

code:

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;
}