两个数字相加得到一个值的java算法

Question

我有一个家庭作业，要求我检查任意三个数字，a、b、c，以便0<=a、 b、c<=10^16，如果我能通过把a和b加在一起达到c。诀窍是，每次加法，它们的值都会改变，所以如果我们把a加到b，我们就会得到a和a+b，而不是a和b。因此，我意识到这不是一个简单的线性方程

为了实现这一点，目标编号c必须能够以以下形式表示：

c=xa+yb

通过一些测试，我发现x和y的值不可能相等，也不可能都相等，以便我能够达到数字c。记住这一点，以及一些涉及a、b或c等于零的特殊情况

有什么想法吗

编辑： 这不是欧几里德的算法，也不是丢番图方程，也许我用c=xa+yc的说法误导了你。即使他们应该满足这个说法，这对于手头的任务来说是不够的

以a=2，b=3，c=10为例。为了达到c，你需要在第一步将a加到b或b加到a，然后在第二步你会得到：a=2，b=5或a=5，b=3，如果你继续这样做，你永远不会达到c。欧几里德的算法将提供输出是的，但很明显，通过将2和3相加，你不能达到10

Answer 1

import java.util.*;
import java.math.BigInteger;

public class Main
{
    private static boolean result(long a, long b, long c)
    {
        long M=c%(a+b);
        return (M%b == 0) || (M%a == 0);
    }
}

想法：c=xa+by，因为x或y更大，我们可以用两种形式之一写出后一个方程： c=x（a+b）+（y-x）b， c=y（a+b）+（x-y）a 取决于谁更大，所以通过每次将c减少a+b，c最终变成： c=（y-x）b或c=（x-y）b，因此c%b或c%a的计算结果将为0

Answer 2

如果我们暂时忘记了x和y应该是正的，那么方程c=xa+yb要么没有解，要么有无穷多解。当c不是gcd（a，b）的倍数时，就没有解

否则，调用gcd（a，b）=t使用扩展的欧几里德算法来查找d和e，使得t=da+eb。然后给出一个解，即c=dc/ta+ec/tb

很明显，0=b/ta-a/tb，因此可以通过将其乘以f来找到更多的解：

c = (dc + fb)/t a + (ec - af)/t b

当我们现在重新引入x和y必须为正或为零的限制时，问题变成寻找使x=（dc+fb）/t和y=（ec-af）/t都为正或为零的f值

如果dc<；0尝试使dc+fb>；=0并查看ec-af是否也为>=0

否则，请尝试使ec-af>；=0并检查dc+fb是否>；=0

Answer 3

注意：重述我所理解的问题：假设给定了非负整数a、b和c。通过执行一系列零或多个操作a = a + b或b = b + a，是否可能达到a + b == c点

好的，在进一步研究之后，我认为你可以对你在问题中的陈述做一个小的改变：

In order for this to be possible, the target number c, must be able to be represented in the form:

c = xa + yb

where GCD(x,y) = 1.

（另外，x和y需要为非负；我不确定它们是否为0。）

你最初的观察结果，x可能不等于y（除非它们都是1），并且x和y不能都是偶数，这被新的条件GCD（x，y）暗示为1；因此，这些观察结果是正确的，但不够有力

如果您在程序中使用此选项而不是已经进行的测试，则可能会使测试通过。（我不保证任何事情。）对于更快的算法，您可以使用注释（和亨利的答案）中建议的扩展欧几里德算法来查找一个x₀和y₀；但是如果GCD（x₀，y₀）≠ 1、你必须尝试其他的可能性x=x₀+nb，y=y₀-na，对于某些n（可能是负数）

我没有严格的证据。假设我们构造所有对（x，y）的集S，使得（1,1）在S，如果（x，y）在S，那么（x，x+y）和（xy）。很明显，（1，n）和（n，1）对于所有n，都在s；1.然后我们可以试着找出，对于一些m和n>；1、这一对（m，n）如何进入S？如果m<n，只有当（m，n-m）已经在S中时，这才可能。如果m>n，只有当（m-n，n）已经在s中时才有可能。无论哪种方法，当你不断地从较大的数字中减去较小的数字时，你得到的基本上是欧几里德算法，这意味着你将到达一个点，你的配对是（g，g），其中g=GCD（m，n）；只有当g=1时，该对才在S中。在我看来，上述方程中目标数c的x和y的可能值正是S中的值。然而，这部分是基于直觉；需要做更多的工作，使其更加严格