同余方程（扩展欧几里德算法）

同余方程

时间限制: 1 Sec  内存限制: 128 MB

题目描述

求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。

输入

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

输出

输出只有一行，包含一个正整数 x0，即最小正整数解。输入数据保证一定有解。

样例输入

复制样例数据

3 10

样例输出

7

提示

对于 100%的数据，2 ≤a, b≤ 2,000,000,000。

ax≡1(mod b) -> ax%b - 1%b≡0,因为b大于2,所以ax%b=1,马上想到ax=by+1，即ax-by=1，这不就是扩展欧几里德吗？

把a求出来，因为a有可能为负的，但题目要正的，那么怎么办呢，可以问by借点(x+mb)a+b(y-ma)=1还是成立的,所以只要在x上加m倍的b就行了。

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

LL a, b;
LL ans;

void ex_gcd(LL a, LL b, LL &x, LL &y){
	if(!b){
		x = 1, y = 0;
		return ;
	}
	ex_gcd(b, a % b, y, x);
	y -= x * (a / b);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%lld %lld", &a, &b);
	LL x, y;
	ex_gcd(a, b, x, y);
	while(x < 0) x += b;
	printf("%lld\n", x);

	return 0;
}
/**/