C++ 毕达哥拉斯四元组检测算法

给定四个点，检查它们是否构成勾股定理四元组。勾股定理四元组定义为由整数 a、b、c、d 组成的元组，满足 a²+b²+c²=d²。它们基本上是丢番图方程的解。在几何解释中，它表示一个边长为整数 |a|、|b|、|c| 且空间对角线为 |d| 的长方体。

这里所示的长方体边是勾股四元组的例子。当它们的最大公约数为 1 时，勾股四元组就是本原勾股四元组。每个勾股四元组都是一个本原勾股四元组的整数倍。我们可以通过公式生成一组 a 为奇数的本原勾股四元组：

a = m² + n² - p² - q² b = 2(mq + np) c = 2(nq - mp) d = m² + n² + p² + q²

其中 m、n、p、q 为最大公约数为 1 的非负整数，且 m + n + p + q 为奇数。因此，所有本原毕达哥拉斯四元组都可用勒贝格恒等式刻画。

(m² + n² + p² + q²)² = (2mq + 2nq)² + 2(nq - mp)² + (m² + n² - p² - q²)²

示例代码：

// C++ code to detect Pythagorean Quadruples.
#include <bits/stdc++.h>
using namespace std;

// function for checking
bool pythagorean_quadruple(int a, int b, int c, int d)
{
    int sum = a * a + b * b + c * c;
    if (d * d == sum)
        return true;
    else
        return false;
}

// Driver Code
int main()
{
    int a = 1, b = 2, c = 2, d = 3;
    if (pythagorean_quadruple(a, b, c, d))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

输出： Yes

时间复杂度：O(1) 辅助空间：O(1)

参考 Wiki mathworld