Romantic---hdu2669（扩展欧几里德模板）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2669

详解：扩展欧几里德

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>

using namespace std;

#define met(a, b) memset(a, b, sizeof(a))
#define INF 0x3f3f3f3f
#define N 10010
typedef long long LL;

LL ex_gcd(LL a, LL b, LL &x, LL &y)///返回值是a和b的最大公约数；
{
    if(b==0)
    {
        x = 1;
        y = 0;
        return a;
    }
    LL c = ex_gcd(b, a%b, x, y);

    LL temp = x;      ///回溯中的x相当于之前的x所以要保留；
    x = y;            ///对应x1 = y2；
    y = temp - a/b*y; ///对应y1 = x2 - a/b * y1；

    return c;
}

int main()
{
    LL a, b, x, y;

    while(~scanf("%I64d %I64d", &a, &b))
    {
        LL c = ex_gcd(a, b, x, y);

        if(c!=1)
            printf("sorry
");
        else
        {
            while(x<=0)
            {
                x+=b;
                y-=a;
            }
            printf("%I64d %I64d
", x, y);
        }
    }
    return 0;
}