扩展欧几里得算法

算法描述

扩展欧几里得算法可直接计算不定方程方程 $ax+by=gcd(a,b),(a,b\in Z)$ 的一组整数解，并返回 $\gcd(a,b)$。

理论基础

裴蜀定理(Bézout’s lemma)

定理描述

对任何整数 $a$、${\displaystyle b}$ 和 ${\displaystyle c}$，关于未知数 ${\displaystyle x}$ 和 ${\displaystyle y}$ 的线性丢番图方程：${\displaystyle ax+by=c}$ 当且仅当 $\gcd(a,b)|c$ 时有整数解。

证明

先证：

对于任意整数 $a,b$ ，存在一对整数 $x,y$ ，满足 $ax+by=gcd(a,b)$。

1. 在欧几里得算法(Euclidean algorithm)的最后一步，即 b=0 时，显然有一对整数 $x=1,y=0$，使得 $a \times 1+0 \times 0=gcd(a,0)$；
2. 若 $b>0$ ，则$\gcd(a,b)=\gcd(b,a\bmod b)$。假设存在一对整数 $x,y$ ，满足 $b \times x+(a \bmod b)\times y=gcd(b,a\bmod b)$。那么 $bx+(a \bmod b)·y=bx+(a−b⌊\frac{a}{b}⌋)·y=ay+b· (x−⌊\frac{a}{b}⌋y)$。令 $x′=y,y′=x−⌊\frac{a}{b}⌋y$，得到 $ax′+by′=\gcd(a,b)$。

由数学归纳法，命题成立。

证毕。

又证：

对于更为一般的方程 $ax+by=c $，当且仅当$ gcd(a,b)∣c$，该方程有整数解。

由于证明过程复杂，以下给出简单的感性认识。

我们可以先求出 $ax+by=gcd(a,b)$ 的一组特解 $x_0,y_0$，然后令$ x_0,y_0$ 同时乘上 $\frac{c}{gcd(a,b)}$，就得到了$ ax+by=c$ 的一组特解$ \frac{c}{gcd(a,b)}x_0,\frac{c}{gcd(a,b)}y_0$。

算法模板

int ex_gcd(int a,int b,int &x,int &y)//x,y的值也需要返回，在此作为引用。
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	else
	{
		int gcd=ex_gcd(b,a%b,x,y);
		//向上递推
		int temp=x;
		x=y;
		y=temp-a/b*y;
		return gcd;
	}
}

算法应用

求解裴蜀等式

理论描述

当且仅当 $\gcd(a,b)|c$ 时方程有解。

扩展欧几里得算法能求出 $ax+by=gcd(a,b)$ 的一组特解。当递归至 $b=0$ 时，此时该方程有一组解 $x=1,y=0$，此值按照规则 $x′=y,y′=x−⌊\frac{a}{b}⌋y$ 向上层返回。

于是得到一组特解 $x_0,y_0$ 使得 $ax_0+by_0=\gcd(a,b)$，等式两边同时乘上 $\frac{c}{gcd(a,b)}$，就得到了 $ax+by=c$ 的一组特解 $\frac{c}{gcd(a,b)}x_0,\frac{c}{gcd(a,b)}y_0$。
下面给出裴蜀等式的通解：

$$x=\frac{c}{d}x_0+k\frac{b}{d},y=\frac{c}{d}y_0-k\frac{a}{d}(k\in Z,d=gcd(a,b))$$

$x$ 的最小正整数解为 $(x_0 \frac{c}{d}\bmod \frac{b}{d}+\frac{b}{d})\bmod \frac{b}{d}$。

例题：洛谷CF7C Line

题目描述

A line on the plane is described by an equation $Ax+By+C=0$ . You are to find any point on this line, whose coordinates are integer numbers from $-5·10^{18}$ to $5·10^{18}$inclusive, or to find out that such points do not exist.

输入格式

The first line contains three integers $A$ ,$ B$ and$C$$ ( -2·10^{9}\le A,B,C\le2·10^{9} )$ —corresponding coefficients of the line equation. It is guaranteed that $A^{2}+B^{2}>0$ .

If the required point exists, output its coordinates, otherwise output -1.

题意翻译

一条直线：$Ax+By+C=0$（$A,B$ 不同时为 $0$），找到任意一个点（在 $-5\times 10^{18}$$\sim$$5\times 10^{18}$ 之间）让它的横纵坐标均为整数，或者确定没有这样的点。
输入：$A，B，C$

输出：该点坐标，没有就输出 $-1$

输入输出样例

输入

2 5 3

输出

6 -3

题解

解一个裴蜀方程 $ax+by=-c$，用扩展欧几里得算法的板子。

代码

#include<iostream>
#define ll long long
using namespace std;
ll ex_gcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	else
	{
		ll gcd=ex_gcd(b,a%b,x,y);
		//向上递推
		ll temp=x;
		x=y;
		y=temp-a/b*y;
		return gcd;
	}
}
void solve()
{
	ll a,b,c,x,y;
	cin>>a>>b>>c;
	c=-c;
	ll d=ex_gcd(a,b,x,y);
	//随便取了一组解
	x=x*c/d+b/d*3;
	y=y*c/d-a/d*3;
	if(c%d) cout<<-1;
	else cout<<x<<' '<<y;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}

求解线性同余方程

线性同余方程

给定整数 $a,b,n\in Z$，形如 $ax≡b\pmod n$ 的方程称为线性同余方程。我们需要求一个整数 $x$ 满足 $ax≡b\pmod n$，或者给出无解。

理论描述

$ax≡b\pmod n$ 等价于 $ax-b$ 是 $n$ 的倍数，不妨设为 $-y$ 倍，即 $ax-b=-yn$。于是可以将线性同余方程改写为裴蜀等式的形式 $ax+ny=b$ 。由裴蜀定理，当且仅当 $gcd(a,n)|b$ 时方程有整数解。

例题：洛谷P1082 同余方程

题目描述

求关于 $x$ 的同余方程 $ a x \equiv 1 \pmod {b}$ 的最小正整数解。

输入格式

一行，包含两个正整数 $a,b$，用一个空格隔开。

输出格式

一个正整数 $x_0$，即最小正整数解。输入数据保证一定有解。

输入输出样例

输入

3 10

输出

7

说明/提示

【数据范围】

对于 40%的数据，$2 ≤b≤ 1,000$；

对于 60%的数据，$2 ≤b≤ 50,000,000$；

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

NOIP 2012 提高组 第二天 第一题

题解

该题的线性同余方程若有解，则 $a,b$ 互质。

需要输出最小正整数解，求得的特解 $x_0$ 却往往不是最小整数解。

已知等式 $a(x_0+kb)+b(y_0-ka)=1$，等式两边同时对 $b$ 取余，得到 $ax_0\bmod b=1$ 。故取最小整数解为 $(x_0\bmod b +b)\bmod b$。

代码

#include<iostream>
#define ll long long
using namespace std;
ll ex_gcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	else 
	{
		ll gcd=ex_gcd(b,a%b,x,y);
		ll temp=x;
		x=y;
		y=temp-a/b*y;
		return gcd;
	}
}
void solve()
{
	ll a,b,c=1;
	cin>>a>>b;
	ll x,y;
	ex_gcd(a,b,x,y);
	x=(x%b+b)%b;
	cout<<x;
}
int main()
{
	solve();
	return 0;
}