Romantic HDU - 2669（扩欧）

扩展欧几里得模板

扩展欧几里德算法——找出一对整数(x,y)，使得ax+by = gcd(a,b)。注意，这里的x和y不一定是正数，也可能是负数或者0。例如， gcd(6,15)=3， 6*3-15*1=3，其中x=3， y=-1。这个方程还有其他解，如x=-2， y=1。

void gcd(int a, int b, int& d, int &x, int &y)

{

    if(!b)

    {

        d = a;

        x = 1;

        y = 0;

    }

    else

    {

        gcd(b, a % b, d, y, x);

        y -= x * (a / b);

    }

}

用数学归纳法并不难证明该算法的正确性，此处略去。注意在递归调用时， x和y的顺序变

了，而边界也是不难得出的： gcd(a,0)=1⋅a-0*0=a。这样，唯一需要记忆的是y-=x*(a/b)，哪

怕暂时不懂得其中的原因也不要紧。

上面求出了ax+by=gcd(a,b)的一组解(x1,y1)，那么其他解呢？任取另外一组解(x2,y2)，

则ax1+by1=ax2+by2（它们都等于gcd(a,b)），变形得a(x1-x2)=b(y2-y1)。假设gcd(a,b)=g，方程

左右两边同时除以g，得a'(x1-x2)=b' (y2-y1)，其中a'=a/g， b'=b/g。注意，此时a'和b'互素，

因此x1-x2一定是b'的整数倍。设它为kb'，计算得y2-y1=ka'。注意，上面的推导过程并没有用

到“ax+by的右边是什么”，因此得出如下结论。

即：设a, b, c为任意整数。若方程ax+by=c的一组整数解为(x0,y0)，则它的任

意整数解都可以写成(x0+kb', y0-ka')，其中a'=a/gcd(a,b)， b'=b/gcd(a,b)， k取任意整数。

以上内容均参考自刘汝佳的《算法竞赛入门经典》

题目代码及讲解

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

void gcd(LL a, LL b, LL &d, LL &x, LL &y)

{

    if(!b)

    {

        d = a;

        x = 1;

        y = 0;

    }

    else

    {

        gcd(b, a % b, d, y, x);

        y -= x * (a / b);

    }

}

int main()

{

    std::ios::sync_with_stdio(false);

    //freopen("input.txt", "r", stdin);

    //freopen("output.txt", "w", stdout);

    LL a, b;

    LL x, y;

    while(cin >> a >> b)

    {

        LL x, y, d;

        gcd(a, b, d, x, y);     //在这里产生一组解

        if(d != 1)      //要满足题目所给的等式，就必须要求a, b的最大公约数为1

            cout << "sorry" << endl;

        else

        {

            while(x < 0)

            {

                x += b / 1;     //它的任意整数解都可以写成(x0+kb', y0-ka')，直到x不为负数为止

            	y -= a / 1;

            }

            cout << x << " " << y << endl;

        }

    }

}

巴特西

Romantic HDU - 2669（扩欧）

扩展欧几里得模板

题目代码及讲解

最新文章

热门文章