算法描述
扩展欧几里得算法可直接计算不定方程方程 a x + b y = g c d ( a , b ) , ( a , b ∈ Z ) ax+by=gcd(a,b),(a,b\in Z) a x + b y = g c d ( a , b ) , ( a , b ∈ Z ) 的一组整数解,并返回 gcd ( a , b ) \gcd(a,b) g cd( a , b ) 。
理论基础
裴蜀定理(Bézout’s lemma)
定理描述
对任何整数 a a a 、b {\displaystyle b} b 和 c {\displaystyle c} c ,关于未知数 x {\displaystyle x} x 和 y {\displaystyle y} y 的线性丢番图方程:a x + b y = c {\displaystyle ax+by=c} a x + b y = c 当且仅当 gcd ( a , b ) ∣ c \gcd(a,b)|c g cd( a , b ) ∣ c 时有整数解。
证明
先证:
对于任意整数 a , b a,b a , b ,存在一对整数 x , y x,y x , y ,满足 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) a x + b y = g c d ( a , b ) 。
在欧几里得算法(Euclidean algorithm)的最后一步,即 b=0 时,显然有一对整数 x = 1 , y = 0 x=1,y=0 x = 1 , y = 0 ,使得 a × 1 + 0 × 0 = g c d ( a , 0 ) a \times 1+0 \times 0=gcd(a,0) a × 1 + 0 × 0 = g c d ( a , 0 ) ;
若 b > 0 b>0 b > 0 ,则gcd ( a , b ) = gcd ( b , a m o d b ) \gcd(a,b)=\gcd(b,a\bmod b) g cd( a , b ) = g cd( b , a mod b ) 。假设存在一对整数 x , y x,y x , y ,满足 b × x + ( a m o d b ) × y = g c d ( b , a m o d b ) b \times x+(a \bmod b)\times y=gcd(b,a\bmod b) b × x + ( a mod b ) × y = g c d ( b , a mod b ) 。那么 b x + ( a m o d b ) ⋅ y = b x + ( a − b ⌊ a b ⌋ ) ⋅ y = a y + b ⋅ ( x − ⌊ a b ⌋ y ) bx+(a \bmod b)·y=bx+(a−b⌊\frac{a}{b}⌋)·y=ay+b· (x−⌊\frac{a}{b}⌋y) b x + ( a mod b ) ⋅ y = b x + ( a − b ⌊ b a ⌋) ⋅ y = a y + b ⋅ ( x − ⌊ b a ⌋ y ) 。令 x ′ = y , y ′ = x − ⌊ a b ⌋ y x′=y,y′=x−⌊\frac{a}{b}⌋y x ′ = y , y ′ = x − ⌊ b a ⌋ y ,得到 a x ′ + b y ′ = gcd ( a , b ) ax′+by′=\gcd(a,b) a x ′ + b y ′ = g cd( a , b ) 。
由数学归纳法,命题成立。
证毕。
又证:
对于更为一般的方程 $ax+by=c ,当且仅当 ,当且仅当 ,当且仅当 gcd(a,b)∣c$,该方程有整数解。
由于证明过程复杂,以下给出简单的感性认识。
我们可以先求出 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) a x + b y = g c d ( a , b ) 的一组特解 x 0 , y 0 x_0,y_0 x 0 , y 0 ,然后令$ x_0,y_0$ 同时乘上 c g c d ( a , b ) \frac{c}{gcd(a,b)} g c d ( a , b ) c ,就得到了$ ax+by=c$ 的一组特解$ \frac{c}{gcd(a,b)}x_0,\frac{c}{gcd(a,b)}y_0$。
算法模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int ex_gcd (int a,int b,int &x,int &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 \gcd(a,b)|c g cd( a , b ) ∣ c 时方程有解。
扩展欧几里得算法能求出 a x + b y = g c d ( a , b ) ax+by=gcd(a,b) a x + b y = g c d ( a , b ) 的一组特解。当递归至 b = 0 b=0 b = 0 时,此时该方程有一组解 x = 1 , y = 0 x=1,y=0 x = 1 , y = 0 ,此值按照规则 x ′ = y , y ′ = x − ⌊ a b ⌋ y x′=y,y′=x−⌊\frac{a}{b}⌋y x ′ = y , y ′ = x − ⌊ b a ⌋ y 向上层返回。
于是得到一组特解 x 0 , y 0 x_0,y_0 x 0 , y 0 使得 a x 0 + b y 0 = gcd ( a , b ) ax_0+by_0=\gcd(a,b) a x 0 + b y 0 = g cd( a , b ) ,等式两边同时乘上 c g c d ( a , b ) \frac{c}{gcd(a,b)} g c d ( a , b ) c ,就得到了 a x + b y = c ax+by=c a x + b y = c 的一组特解 c g c d ( a , b ) x 0 , c g c d ( a , b ) y 0 \frac{c}{gcd(a,b)}x_0,\frac{c}{gcd(a,b)}y_0 g c d ( a , b ) c x 0 , g c d ( a , b ) c y 0 。
下面给出裴蜀等式的通解:
x = c d x 0 + k b d , y = c d y 0 − k a d ( k ∈ Z , d = g c d ( a , b ) ) 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 = d c x 0 + k d b , y = d c y 0 − k d a ( k ∈ Z , d = g c d ( a , b ))
x x x 的最小正整数解为 ( x 0 c d m o d b d + b d ) m o d b d (x_0 \frac{c}{d}\bmod \frac{b}{d}+\frac{b}{d})\bmod \frac{b}{d} ( x 0 d c mod d b + d b ) mod d b 。
例题:洛谷CF7C Line
题目描述
A line on the plane is described by an equation A x + B y + C = 0 Ax+By+C=0 A x + B y + C = 0 . You are to find any point on this line, whose coordinates are integer numbers from − 5 ⋅ 1 0 18 -5·10^{18} − 5 ⋅ 1 0 18 to 5 ⋅ 1 0 18 5·10^{18} 5 ⋅ 1 0 18 inclusive, or to find out that such points do not exist.
输入格式
The first line contains three integers A A A ,$ B$ andC C 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 A^{2}+B^{2}>0 A 2 + B 2 > 0 .
If the required point exists, output its coordinates, otherwise output -1.
题意翻译
一条直线:A x + B y + C = 0 Ax+By+C=0 A x + B y + C = 0 (A , B A,B A , B 不同时为 0 0 0 ),找到任意一个点(在 − 5 × 1 0 18 -5\times 10^{18} − 5 × 1 0 18 ∼ \sim ∼ 5 × 1 0 18 5\times 10^{18} 5 × 1 0 18 之间)让它的横纵坐标均为整数,或者确定没有这样的点。
输入:A , B , C A,B,C A , B , C
输出:该点坐标,没有就输出 − 1 -1 − 1
输入输出样例
输入
2 5 3
输出
6 -3
题解
解一个裴蜀方程 a x + b y = − c ax+by=-c a x + b y = − c ,用扩展欧几里得算法的板子。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #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 ∈ Z a,b,n\in Z a , b , n ∈ Z ,形如 a x ≡ b ( m o d n ) ax≡b\pmod n a x ≡ b ( mod n ) 的方程称为线性同余方程。我们需要求一个整数 x x x 满足 a x ≡ b ( m o d n ) ax≡b\pmod n a x ≡ b ( mod n ) ,或者给出无解。
理论描述
a x ≡ b ( m o d n ) ax≡b\pmod n a x ≡ b ( mod n ) 等价于 a x − b ax-b a x − b 是 n n n 的倍数,不妨设为 − y -y − y 倍,即 a x − b = − y n ax-b=-yn a x − b = − y n 。于是可以将线性同余方程改写为裴蜀等式的形式 a x + n y = b ax+ny=b a x + n y = b 。由裴蜀定理,当且仅当 g c d ( a , n ) ∣ b gcd(a,n)|b g c d ( a , n ) ∣ b 时方程有整数解。
例题:洛谷P1082 同余方程
题目描述
求关于 x x x 的同余方程 $ a x \equiv 1 \pmod {b}$ 的最小正整数解。
输入格式
一行,包含两个正整数 a , b a,b a , b ,用一个空格隔开。
输出格式
一个正整数 x 0 x_0 x 0 ,即最小正整数解。输入数据保证一定有解。
输入输出样例
输入
3 10
输出
7
说明/提示
【数据范围】
对于 40%的数据,2 ≤ b ≤ 1 , 000 2 ≤b≤ 1,000 2 ≤ b ≤ 1 , 000 ;
对于 60%的数据,2 ≤ b ≤ 50 , 000 , 000 2 ≤b≤ 50,000,000 2 ≤ b ≤ 50 , 000 , 000 ;
对于 100%的数据,2 ≤ a , b ≤ 2 , 000 , 000 , 000 2 ≤a, b≤ 2,000,000,000 2 ≤ a , b ≤ 2 , 000 , 000 , 000 。
NOIP 2012 提高组 第二天 第一题
题解
该题的线性同余方程若有解,则 a , b a,b a , b 互质。
需要输出最小正整数解,求得的特解 x 0 x_0 x 0 却往往不是最小整数解。
已知等式 a ( x 0 + k b ) + b ( y 0 − k a ) = 1 a(x_0+kb)+b(y_0-ka)=1 a ( x 0 + kb ) + b ( y 0 − ka ) = 1 ,等式两边同时对 b b b 取余,得到 a x 0 m o d b = 1 ax_0\bmod b=1 a x 0 mod b = 1 。故取最小整数解为 ( x 0 m o d b + b ) m o d b (x_0\bmod b +b)\bmod b ( x 0 mod b + b ) mod b 。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #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 ; }