基础数论-扩展欧几里得算法-蒲公英云

基础数论-扩展欧几里得算法

Dear 丶 2022-05-24 11:16 305阅读 0赞

首先我们先了解欧几里得算法

求俩个数a,b的最大公约数gcd(a,b)

根据贝祖定理得，gcd(a,b)=gcd(b,a-b),(a>b) 直到b为0时，a就是答案，但是这样时间复杂度有点高，因为a-b并不能保证一定大于b，所以我们又会做一次同样操作，即gcd(a,b)=gcd(b,a mod b)。

时间复杂度log N

代码如下：

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

扩展欧几里得算法：

对于这样的方程ax+by=gcd(a,b) 求出满足方程的x,y

通过刚刚的欧几里得算法，

当b==0时，ax+0*y=gcd(a,0) x=1 y=0

当b>0时，那么根据欧几里得算法 gcd(a,b)=gcd(b,a mod b)

b*x`+(a mod b) y` =gcd(b,a mod b) =gcd(a,b)

ax + by =gcd(a,b)

我们把第一个式子按照第二个式子化简

b*x`+(a-a/b*b)*y` =gcd(a,b)

ay`+b(x`-a/b*y`) =gcd (a,b)

即x=y` 和 y=(x`-a/b*y`)

我们一直递归到b=0，然后把x=1 y=0代入。

时间复杂度log N

代码如下：

int extend_gcd(int a,int b,int &x,int &y)
    if (b==0) {
        x=1;y=0;
        return a;//返回的结果是最大公约数
    } else {
        int d=exgcd(b,a%b,y,x);//x 和y 的位置换了注意
        y-=(a/b)*x;
        return d;
    }
}

单变元模线形方程

对于这样的方程 ax=b mod n 我们可以转化为 ax +ny =b 我们令d=gcd(a,n)

当b整除d时有解，d个，否则无解。

假设我们已经求出 ax + ny = gcd(a,n) =d

那么 ax +ny = b 的解为X=x* b/d;

令X1 Y1 X2 Y2为方程ax + ny =b 的俩组解

aX1 + bY1 =b

aX2 + bY2 =b

即a(X1-X2)=b(Y2-Y1) 我们俩边同时除以d

a/d *(X1-X2)=n/d * (Y2-Y1) 因为d为gcd(a,n)那么gcd(a/d ,n/d)=1 即互质

那么X1-X2=k *(n/d) 和 Y2-Y1=k` (a/d) 俩个k不一样咯注意。

即X1=X2+k*(n/d) Y1=Y2-k`*(a/d)

通解已经推出了不难发现，当k为d时，在模n下 X1=X2+n 与前面重复，所以k的取值为[0,d-1]

最小正整数解 X0=(X1 %(n/d) +(n/d) )% (n/d)

vector<int> line_mod_equation(a,b,n)
{
    int x,y;
    int d=extend_gcd(a,b,x,y);
    vector<int > ans;
    ans.clear();
    if (b%d==0) {
        x=(x%n+n)%n;
        ans.push_back(x*(b/d)%(n/d));
        for (int i=d;i<d;i++) {
            ans.push_back((ans[0]+i*(n/d))%n);
        }
    }
    return ans;
}