同余方程

线性同余方程,也就是给定a,b,m,求一个整数x满足a*x≡b(mod m)a*x≡b(mod m),然后因为ax≡b(mod m)ax≡b(mod m)等价于

ax−b是m的倍数,不妨设y为一个负数,那么这个方程可以改写为ax+m*y=b

于是 我们可以通过拓展欧几里得算法求出特解,然后(x%b+b)%b(x%b+b)%b来达到最小值的效果.

如例题：

题目描述
求关于x的同余方程ax≡1(modb)ax≡1(modb)的最小正整数解。

输入格式
输入只有一行，包含两个正整数a,b,用一个空格隔开。

输出格式
输出只有一行,包含一个正整数x，表示最小正整数解。

输入数据保证一定有解。

数据范围
2≤a,b≤2∗1092≤a,b≤2∗109
样例
输入样例：
3 10
输出样例：
7

给出代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A,B,x,y;
ll ex_gcd(ll a,ll b,ll &x,ll &y)//模板
{
	if(!b)
	{
		x=1;y=0;return a;
	}
	ll d=ex_gcd(b,a%b,x,y);
	ll t=x;x=y;y=t-y*(a/b);
	return d;
}
int main()
{
	cin>>A>>B;
	ex_gcd(A,B,x,y);
	cout<<(x%B+B)%B<<endl;//得到最小的
	return 0;
}