本文主要是介绍hdu - 2669 - Romantic（扩展欧几里得），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出a, b(0<a, b<=2^31)，求X * a + Y * b = 1 的一组解x1, x2，满足x1 >= 0。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2669
——>>在找乘法逆元的题目，看到这题简单顺手A了。。
#include <cstdio>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 -= a / b * x;}
}int main()
{int a, b;LL d = 0, x = 0, y = 0;while (scanf("%d%d", &a, &b) == 2){Gcd(a, b, d, x, y);if (d != 1){puts("sorry");}else{if (x >= 0){printf("%I64d %I64d\n", x, y);}else{LL t = - x / b;if (x % b){++t;}printf("%I64d %I64d\n", x + b * t, y - a * t);}}}return 0;
}
这篇关于hdu - 2669 - Romantic（扩展欧几里得）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
