寻找所有满足等式的数字对

Question

在C++中，寻找符合某个公式的所有正整数对的最优方法是什么？例如：

a^2 * b = 16;//a & b MUST be positive INT.

我该如何找到满足公式的所有a和b的组合？

编辑：为了更清晰，这只是一个例子。实际上，我有一个a^2 * b = c的公式，其中c在使用for循环递增，我需要找到每个满足此方程条件的正整数对(a，b)。

- josneville

---

解出a，并放入任意的b中。 - dari

这个问题应该在数学网站上提问。 - Skizz

这是(a^2)*b = 16（我的理解）还是a^(2*b) = 16？ - didierc

只有整数解吗？否则就有无限解！ - Fantastic Mr Fox

只有正整数解，我有一个更大的问题，但这是我可以在这里提出的最简单形式。从技术上讲，我有a^2 * b = c，其中c通过for循环递增，我需要找到每个c的所有可能的a和b。 - josneville

@Ben 我正要发布这个呢，嘿嘿！ - Albert Renshaw

Answer 1

问题是找到所有正整数对 (a,b)，使得方程式 a^2 * b = c 成立，其中 c 也是一个正整数。

从方程式中可以得出，c 是一个完全平方数的倍数。因此，我们首先要找到所有能够整除 c 的完全平方数。显然，当 a=1, b=c 时，方程式成立，因此我们知道每个值都至少有一个解。在找到每个 a 后，我们通过将 c 除以每个 a^2 来得到其对应的 b。

以下是以上实现的 C++ 代码：

std::vector<std::pair<int, int> > solve(int c) {
    std::vector<int> a;
    for (int i = 1; i * i <= c; ++i)
        if (c % (i*i) == 0) a.push_back(i);

    std::vector<std::pair<int, int> > solutions;
    solutions.reserve(a.size());
    for (std::vector<int>::iterator it = a.begin(); it != a.end(); ++it) {
        const int& a = *it;
        solutions.push_back(std::pair<int, int>(a, c / (a*a)));
    }

    return solutions;
}

这里有一个实时演示，展示了关于 c = 7! = 5040 的解决方案。 点击这里查看实例。

- tclamb

Answer 2

找到c的因数，然后找到使用三个值的子集，其中两个值相同。

- Skizz

Answer 3

通过检查，三个整数解为：

1. a = ±1，b = 16

2. a = ±2，b = 4

3. a = ±4，b = 1

否则，有无限解。Wolfram|Alpha 给出了详细信息。

- user448810

---

我并不是指特定的这个例子，这只是个例子。我的意思是在任何涉及到两个未知变量的情况下。 - josneville

现在你在评论中改变了问题。我没有测试过，但我认为它会起作用。对于任何给定的c，设置a = floor(sqrt(c))和b = 1。计算a ** 2 * b。如果它大于c，则将a减1并重试。如果它小于c，则增加b并重试。如果它等于c，则您有一个解决方案；报告它，然后将a减1并将b增加1，然后再次尝试。当a变为0时停止。 - user448810

Answer 4

如果您需要重复执行此操作，则我认为解决此问题的最有效方法如下： 1. 设置一个平方表，[0, 1, 4, 9, 16, ......]，表的长度取决于您要处理的最大数字，无论如何，您将需要O(sqrt(N))的空间来查找表。 2. 将数字分解成因数，例如，16有5个因数（1、2、4、8、16）。 3. 从查找表中检查，您可以发现1、4和16在查找表中。因此有6对，即(-1或1)^2 * 16，(-2或2)^2 * 4和(-4或4)^2 * 1。

- dguan