欧几里得范数

问题

毕达哥拉斯三元组由三个自然数 a < b < c 组成，并满足 $a^2 + b^2 = c ^2$ ，例如 $3^2 + 4^2 = 5^2$

有且只有一个毕达哥拉斯三元组满足 a + b + c = 1000。求这个三元组的乘积 $a * b * c$

暴力枚举

为了使题目更具一般性，假设 a + b + c = n，由 a < b < c，可以得知 $a < \frac{n}{3}$ ， $max(a, \frac{n}{4}) < b < \frac{n}{2}$

fun main() {
    println("${pythagoreanTriplet(12)}")    // 3 * 4 * 5 = 60
    println("${pythagoreanTriplet(1000)}")  // 200 * 375 * 425 = 31875000
}

fun pythagoreanTriplet(n: Int): Triple<Int, Int, Int> {
    if (n.and(1) == 1) {
        // n 为奇数，不存在毕达哥拉斯三元组（尾数奇偶性可反证）
        return Triple(0, 0, 0)
    }
    val upper = n.div(3)
    (0 until upper).forEach { a ->
        val lower = a.coerceAtLeast(n.div(4)) + 1
        (lower until n.shr(1)).forEach { b ->
            if (a * a + b * b == (n - a - b) * (n - a - b)) {
                return Triple(a, b, n - a - b)
            }
        }
    }
    return Triple(0, 0, 0)
}

奇技淫巧

对于 0 < p < q，以下三个数可以构成毕达哥拉斯三元组： $q^2 - p^2,\, 2 * q * p,\, q^2 + p^2$

令这三个数为 a、b、c(倘若 $2 * q * p > q^2 - p^2$ ，调换 a、b 即可，不影响结论)，则有： $a + b + c = q^2 - p^2 + 2 * q * p + q^2 + p^2 = 2 * q * (q + p) = n$ ，即：

$q * (q + p) = \frac{n}{2}$

可以推出 $q = \sqrt{\frac{n}{2} - q * p} < \sqrt{\frac{n}{2}}$ ；
同时可推出， $p = \frac{\frac{n}{2}}{q} - q$ ，又因 p < q，故 $\frac{\frac{n}{2}}{q} - q < q$ ，即 $q > \frac{\sqrt n}{2}$ 。所以：

$\frac{\sqrt n}{2} < q < \sqrt{\frac{n}{2}}，\, 且\, q\, 是\, \frac{n}{2} \,的因子$

n = 1000 时满足区间 $[\frac{\sqrt n}{2}, \sqrt{\frac{n}{2}}]$ 即 $[\sqrt{250}, \sqrt{500}]$ 的整数只有 16、17、18、19、20、21、22，遍历区间，显然只有 20 是 $\frac{n}{2} = 500$ 的因子，所以 q = 20，p = 5，故有： $q^2 - p^2 = 20^2 - 5^2 = 375,\, 2 * q * p = 2 * 20 * 5 = 200,\, q^2 + p^2 = 20^2 + 5^2 = 425$

按大小顺序分别赋值 $a = 200,\, b = 375,\, c = 425$ ，可验证： $a^2 + b^2 = 200^2 + 375^2 = 425^2 = c^2$

抠腚如下：

fun main() {
    println("${pythagoreanTriplet(12)}")    // 3 * 4 * 5 = 60
    println("${pythagoreanTriplet(1000)}")  // 200 * 375 * 425 = 31875000
}

fun pythagoreanTriplet(n: Int): Triple<Int, Int, Int> {
    if (n.and(1) == 1) {
        // n 为奇数，不存在毕达哥拉斯三元组（尾数奇偶性可反证）
        return Triple(0, 0, 0)
    }
    val lower = floor(sqrt(n.toDouble()).div(2)).toInt()
    val upper = ceil(sqrt(n.toDouble().div(2))).toInt()
    (lower..upper).forEach { q ->
        if (n.shr(1).mod(q) == 0) {
            val p = n.shr(1).div(q) - q
            if (p < q) {
                return Triple(q * q - p * p, 2 * p * q, q * q + p * p)
            }
        }
    }
    return Triple(0, 0, 0)
}