HDU 2669 Romantic(扩展欧几里德, 数学题)

题目

//第一眼看题目觉得好熟悉，但是还是没想起来
//洪湖来写不出来去看了解题报告，发现是裸的 扩展欧几里得 - -

/*

//扩展欧几里得算法（求 ax+by=gcd ）
//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
#define LL long long
LL extend_gcd(LL a,LL b,LL &x,LL &y){
if(a==0&&b==0) return -1;//无最大公约数
if(b==0){x=1;y=0;return a;}
LL d=extend_gcd(b,a%b,y,x);
y-=a/b*x;
return d;
}

*/

/*
//扩展欧几里德 模版二
void ex_gcd(__int64 a, __int64 b, __int64 &d, __int64 &x, __int64 &y)
{
if(!b){ d = a; x = 1; y = 0;}
else
{
ex_gcd(b, a%b, d, y, x);
y -= x*(a/b);
}
} //ex_gcd

*/

//猜测：如果两者的最大公约数不是1，那么就无法达成目的，输出sorry。。。
//猜测正确^-^

//x>=0

//a * x + b * y = 1
//-> a*(x+b) + b*(y-a) = a*x + a*b + b*y - a*b = 1

#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
#define LL __int64
LL extend_gcd(LL a,LL b,LL &x,LL &y){
    if(a==0&&b==0)  return -1;//无最大公约数
    if(b==0){x=1;y=0;return a;}
    LL d=extend_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

int main()
{
    LL a, b, x, y, d;
    while(scanf("%I64d%I64d",&a,&b)!=EOF)
    {                    
        d = extend_gcd(a, b, x, y);
        if(d == 1 )
        {
            while(x<0)//output nonnegative integer X and integer Y
            {
                //a * x + b * y = 1   
                //->  a*(x+b) + b*(y-a) = a*x + a*b + b*y - a*b = 1
                x = x+b;
                y = y-a;
            }
            printf("%I64d %I64d
",x,y);
        }
        else 
        {
            printf("sorry
");
        }
            
    }

    return 0;

}