luo gu

由$a*x \equiv1 (\mod b)$ 推导为扩展欧几里得

• ->$a*x \mod b == 1 \mod b$
• ->$a*x \mod b =1$
• 即-> $ax = nb+1$(n是常数)
• -> $ax-nb=1$
• ->$ax+yb=1$ (y = -n,常数无影响)
  模板：

  #include <iostream>
  #include <string.h>
  #include <queue>
  
  using namespace std;
  
  int exgcd(int a,int b,long long & x,long long & y) {
  	if (b == 0) {
  		x = 1;
  		y = 0;
  		return a;
  	}
  	int res = exgcd(b,a%b,x,y);
  	// 回溯的时候进行  推倒x,y
  	long long temp = y;
  	y = x - (a/b)*y;
  	x = temp;
  	return res;
  }
  
  
  int main() {
  	int a,b;
  	long long x,y;
  	cin >> a >> b;
  	exgcd(a,b,x,y);
  	if (x > 0) {
  		while (x > 0) 
  			x -= abs(b);
  		x += abs(b);
  		cout << x << endl;
  	}
  	else {
  		while (x < 0) 
  			x += abs(b);
  		cout << x << endl;
  	}
  	return 0;
  }