算法学习系列(二十九):裴蜀定理、扩展欧几里得算法

算法学习系列(二十九):裴蜀定理、扩展欧几里得算法这个扩展欧几里得算法用的还是比较多的 而且也很实用 话不多说直接开始吧

大家好,欢迎来到IT知识分享网。

引言

这个扩展欧几里得算法用的还是比较多的,而且也很实用,话不多说直接开始吧。

一、裴蜀定理

裴蜀定理:对于任意正整数 a 和 b ,一定存在非零整数 x 和 y ,使得 a x + b y = g c d ( a , b ) 裴蜀定理:对于任意正整数a和b,一定存在非零整数x和y,使得ax+by=gcd(a,b) 裴蜀定理:对于任意正整数ab,一定存在非零整数xy,使得ax+by=gcd(a,b)
也就是说a和b能凑出来的最小正整数就是它们的最大公约数

二、扩展欧几里得算法模板

给出 a 和 b , 求满足 a x + b y = g c d ( a , b ) 中任一 x 和 y 的值 给出a和b,求满足ax+by=gcd(a,b)中任一x和y的值 给出ab,求满足ax+by=gcd(a,b)中任一xy的值

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

三、公式推导

a x + b y = g c d ( a , b ) ax+by=gcd(a,b) ax+by=gcd(a,b)
当 b 为 0 , g c d ( a , b ) = a , a x + y ∗ 0 = a , 则一组解为 x = 1 , y = 0 当b为0,gcd(a,b)=a,ax+y*0=a,则一组解为x=1,y=0 b0gcd(a,b)=aax+y0=a,则一组解为x=1,y=0
g c d ( a , b ) = g c d ( b , a m o d      b ) , a m o d    b = a − ( a b )   ∗   b , 注:此处的 a b 都为下取整, gcd(a,b) = gcd(b,a \mod\ b),a\mod b=a-(\frac{a}{b})\ *\ b,注:此处的\frac{a}{b}都为下取整, gcd(a,b)=gcd(b,amod b),amodb=a(ba)  b,注:此处的ba都为下取整,
则 b y + ( a m o d    b ) x = d , b y + ( a − ( a b ) ∗ b ) x = d , 则by+(a\mod b)x=d,by+(a-(\frac{a}{b})*b)x=d, by+(amodb)x=d,by+(a(ba)b)x=d,
则 a x + b ( y − ( a b ) ∗ x ) = d 则ax+b(y-(\frac{a}{b})*x)=d ax+b(y(ba)x)=d



四、例题

1.扩展欧几里得算法模板题

题目描述:

给定 n 对正整数 ai,bi,对于每对数,求出一组 xi,yi,使其满足 ai×xi+bi×yi=gcd(ai,bi)。 输入格式 第一行包含整数 n。 接下来 n 行,每行包含两个整数 ai,bi。 输出格式 输出共 n 行,对于每组 ai,bi,求出一组满足条件的 xi,yi,每组结果占一行。 本题答案不唯一,输出任意满足条件的 xi,yi 均可。 数据范围 1≤n≤105,1≤ai,bi≤2×109 输入样例: 2 4 6 8 18 输出样例: -1 1 -2 1 

示例代码:

#include <cstdio> #include <iostream> using namespace std; int exgcd(int a, int b, int& x, int& y) { 
    if(!b) { 
    x = 1, y = 0; return a; } int d = exgcd(b, a%b, y, x); y -= a / b * x; return d; } int main() { 
    int n; scanf("%d", &n); while(n--) { 
    int a, b, x, y; scanf("%d%d",&a, &b); exgcd(a, b, x, y); printf("%d %d\n", x, y); } return 0; } 

2.线性同余方程

题目描述:

给定 n 组数据 ai,bi,mi,对于每组数求出一个 xi,使其满足 ai×xi≡bi(modmi),如果无解则输出 impossible。 输入格式 第一行包含整数 n。 接下来 n 行,每行包含一组数据 ai,bi,mi。 输出格式 输出共 n 行,每组数据输出一个整数表示一个满足条件的 xi,如果无解则输出 impossible。 每组数据结果占一行,结果可能不唯一,输出任意一个满足条件的结果均可。 输出答案必须在 int 范围之内。 数据范围 1≤n≤105,1≤ai,bi,mi≤2×109 ,输入样例: 2 2 3 6 4 3 5 输出样例: impossible -3 

求 a x ≡ b ( m o d m ) ,即 a x = m y + b , 即 a x − m y = b , 求ax \equiv b \pmod m,即ax=my+b,即ax-my=b, axb(modm),即ax=my+b,axmy=b
令 y ′ = − y , 则 a x + m y ′ = b , 令y\prime =-y,则ax+my\prime=b, y=y,ax+my=b,
又存在 a x + m y ′ = g c d ( a , m ) , 又存在ax+my\prime = gcd(a,m), 又存在ax+my=gcd(a,m),
所以只要判断 b 是否为 g c d ( a , m ) 的倍数即可判断是否存在,并且 r e s = b g c d ( a , m ) ∗ x 所以只要判断b是否为gcd(a,m)的倍数即可判断是否存在,并且res=\frac{b}{gcd(a,m)}*x 所以只要判断b是否为gcd(a,m)的倍数即可判断是否存在,并且res=gcd(a,m)bx


示例代码:

#include <cstdio> #include <iostream> using namespace std; typedef long long LL; int exgcd(int a, int b, int& x, int& y) { 
    if(!b) { 
    x = 1, y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } int main() { 
    int n; scanf("%d", &n); while(n--) { 
    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("%lld\n", (LL)x * (b / d) % m); else puts("impossible"); } return 0; } 

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/128772.html

(0)
上一篇 2025-08-29 14:26
下一篇 2025-08-29 14:33

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信