逆元、扩展欧几里得算法、高斯消元
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
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< 扩展欧几里得算法
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
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
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
#include
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=c;i--)//将改行第一个数变为1a[r][i]/=a[r][c];for(int i=r+1;ieps)for(int j=n;j>=c;j--)a[i][j]-=a[r][j]*a[i][c];//将最上面一行每一列的系数乘当前行第一列的系数r++;}if(reps)//最后这个系数不为0，说明无解。因为0!=0错误return -1;//无解return 1;//无穷多组解}for(int i=n-1;i>=0;i--){for(int j=i+1;j
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！