本文共 1394 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要找到满足方程 ax + by = 1 的整数解，其中 x 是非负的，并且尽可能小。只有当 a 和 b 互质时，这个方程才有解。我们可以通过扩展欧几里得算法来找到一组解，并对其进行调整以满足要求。

方法思路

解决代码

#include 
   
    #pragma warning(disable:4996)int a, b, x, y;int gcd(int a, int b) {    return b == 0 ? a : gcd(b, a % b);}int extgcd(int a, int b, int x, int y) {    int d = a;    if (b != 0) {        d = extgcd(b, a % b, x, y);        y -= (a / b) * x;    } else {        x = 1;        y = 0;    }    return d;}int main() {    while (scanf("%d %d", &a, &b) != EOF) {        if (extgcd(a, b, x, y) > 1) {            puts("sorry");            continue;        }        if (y < 0) {            y = -y;            a = -a;        }        if (x < 0) {            x = -x;            b = -b;        }        if (extgcd(a, b, x, y, 1) != 1) {            puts("sorry");            continue;        }        while (x >= 0) {            x -= b;            y += a;        }        while (x < 0) {            x += b;            y -= a;        }        printf("%d %d\n", x, y);    }    return 0;}
   

代码解释

通过这种方法，我们能够高效地找到满足条件的解，并确保输出的 x 是最小的非负整数。

转载地址：http://lotez.baihongyu.com/