我试图在 C++/C 中创建一个高效的算法来找到一个(任何)解和丢番图方程的解的数量 Ax+By+Cz=D 其中 A、B、C、D 是用户给定的整数，x,y,z 在用户给定的范围内运行。 x,y,z 也是整数。
我不想通过执行 3 个嵌套循环来使用蛮力方法，因为它是 O(n^3)。
所以算法中的第一件事就是找出是否有解:
Ax+By=gcd(A,B)
gcd(A,B)w+Cz=gcd(gcd(A,B),C)
最后，如果 gcd(gcd(A,B),C) 划分 D 则有解决方案。
我可以做到这一点，但现在我回到原点...我花了好几个小时试图找到关于如何做到这一点的引用资料，但我发现的只是蛮力或 2 个变量的算法，或者用我不懂的语言...
最佳答案
使用Extended Euclidean algorithm .话不多说，链接说明一切。而且你已经打破了问题并使其成为简单的 Ax+By=gcd(A,B) 问题。
关于c++ - 找到具有 3 个变量的丢番图方程的一个特定解和解的数量的有效算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27065392/