扩展欧几里得板子

亦凉 2021-09-07 06:20 305阅读 0赞

a*x+b*y=c，求出其中一组解x y

int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法
    { 
        if(b==0)
        { 
            x=1;y=0;
            return a;  //到达递归边界开始向上一层返回
        }
        int r=exgcd(b,a%b,x,y);
        int temp=y;    //把x y变成上一层的
        y=x-(a/b)*y;
        x=temp;
        return r;     //得到a b的最大公因数
    }
    
    bool linear_equation(int a,int b,int c,int &x,int &y)
    { 
        int d=exgcd(a,b,x,y);
        if(c%d)
            return false;
        int k=c/d;
        x*=k; y*=k;    //求得的只是其中一组解
        return true;
    }

转载于[https://blog.csdn.net/destiny1507/article/details/81750874][https_blog.csdn.net_destiny1507_article_details_81750874]  
[https://blog.csdn.net/syz201558503103/article/details/76512144][https_blog.csdn.net_syz201558503103_article_details_76512144]

[https_blog.csdn.net_destiny1507_article_details_81750874]: https://blog.csdn.net/destiny1507/article/details/81750874
[https_blog.csdn.net_syz201558503103_article_details_76512144]: https://blog.csdn.net/syz201558503103/article/details/76512144

发表评论取消回复

表情：

评论列表（有 0 条评论，305人围观）

还没有评论，来说两句吧...

相关阅读

相关扩展欧几里得算法

poj 1061题目，青蛙的约会。一开始想暴力求解的。但是之前提交过，tle... 今天过来查一下，说是扩展欧几里得算法。我了个去。这么复杂的名字，得是有多深奥。查了才知

系统管理员/ 2022年09月29日 05:30/ 0 赞/ 199 阅读

相关欧几里得和扩展欧几里得算法

（一）欧几里得算法又称辗转相除法，是求解两个数的最大公约数的算法，基本定义为：设 a=qb+r，其中a，b，q，r都是整数，则：gcd（a，b）= gcd（b，r）利用

ゞ浴缸里的玫瑰/ 2022年08月21日 03:20/ 0 赞/ 250 阅读

相关扩展欧几里得定理

扩展欧几里德算法（注意：拓展（扩展）欧几里得算法是求解形如ax+by=1的方程组的（而且a和b是互质的，允许通过约分得到，并且求出的x如果是正数的话那一定是最小正整数，如果为负

缺乏、安全感/ 2022年06月17日 06:54/ 0 赞/ 279 阅读

相关扩展欧几里得算法

问题描述：求解二元一次方程ax+by=c。问题分析：上述的二元一次方程可以用同余方程来进行描述：ax≡cmod(b) 两个问题可以进行转换，但是都可以用扩展的欧几

心已赠人/ 2022年06月15日 10:00/ 0 赞/ 243 阅读

相关欧几里得推扩展欧几里得

欧几里得求整数a,b的最小公约数gcd(a,b)的算法。即欧几里得算法(俗称最小公倍数算法)。有一个重要的公式如下,这个公式的证明略,百度上有. (1) g

我会带着你远行/ 2022年06月13日 09:22/ 0 赞/ 252 阅读

相关欧几里得+扩展欧几里得（理解）

-------------------- 欧几里得： -------------------- 辗转相除法代码： typedef long long

妖狐艹你老母/ 2022年06月05日 05:39/ 0 赞/ 298 阅读

相关 ZOJ - 3609 (逆元、扩展欧几里得板子)

include<cstdio> using namespace std; typedef long long ll; ll exten

落日映苍穹つ/ 2022年05月26日 01:22/ 0 赞/ 153 阅读

相关扩展欧几里得

GCD 定义欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。结论与证明对于a,b两个正整数（a>b），gcd(a,b)=gcd(a

以你之姓@/ 2022年03月20日 07:53/ 0 赞/ 265 阅读

相关扩展欧几里得算法

下面直接使用简称exgcd就好。先引入紫书上的一个经典问题，求直线方程ax+by+c=0的所有整数解。我们先来看一个简单的，求ax+by=gcd(a,b)的一组整数解。

今天药忘吃喽~/ 2021年09月29日 21:02/ 0 赞/ 406 阅读

相关扩展欧几里得板子

ax+by=c，求出其中一组解x y int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法 {

亦凉/ 2021年09月07日 06:20/ 0 赞/ 306 阅读