扩展欧几里得与二元不定方程

二元不定方程,就是形同ax+by=c的二元方程,
只不过有无数组解罢了。
还有原谅我蒟蒻,不会用字母的写法,只好直觉+小学数学写法了

我们可以使用辗转相除法来解决(过渡好生硬啊)

我们首先来看一组例子
为了方便理解,特将每个多项式系数都写了出来,同时并没有将符号带进括号

37x-107y=25

37x-(37*2+33)y=25
37(x-2y)-33y=25

(-33*-1+4)(x-2y)-33y=25
-33(-x+3y)+4(x-2y)=25

(4*-8-1)(-x+3y)+4(x-2y)=25
4(9x-26y)-1(-x+3y)=25 

(-1*4+0)(9x-26y)-(-x+3y)=25
-(-37x+107y)+0(9x-26y)=25

我们自下而上看
因为系数0的存在
那么9x-26y=0
我们又可以惊奇的发现
9x-26y正好在它上面式子中出现了。
考虑整体思想,将括号内的多项式(就是(x-+3y))(or单项式)看做一个整体,便可求得(-x+3y)的值(当做一次方程来做)
再如此处理,便可将x,y的一对特值找出来 

那怎么求出其他的特值捏?

对于一个减法,我们总可以用正号将一个减数变成加数

那么就变成了两个数和相等的情况(真啰嗦)

那么我们这一个整数d

ax+by=c=a(x+bd)+b(y+ad)=c

因为将括号开出来时就将bd 和 ad消去了,所以两数的和不会改变

所以(x+bd)与 (y-ad)也是一组特解

这样有条件枚举d便会找到想要的特解

在理解了如何利用辗转相除法来求解后,再来看程序实现

#include<iostream>
using namespace std;
void exgcd(long long a,long long b,long long &x,long long &y,long long r)
{
	if(b==0)//有了系数0,为什么0肯定在b上?请回看gcd
	{
		x=r/a; //最终结果有可能系数为非零整数
		y=0;//e.....
		return ;
	}
	exgcd(b,a%b,x,y,r);//辗转相除
    //因为这里是回溯,注意下面写下一层就是递归意义上的下一层。可能理解起来有些别扭,原谅我吧233.
	long long k=x;//暂时保留下一层的x,注意是自下而上计算的
	x=y;//可以参考例子,例子我觉得自己写的很公正(就是有些别扭)
	y=k-a/b*y;//k是下一层的x,下一层的x是这一层的x-这一层的x,y的系数的商*这一层的x+这一层的y(不乘任何数)(这里的y是变量,储存的是下一层的x),便得到了这一层的y。
	return ;
}
int main() 
{
	long long a,b,l;//ab为xy的系数,l为化成ax+by=c后的c
	cin>>a>>b>>l;
	long long x,y;
	exgcd(a,b,x,y,l); //扩展欧几里得是特殊的二元不等式
	cout<<x<<" "<<y;
}

扩欧只需要将ax+by=c中的c变为1即可

原文地址:https://www.cnblogs.com/Lance1ot/p/8494383.html