exgcd(扩展欧几里得算法）

当我们要求解ax+by=c时，注意到x和y应该是一个解集，c是a的x倍加上b的y倍的和，假设gcd(a,b)==d,那么，c也应该是d的整数倍，即d|c.

那么根据这，我们可以想到在思考ax+by=c的解集前，我们可以先思考ax+by=d的解集，注意到等式右边缩小了c/d倍，假设原解集为x1,y1,现解集为x2,y2，那么将x2,y2扩大c/d倍就得到了x1,y1。

现在问题变成求解ax+by=d的解集，看到gcd(a,b)=d,不由得想到辗转相除法，

即gcd(a,b)==gcd(b,a%b)，可以得到ax1+by1=d=bx2+(a%b)y2,将这个式子一直向下递归直到终态，即a%b==0,ax+(a%b)y=d,则x=1,y=0,d=a

假设最后一组解为Xn=1,Yn=0,那它是否与它的上一组解存在关系，可以不断递推直到得到x1,y1呢?

以下是数学推导

解集之间存在关系，向上递推回来，我们就得到了ax+by=d的一组特解x1,y1了

#include<bits/stdc++h>
using namespace std;
using ll=long long;

ll exgcd(ll a,ll b,ll &x,ll &y)
{
   if(!b)
   {
     x=1,y=0;
     return a;
   }
  //在向下递归时将x和y交换位置，当得到特解开始返回时
  //这一层的x变成了上一层的y,对应了x1=y2
  //而这一层的y变成了上一层的x，此时y1=x2，所以将y-=a/b*x，
  //y1=x2,真正的y1=x2-a/b*y2=y-a/b*x
  ll d=exgcd(b,a%b,y,x)
  y-=a/b*x;
  return d;
}

对于ax+by=d我们得到了特解x1,y1,如何得到解集呢？

事实上对于不定方程ax+by=d有特解x0,y0,就有解集

x=x0+k*(b/d)

y=y0-k*(a/d)

d是a，b的最大公约数，可以简单模拟以下有ax0+by0=d,成立，那么显然有a(x0+b/d)+b(y0-a/d)=d成立，乘开就相等了

这个定理帮我们引出一个非常重要的东西，那就x的最小非负整数解，一定为x0%(b/d),为什么呢?

x的解是以b/d为步长分布在坐标轴上的，那么不论x0为多少，最小非负整数解都为x0%(b/d)

那么现在来总解一下，我们通过ax+by=d求得了一组特解，命为x0,y0,将其扩大c/d倍，就得到了ax+by=c的一组特解x1,y1,再将x1%b/d就得到了ax+by=c的最小正整数解x2

归纳一下得到式子

x2=(x0*c/d)%(b/d)

y2=(c-a*x2)/b

只此就求得了ax+by=c的解

那就愉快的写例题吧 蓝桥4328线性同余方程

AC代码附上

#include<iostream>
using namespace std;
using ll = long long;
ll exgcd(ll a, ll b, ll& x, ll& y)
{
	if (!b)
	{
		x = 1, y = 0;
		return a;
	}
	ll d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
ll getabs(ll x)
{
	return (x < 0 ? -x : x);
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t; cin >> t;
	while (t--)
	{
		ll a, b, m; cin >> a >> b >> m;
		ll x, y, d = exgcd(getabs(a), getabs(m), x, y);
		if (b % d)
		{
			cout << -1 << endl;
		}
		else
		{
			x *= (a < 0 ? -1 : 1) * (b / d);
			x = (x % (m / d) + (m / d)) % (m / d);
			cout << x << endl;
		}
	}
	return 0;
}

值得注意的是我们要将式子转化为a*x+m*y=b

还要注意的是a可能为负，我们取绝对值再判断

再上一道例题蓝桥1317青蛙的约会

AC代码附上

#include<iostream>
using namespace std;
using ll = long long;
ll exgcd(ll a, ll b, ll& x, ll& y)
{
	if (!b)
	{
		x = 1, y = 0;
		return a;
	}
	ll d = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
ll getabs(ll x)
{
	return x <0 ? -x : x;
}
int main()
{
	ll _x, _y, m, n, L; cin >> _x >> _y >> m >> n >> L;
	ll a = m - n, b = L, c = _y - _x;
	ll x, y, d = exgcd(getabs(a), getabs(b), x, y);
	if (c % d)
	{
		cout << "impossible" << endl;
	}
	else
	{
		x *= (a < 0 ? -1 : 1) * (c / d);
		x = (x % (b / d) + (b / d)) % (b / d);
		cout << x << endl;
	}
	return 0;
}

注意转化，设k次向遇，_x+k*m=_y+k*n(mod L)

得到k(m-n)+Ly=_y-_x

欧克了