2

我正在尝试完成一项家庭作业，其中涉及找出任何三个非负数 a、b 和 c，如果 c 可以通过将 a 和 b 相加来达到。例子：

如果 a = 3, b = 5, c = 19 我们将执行以下第一步：(3,5) 第二步：(3,8) 第三步：(11,8) 第四步：(19,8) 因此已达到 c。

这涉及找到方程 c = x a + y b 的所有正解，并检查 GCD(x,y) = 1。如果是，则答案是肯定的，否则，答案是否定的。

 long long int cc = c; //saving the starting value of c
    c=c-a; //a has to be in c at least once
       while(c>0){  // we reduce c by a in each step until b divides c, which would mean we found 
           if(c%b==0){ //solutions to c=xa+yb or until c becomes <=0
               y = (c/b);   //evaluating y
               x = ((cc - c)/a); //evaluating x
               if(gcd(x,y)==1) //if it's correct, then it's possible, otherwise try other solutions
               return true;
           }
           c=c-a; //reduce c by a
       }

这是我需要帮助优化的代码部分。为了找到解决方案，我将 c 迭代地减少了我设置为 max(a,b) 的 a，一旦我从 c 中取出所有 'a，我得到一个可被 b 整除的数字，因此找到了解决方案。我将该数字除以 b，结果是解的 y 部分，然后我将从 c 中取出的内容除以 a，得到解的 x 部分。

有什么办法可以更快地找到正解 x 和 y 吗？我听说过扩展欧几里得算法，但我不知道如何实现它。

4

0 回答 0