文章目录

• 同余
• 前置知识 ————扩展欧几里得定理
• 什么是同余
• 公式表达
• 如何求一个数的同余
• 逆元
• 什么是逆元
• 逆元有什么用
• 如何求逆元
• 总结
• code:

• 同余

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

  • 什么是同余

    对于两个数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来求的
    另外两种分别是费马小定理（有局限性，但是非常简单）和线性推逆元(线性的去求逆元，适用于大规模求逆元)
    • 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/bb) == bx’+(a-a/bb)y’
    • ax + by == bx’ + ay’ - a/b*by’
    • ax + by == ay’ + b(x’-a/b*by)
    • x = y’,y = x’ - ab / by
    由此，我们可以得出求一个数的逆元的公式了

  • 总结

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

  code: