hdu 2669 Romantic

http://acm.hdu.edu.cn/showproblem.php?pid=2669
这就是简单的扩展欧几里得算法，求x 的最小正整数解

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
void exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return ;
    }
    exgcd(b, a%b, x, y);
    LL tmp = x;
    x = y;
    y = tmp - ( a / b) * y;
}
LL gcd(LL m, LL n)
{
    if(n == 0)
        return m;
    return gcd(n, m % n);
}
int main()
{
    LL a,b,x,y;
    while(cin >> a >> b)
    {
        if(gcd(a, b) != 1)
        {
           puts("sorry");
           continue;
        }
        exgcd(a, b, x, y);
        x = (b + x % b) % b;
        y = (1 - a * x) / b;
        cout<< x << " " << y << endl;
    }
    return 0;
}

        

          
        
        
        

          

          AI 代码解读