逆元

标签：b% return tx int 逆元 mod

        乘法逆元，一般用于求（a / b）(mod p)的值（p 通常为质数），是解决模意义下分数数值的必要手段。

        关于求余，有以下三种规则：

        加法：(a+b)%m=(a%m+b%m)%m

        减法：(a−b)%m=(a%m−b%m)%m

        乘法：(a∗b)%m=(a%m∗b%m)%m

        但是这个规则在除法不适用，所以就要用到乘法逆元。

逆元的概念

若a*x≡1(mod b)，a,b互质，则称x为的逆元，记为a^-1。

根据逆元的定义，可转化为a*x+b*y=1,用拓展欧几里得法求解。逆元可以用来在计算（t/a)mod b时，转化为t*a^-1 mod b。

那么逆元怎么求呢？我们来看3种方法。

1. 利用快速幂和扩展欧几里得算法求逆元。

         void exgcd(int a,int b,int c,int &x,int &y){

                 If(a==0){

                           x=0;y=c/b;return;

                  }

                 else{

                          int tx,ty;

                          exgcd(b%a,a,tx,ty);

                          x=ty-(b/a)*tx;

                          y=tx;

                          return;

                  }

        2.费马小定理

        p是一个质数，并且a % p≠0，则有a ^{p − 1}≡1 ( mod p )，a ^{p − 2}≡a⁻¹，即可得到逆元。

        参考代码：

        int quic_pow(int a,int n,int mod){

                  int ans=1;

                  while(n){

                           If(n&1)ans=(and*a)%mod;

                           a=(a*a)%d;

                           n >>=1;

                  }

                  return ans;

           }

        int inv(int a,int p){

                   return quick_pow(a,p-2,p);

        }

       3.线性求解逆元

        用于求一连串数字对于一个 mod p 的逆元，并且大多数题只能用这种方法，别的算法都比这些要求一串要慢。

       首先我们有一个,1^(−1) = 1 (mod p)

       然后设 p=k*i+r,(1<r<i<p)也就是k是p/i的商，r是余数。

       再将这个式子放到(mod p)意义下就会得到：k∗i+r =0(mod p)

       然后乘上i^(-1), r^(−1)就可以得到:

        k ∗r−1+i−1=0(mod p)

        i^(-1)=(−k)∗r−1(mod p)

        i^(-1 =−⌊p/i⌋∗(p mod i)^(-1)(mod p)

       然后，我们就可以从前面推出当前的逆元了。

       例题 洛谷P3811

标签：b%,return,tx,int,逆元,mod
From： https://www.cnblogs.com/ddfy198811/p/17027734.html