c++ - 找到等于方程式的所有数字对

Question

在 c++ 中发现符合公式的所有正整数对的最佳方法是什么。例如:

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

如何找到符合公式的 a 和 b 的所有组合？

编辑:为了更清楚起见，这只是一个例子。实际上，我有 a^2 * b = c，其中 c 使用 for 循环递增，我需要找到符合该方程式标准的每个正整数对 (a,b)。

Answer 1

问题是找到满足方程 a^2 * b = c 的所有正整数对 (a,b) 其中 c也是一个正整数。

根据等式，c 可以被一个完美的平方整除。所以首先，我们找到所有均匀划分 c 的完美正方形。平凡地，a=1, b=c 满足这一点，因此我们知道 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;
}

这是一个 live example ，显示 c = 7! 的解决方案! = 5040。