扩展欧几里得算法

扩欧代码（时间复杂度O(logn)）

求ax+by=gcd(a,b)的一组整数解

int gcd(int a,int b)
{
	if(b==0)return a;
	return gcd(b,a%b);
}
int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	int x1,y1,d;
	d=exgcd(b,a%b,x1,y1);
	x=y1,y=x1-a/b*y1;
	return d;
}

扩欧的应用

• 求解不定方程
• 求解同余方程
• 求解模的逆元

求解不定方程

求不定方程ax+by=c的一组整数解

思路

若gcd(a,b)|c(gcd(a,b)是c的因子)，则有整数解

先用扩欧求ax+by=gcd(a,b)的解

再乘以c/gcd(a,b)，即得原方程的特解

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
    
int exgcd(int a,int b,int &x,int &y)
{
  if(b == 0) {x=1, y=0; return a;}
  int x1, y1, d;
  d = exgcd(b, a%b, x1, y1);
  x = y1, y = x1-a/b*y1;
  return d;
}
int main()
{
  int a, b, c, x, y;
  cin >> a >> b >> c;
  int d = exgcd(a,b,x,y);
  if(c%d == 0)printf("%d %d",c/d*x,c/d*y);
  else puts("none");
  return 0;
}

求解同余方程

给定整数a,b,m，求解同余方程ax≡b(mod m)，如果x存在整数解，输出任意一个，不存在输出none

思路

把同余方程转化为不定方程，

由ax≡b(mod m)

得ax=m(-y)+b

ax+my=b

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
    
int exgcd(int a,int b,int &x,int &y){
  if(b == 0){x = 1, y = 0; return a;}
  int x1, y1, d;
  d = exgcd(b, a%b, x1, y1);
  x = y1, y = x1-a/b*y1;
  return d;
}
int main(){
  int a, b, m, x, y;
  scanf("%d%d%d", &a, &b, &m);
  int d = exgcd(a, m, x, y);
  if(b%d == 0) 
    printf("%d", 1ll*x*b/d%m);
  else puts("none");
  return 0;
}

求解模的逆元

a与m互质时，对于方程ax≡1(mod m)，求a的乘法逆元x(0<x<m)

思路

转化为同余方程，等价于ax+my=1

(x%m+m)%m即为答案，这是为了得到最小正整数

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
    
int exgcd(int a,int b,int &x,int &y){
  if(b == 0){
    x = 1, y = 0; return a;
  }
  int x1, y1, d;
  d = exgcd(b, a%b, x1, y1);
  x = y1, y = x1-a/b*y1;
  return d;
}
int main(){
  int a, m, x, y;
  scanf("%d%d", &a, &m);
  exgcd(a, m, x, y);
  printf("%d", (x%m+m)%m);
  return 0;
}