1、定义：若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a（整除），则存在一个整数 x，使得 a/b≡a*x(modm)，则称 x 为 b 的模 m 乘法逆元，记为 b^(−1)(modm)。

2、b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，b^(m−2 )即为 b 的乘法逆元。
性质1：b*b^(-1)==1(modm)。

ACWing876. 快速幂求逆元

题意：给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible。
思路；根据逆元性质，a*a^(-1)==1(modp)，因为p是质数，由费马定理a^(p-1)==1(modp)，所以有a*a^(p-2)==1(modp)，所以要求的就是a^(p-2)。当且仅当a与p互质时有解（否则会有a%p==0,导致答案是0，不可能同余1）。

#include<iostream>
using namespace std;
typedef long long ll;
ll res;
ll quick_mod(int a,int k,int p)
{res=1;while(k){if(k&1) res=(ll)res*a%p;a=(ll)a*a%p;k=k>>1;}return res;
}
int main()
{int t,a,p;cin>>t;while(t--){res=0;cin>>a>>p;res=quick_mod(a,p-2,p);if(a%p) cout<<res<<endl;else cout<<"impossible"<<endl;}return 0;
}

扩展欧几里得算法

1、裴蜀定理：对于任意正整数a,b，一定存在非零整数x,y，使得ax+by=gcd(a,b)
0和任何数的最大公约数都是那个数

ACWing 877. 扩展欧几里得算法
题意：给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)。
 

#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{if(b==0) {x=1,y=0;return a;}int d=exgcd(b,a%b,y,x);//d就是a,b的最大公因数y-=a/b*x;return d;
}
int main()
{int n;scanf("%d",&n);while(n--){int a,b,x,y;scanf("%d%d",&a,&b);exgcd(a,b,x,y);printf("%d %d\n",x,y);}
}

ACWing 878. 线性同余方程

题意：求出一个x，使a*x≡b(modm)，如果无解则输出 impossible。
思路：a*x==b(mod m)→a*x==m*y+b，即ax-my=b，于是ax+my`=b(y,y`求出来的y值都是可以的，只需要a,b是正整数），利用扩展欧几里得算法求出x的值，再将x=x*b/d即是答案。另d=gcd(a,m)，无解的情况是当b%d==1，即当b不是d的倍数时，原方程无解，由裴蜀定理可知。

#include<iostream>
using namespace std;
typedef long long ll;
int exgcd(int a,int b,int &x,int &y)
{if(!b){x=1,y=0;return a;}int d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}
int main()
{int n,a,b,m;int x,y;scanf("%d",&n);while(n--){scanf("%d%d%d",&a,&b,&m);int d=exgcd(a,m,x,y);if(b%d)printf("impossible\n");elseprintf("%lld\n",(ll)x*b/d%m);}return 0;
}

高斯消元

ACWing 883. 高斯消元解线性方程组

思路：步骤：枚举每一列：①找到该列绝对值最大的一行；②将改行换到最上面；
③将改行第一个数化为1；④将该行下面所有行的第c列化为0。

#include<iostream>
#include<cmath>
using namespace std;
const double eps=1e-6;
const int N=110;
double a[N][N];
int n;
int gauss()
{int c,r;for(c=0,r=0;c<n;c++)//枚举每一列{int t=r;for(int i=r;i<n;i++)//找到该列绝对值最大的一行if(fabs(a[t][c])<fabs(a[i][c]))t=i;if(fabs(a[t][c])<eps) //当前列全为0continue;for(int i=0;i<n+1;i++)//将该行换到前面swap(a[t][i],a[r][i]);for(int i=n;i>=c;i--)//将改行第一个数变为1a[r][i]/=a[r][c];for(int i=r+1;i<n;i++)//将下面所有行的第c列消为0if(fabs(a[i][c])>eps)for(int j=n;j>=c;j--)a[i][j]-=a[r][j]*a[i][c];//将最上面一行每一列的系数乘当前行第一列的系数r++;}if(r<n){for(int i=r;i<n;i++)if(fabs(a[i][c])>eps)//最后这个系数不为0，说明无解。因为0!=0错误return -1;//无解return 1;//无穷多组解}for(int i=n-1;i>=0;i--){for(int j=i+1;j<n;j++)a[i][n]-=a[i][j]*a[j][n];//用下面所有行的每一列的系数来消去当前行其他的变量，只剩下xi}return 0;//唯一解
}
int main()
{scanf("%d",&n);for(int i=0;i<n;i++)for(int j=0;j<n+1;j++)scanf("%lf",&a[i][j]);int t=gauss();if(t==0)for(int i=0;i<n;i++){if(fabs(a[i][n])<eps) a[i][n]=0;//去掉输出-0.00的情况printf("%.2lf\n",a[i][n]);}else if(t==-1) printf("No solution\n");else printf("Infinite group solutions\n");return 0;
}