洛谷p1082 同余方程

洛谷1082 同余方程

[a x equiv 1 pmod {b} ]

根据同余式的定义，我们可以知道一个一次同余方程一定可以写成
ax+by=c的不定方程形式
简单证一下吧
比如

[a x equiv c pmod {b} ]

我们引入一个变量k，根据mod运算的性质，我们可知该式一定可以写为：ax-kb=c的形式
我们定义y=-k;所以该式就变为了：ax+by=c的形式。
我们根据贝祖定理可知：给出两个数a,b，设d=gcd(a,b)，则一定有ax+by=d。因为ax,by,一定是d的倍数，所以ax+by=c中的c也一定是d的倍数
即然c是d 的倍数,那么一定有

[c equiv 0 pmod d ]

我们再回到题上去看
本题中我们的c 是1那一定有1%gcd(a,b)=0;所以我们可以得出
若同余方程有解，则gcd(a,b）=1
接下来方程就转化为ax+by=d的形式
我们要求出最小的x,扩欧跑一遍
因为我们要求的是最小的X(所得到的x有可能为负或不为最小)我们对所得的x处理一下输出即可
代码如下

#include<iostream>
#include<cstdio>
using namespace std;
long long x,y,a,b;
void exgcd(long long a,long long b){
	if(b==0){
		x=1;
		y=0;
		return ;
	}
	exgcd(b,a%b);
	long long tmp=x;
	x=y;
	y=tmp-a/b*y;
}
int main(){
	cin>>a>>b;
	exgcd(a,b);
	x=(x%b+b)%b;
	cout<<x; 
	return 0;
}

结束
我们求出的这个最小x也就是在mod该模数下的最小逆元