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

关键词：

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的一对特值找出来 

#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;

扩展欧几里得算法

https://zh.wikipedia.org/wiki/扩展欧几里得算法 用类似辗转相除法，求二元一次不定方程的整数解。然后把它们改写成“余数等于”的形式//式1//式2//式3然后把它们“倒回去”//应用式3//应用式2//应用式1得解。这个过程可以用矩阵... 查看详情

扩展欧几里得笔记(代码片段)

扩欧求逆元~~若有$a$和$x$满足$ax≡1(modp)$，则称$a$和$x$是在模$p$意义下的乘法逆元，此时在模$p$意义下乘以$x$相当于除以$x$。一个数有逆元的充要条件是$gcd(a,p)=1$，此时逆元唯一存在。给定$p$，要求$a$的逆元，相当于求解同余... 查看详情

简单数论总结2——同余方程与扩展欧几里得算法(代码片段)

...是快要开学赶紧来肝上两篇今日内容——同余方程和扩展欧几里得算法同余同余的定义：若存在两个整数a，b，使得(a-b)MODP为0，则称作a与b在MODP的情况下同余换种通俗的说法，就是，aMODP与bMODP相等 记作  (aequivb(modP))... 查看详情

扩展欧几里德伪代码

求解二元一次不定方程mx+ny=gcd(m,n)1intex_gcd(intm,intn,int&x,int&y)2{3if(n==0){4x=1;5y=0;6returnm;7}8inttmp,g;9g=ex_gcd(n,m%n,x,y);10tmp=x;11x=y;12y=tmp-m/n*y;13returng;14} 查看详情

不定方程与扩展欧几里得(代码片段)

时间不多了，先把代码放上来。1#include<iostream>2#include<cstring>3#include<cstdio>45usingnamespacestd;67typedeflonglongll;89llgcd(lla,llb)1011return(b==0)?a:(gcd(b,a%b));121314llexgcd(lla,llb,ll&x,ll&y)1516if(b==0)17x=1;y=0;18returna;1920llt=exgcd(b,a%b,y,x);2... 查看详情

数论学习之欧几里得的应用

扩展欧几里德算法的应用：1.求二元一次方程ax+by=c的整数解定理：对于整数方程ax+ by=c，若cmodGcd(a,b) ==0，则该方程存在整数解，否则不存在整数解。    设d=gcd(a,b),a‘=a/d,  b‘=b/d,则方程变形为d(a‘x+b... 查看详情

扩展欧几里得算法裴蜀定理与乘法逆元

扩展欧几里得算法扩展欧几里得算法（扩O）能在求gcd（a，b）的同时求出丢番图方程ax+by=gcd(a,b)的解。然而怎么求呢？我们观察gcd(a,b)=gcd(b,a%b)，所以设如下两个方程：ax+by=gcd(a,b)=d；bx’+(a%b)y’=gcd(b,a%b)；明显gcd(a,b)=gcd(b,a%b)，也... 查看详情

扩展欧几里得

...明：本文中的变量若非特别说明，均指整数。定义：扩展欧几里得算法是用于解决一类形如求解a*x+b*y=c中(x,y)，或者形如a*x≡b(modc)中x的问题。引理（裴蜀定理）：不定方程a*x+b*y=gcd(a,b)（x,y为变量）一定有无数个解。证明：先证... 查看详情

扩展欧几里得算法

题目给定两个整数(a,c,m)请求出模方程[axequivcmodm ag1]的最小正整数解。分析我们构造方程[axequiv1modm ag2]不难发现，如果我们能求出((2))中的一个解，将其乘上(c)即可得到((1))的一个解。那么现在就要求((2))的一个解。其等价于不定... 查看详情

扩展欧几里德算法的应用

...35扩展欧几里德算法的应用主要有以下三方面：（1）求解不定方程；（2）求解模的逆元；（3）求解模线性方程（线性同余方程）； 一、解不定方程   对于不定整数方程pa+qb=c，　1.若cmodgcd(p,q)=0,则该方程存在整数... 查看详情

同余方程（扩展欧几里得）

#include<cstdio>usingnamespacestd;intx,y;intgcd(inta,intb,int&x,int&y){if(!b){x=1,y=0;returna;}intret=gcd(b,a%b,x,y);intt=x;x=y;y=t-a/b*y;returnret;}inta,b;intmain(){scanf("%d%d",&a, 查看详情

扩展欧几里得算法详解(代码片段)

本篇将附上扩展欧几里得算法的思想与推导;对于一个方程(a*x+b*y=gcd(a,b))来说,我们可以做如下的推导:设有(a*x_1+b*y_1=gcd(a,b));同时我们有(b*x_2+(a\%b)*y_2=gcd(b,a\%b));对于这个方程组,我们希望知道的是(x_1,x_2,y_1,y_2)之间的关系,这样我们... 查看详情

扩展欧几里得noip2012同余方程

题目描述求关于x的同余方程ax≡1(modb)的最小正整数解。输入输出格式输入格式： 输入只有一行，包含两个正整数a,b，用一个空格隔开。 输出格式： 输出只有一行，包含一个正整数x0，即最小正整数解。输入数据保证... 查看详情

『扩欧简单运用』(代码片段)

扩展欧几里得算法顾名思义，扩欧就是扩展欧几里得算法，那么我们先来简单地回顾一下这个经典数论算法。对于形如(ax+by=c)的不定方程，扩展欧几里得算法可以在(O(5log_10mina,b))的时间内找到该方程的一组特解，或辅助(gcd)判断... 查看详情

wenbao与欧几里得及线性同余方程(代码片段)

 扩展欧几里得：设a和b不全为0，则存在整数x和y,使得 gcd(a,b)==x*a+y*b; 求解a*x+b*y=c;  令d=gcd(a,b);若c%d==0;则有解　　a*x ≡c(modb)　　特解可以根据扩欧求得 通解为X=x+k*(c/d);k~[0,d-1];  令T=b/d;最小解为( 查看详情

扩展欧几里得

对于方程ax+by=c（x,y为整数），当且仅当c%gcd（a,b）==0时，（x,y）有解（见证明3），且有gcd(a,b)组解。求出方程的一个解x，方程的最小正整数解x0=(x%(b/gcd(a,b))+b/gcd(a,b))%b/gcd(a,b)(见证明4)那么exgcd（inta,intb,int&x,int&y）为求解该... 查看详情

poj2115clooooops[一元线性同余方程]

...$。要想方程有解，必须满足$(a,m)midd$。 这时利用扩展欧几里得求出$ax+m 查看详情

扩展gcd求解二元不定方程及其证明

#include<cstdio>#include<iostream>usingnamespacestd;/*扩展gcd证明 由于当d=gcd(a,b)时； d=d1=gcd(b,a%b); d1=b1x1+a%by1; d=ax+by=b1x1+a%by1。又由于a%b=a-a%b*b; 上式变形能够有 b1x1+(a-b*a/b)*y1=a*y1+b*(x1-a/b*y1 查看详情