找到等于等式的所有数字对

Question

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

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

我怎样才能找到符合公式的a和b的所有组合？

编辑:为了更加清晰,这只是一个例子.真的,我有一个^ 2*b = c,其中c使用for循环递增,我需要找到符合此等式标准的每个正整数对(a,b).

Answer 1

问题是找到(a,b)满足等式的所有正整数对,a^2 * b = c其中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;
}

这是一个实例,展示了解决方案c = 7! = 5040.