数学公式支持不能。。只能截图

b在模m 下存在逆元的条件： b与m互质（ 即gcd（b,m） == 1 ）。

求逆元又分三种方法，拓展欧几里得法，欧拉函数法，费小马法。从一般到特殊吧：

 1、拓展欧几里得法：

　　要求：a与m互质。

代码：

 

void ext_gcd(int a, int b, int &d, int &x, int &y){    if(!b)    {        d = a;        x = 1;        y = 0;    }    else    {        ext_gcd(b, a%b, d, y, x);        y -= x*(a/b);    }}int mod_inverse(int a, int m){    int x, y,d;    ext_gcd(a, m, d, x, y);    return (m + x % m) % m;}

 

 

2、欧拉函数法

　　要求：b与m互质。

  

 

代码：

 

int eurler_phi(int n){    int res = n;    for(int i = 2; i * i <= n; i++){        if(n % i == 0){            res = res / i * (i - 1);            while(n % i == 0) n /= i;        }    }    if(n != 1) res = res / n * (n - 1);    return res;}

 

 

3、费小马定理法

 

 

代码：可用快速幂幂