c++已知两模数及余数求最小原数

在C++中，给定两个整数a和b作为模数（numerator和denominator），以及它们之间的余数c，你可以通过扩展欧几里得算法（Extended Euclidean Algorithm）找到满足条件的最小正整数x和y。这个算法可以同时计算出最大公约数（GCD）和一组解，其中gcd(a, b) * x + c * y = gcd(a, b)。

以下是使用辗转相除法（也叫欧几里得算法）和更相减损术逐步求解的过程：

1. 首先，确定初始值：x0 = 0，y0 = 1，x1 = 1，y1 = 0。
2. 每一步，更新变量：
- 如果当前余数为0，则停止，因为a % b == 0，此时x = x1，y = x0。
- 否则，令x = x1 - (a // b) * x0，y = x0 + (a // b) * x1。
3. 最终的x就是最小原数，使得ax + cy ≡ 0 (mod b)。

如果你想直接实现这个过程，可以考虑使用循环或递归结构。如果你需要一个完整的函数来完成此任务，下面是一个简化的示例：

int extendedEuclid(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x_temp, y_temp;
    int gcd = extendedEuclid(b, a % b, x_temp, y_temp);
    x = y_temp;
    y = x_temp - (a / b) * y_temp;
    return gcd;
}

// 使用方法：
int a, b, c;
// ...获取a、b、c的值
int gcd, x, y;
extendedEuclid(a, b, x, y);
int smallest_number = x * b - c * y; // 最小原数