逆元的四种求法

a,x,p均为正整数,p是质数,a*x≡1(mod p)

给出a,p求最小的符合条件的x(也就是a的逆元，a^-1(mod p))。

法一：快速幂 O（log p）

根据费马小定理可得 a*a^p-2=a^p-1≡1(mod p)，此时a^-1≡a^p-2(mod p)。用快速幂求即可。

1 int p,x=1,w,a,xx;
2 w=p-2;
3 xx=a;
4 while(w){
5    if(w&1)a*=xx,a%=p;
6     xx*=xx;xx%=p;
7     w/=2;
8 }

法二：扩展欧几里德(不要求p是质数，只要求a,p互质) O（log a）

我们知道，扩展欧几里得可以求给定正整数a,b的关于整数x,y的不定方程 a*x+b*y=gcd(a,b)的某一组解。

此时，只要将该方程写作a*x+p*y=1并求出x即可。

1 void exgcd(int a,int b,int &x,int &y){//对a,b求逆元，注意勿省略&，修改的是x,y本身而不是传递的值
2     if(b==0){
3         x=1;
4         y=0;
5         return ;
6     }
7     gcd(b,a%b,y,x);
8     y-=x*(a/b);
9 }

法三：线性求逆元 O(a)

这种方法比较适用于求1~a对某一p的逆元。

若 p÷a=k…r。

则有 a*k+r≡0(mod p) k+r*a^-1≡0(mod p) a^-1≡-k*r^-1(mod p)

代码也比较好写。

1 const int sz=1e6+5;
2 int a,p,x[sz];//x[i]表示i的逆元
3 x[1]=1;
4 for(int i=2;i<=a;i++)x[i]=-(p/i)*x[p%i],x[i]=(x[i]%p+p)%p;

法四：法三的……优化？（对于求单个数的逆元来说算是吧……） O(log a)

其实以上三个方法都比较容易找到，写这篇博客的真正目的是在书上看见了法四，想分享一下。

对于法三，其实求每个a的逆元，只要求出(p%a)的逆元即可。则可以递归地去做。