首页 > 其他 > 详细

exgcd扩展欧几里得求解的个数

时间:2018-08-11 01:02:44      阅读:38      评论:0      收藏:0      [点我收藏+]

标签:接下来   可能   正整数   计数   article   urn   pan   target   col   

知识储备

扩展欧几里得定理

欧几里得定理

(未掌握的话请移步[扩展欧几里得])

正题

设存在ax+by=gcd(a,b),求x,y。
我们已经知道了用扩欧求解的方法是递归,终止条件是x==1,y==0;

int exgcd( int a, int b, int &x, int &y ) {
    if( b == 0 ) {
        x = 1;
        y = 0;
        return a;
    }
    int tmp = a % b;
    if( tmp > b ) swap( tmp, b );
    int ans=exgcd(b,a%b,x,y);
    tmp = x;
    x = y;
    y = tmp - a / b * y;
    return ans;
}

 


到b==0时,我们可以得到一组解:(1,0)。
接下来再逐步回带,求出所有可能的解。具体是为什么呢?

证明


已知:

ax1+by1=gcd(a,b)
bx2+(a mod b)y2=gcd(a,b)
a mod b = a-a/b*b

可求得:
ax1+by1=bx2+(a mod b)y2=gcd(a,b)

ax1+by1=bx2+(a-a/b*b)y2=gcd(a,b)
化简得
ax1+by1=bx2+ay2-a/b*b*y2=gcd(a,b)
所以可证出:
对于每一次递归中的x1y1,与上一次递归中的x2y2存在如下关系:
x1 = y2,y1 = x2 - a / b * y2

证明毕,
每次的x和y均存在递归关系,所以我们可以在求得一组解后回溯时回带求出其他解,此时计数

P.S.

对于求方程正整数解的个数的题,需要注意特判
设ax+by=c,给定a,b,c,求x,y的正整数解个数

x=0,y=0,z=0时,方程无数解
x=0,y=0,z!=0时,方程无解
x,y<0,z>0时方程无解,反之亦然

exgcd扩展欧几里得求解的个数

标签:接下来   可能   正整数   计数   article   urn   pan   target   col   

原文:https://www.cnblogs.com/floatiy/p/9457844.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号