欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu 2669 Romantic

程序员文章站 2024-01-12 09:55:46
...

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;
}