拓展欧几里德算法

拓展欧几里德算法

对贝祖等式：ax+by=gcd(a,b);  一定存在整数解，求x最小的整数解x,y (x,y可以是负数)

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn=1000100;
const int INF=(1<<28);

/**
求解贝祖等式ax+by=gcd(a,b)的最小整数解(x最小)
*/
int a,b;
int 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 t=y;
    y=x-a/b*y;
    x=t;
    return r;
}

int main()
{
    while(cin>>a>>b){
        exgcd(a,b,x,y);
        cout<<"x="<<x<<endl;
        cout<<"y="<<y<<endl;
    }
    return 0;
}

拓展欧几里德的应用如下

1，解不定等式：px+qy=r

思路：显然，当且仅当gcd(p,q)%r==0时有整数解。令d=gcd(p,q)，两边同时乘以r/d，再进行exgcd解，最后将解乘以d/r即可

代码略。。

2，解模线性同余方程：ax=b(mod n)

思路：容易知道，即解ax+ny=b中的x，显然，当且仅当gcd(a,n)%b==0时有解。方法同上，但需将解mod n，代码如下：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn=1000100;
const int INF=(1<<28);

/**
求解模线性同余方程：ax=b(mod n)的最小整数解
*/
int a,b,n;
int 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 t=y;
    y=x-(a/b)*y;
    x=t;
    return r;
}

bool mod_linear_equation(int a,int b,int n)
{
    int d=exgcd(a,n,x,y);
    if(b%d) return false;
    x=x*(b/d)%n;///最小解
    x=(x%(n/d)+(n/d))%(n/d); ///最小正整数解
    for(int i=1;i<d;i++) cout<<(x+i*(n/d))%n<<endl;///打印所有解
    return true;
}

int main()
{
    while(cin>>a>>b>>n){
        if(mod_linear_equation(a,b,n))
            cout<<"x="<<x<<endl;
        else cout<<"no solve"<<endl;
    }
    return 0;
}

3，求解模的逆元，现在没学，以后补上

更多介绍：http://www.acmerblog.com/extend-gcd-5610.html