633. 平方数之和

#python #leetcode #math

题目描述

关联：https://leetcode.cn/problems/sum-of-square-numbers/description/

题目描述

给定一个非负整数 \(c\) ，判断是否存在两个整数 \(a\) 和 \(b\)，使得 \(a^2 + b^2 = c\)。

其中 \(0 \leq c \leq 2^{31} - 1\)

解题思路

好多题解都是用双指针做的，我们这里采用一个和主流不同的做法，即数论方法.

先验判断

首先可以对 \(c\) 进行先验判断，如果 \(c \equiv 3 \pmod{4}\)，那么 \(c\) 一定不能表示为两个整数的平方和.

证明

对于任意整数 \(k \in \mathbb{Z}\)：

\[ \begin{aligned} (2k)^2 &= 4k^2 \\ (2k + 1)^2 &= 4k^2 + 4k + 1 = 4(k^2 + k) + 1 \end{aligned} \]

即：

• 对于任意偶数 \(a\) 其平方 \(a^2 \equiv 0 \pmod{4}\).
• 对于任意奇数 \(a\) 其平方 \(a^2 \equiv 1 \pmod{4}\).

将其相加，不难看出：

• 对于任意偶数 \(a\) \(b\)，其平方和 \(a^2 + b^2 \equiv 0 \pmod{4}\).
• 对于任意偶数 \(a\) 奇数 \(b\)，其平方和 \(a^2 + b^2 \equiv 1 \pmod{4}\).
• 对于任意奇数 \(a\) \(b\)，其平方和 \(a^2 + b^2 \equiv 2 \pmod{4}\).

因此，如果 \(c \equiv 3 \pmod{4}\)，那么 \(c\) 一定不能表示为两个整数的平方和.

由于力扣喜欢出随机数据，因此这个判断能快速过滤 25% 的数据.

相关定理介绍

在本方法中，我们需要用到 丢番图恒等式（也被称为 婆罗摩笈多-斐波那契恒等式） 和 费马平方和定理.

丢番图恒等式

证明：若 \(a\) 和 \(b\) 可以表示为两个整数的平方和，那么 \(a \cdot b\) 也可以表示为两个整数的平方和.

设 \(a = w^2 + x^2\)，\(b = y^2 + z^2\)，那么：

\[ \begin{aligned} a &= w^2 + x^2 = (w + ix)(w - ix) \\ b &= y^2 + z^2 = (y + iz)(y - iz) \end{aligned} \]

\[ \begin{aligned} a \cdot b &= (w + ix)(w - ix)(y + iz)(y - iz) \\ &= [(w + ix)(y + iz)][(w − ix)(y − iz)] \\ &= [(wy − xz) + i(wz + xy)][(wy − xz) − i(wz + xy)] \\ &= (wy - xz)^2 + (wz + xy)^2 \\ \end{aligned} \]

即 \(a \cdot b\) 也可以表示为二平方和.

费马平方和定理

奇素数 \(p\) 能表示为两个平方数之和的充分必要条件是 \(p \equiv 1 \pmod{4}\).

根据丢番图恒等式，当我们发现 \(c\) 的一个素因子可以被表示为两个整数的平方和时，我们可以将其约去，继续分析剩下的部分，即：

丢番图恒等式的推论

若存在 \(c\) 的一个素因子 \(p_i\) 可以表示为两个整数的平方和，那么 \(c\) 和 \(c^* = \dfrac{c}{p_i}\) 在是否可以表示为两个整数的平方和上具有相同的性质.

本结论的具体证明详见 欧拉的证明.

逐个分析素因子

我们的思路便是利用丢番图恒等式，不断约去 \(c\) 的能被表示为两个整数的平方和的素因子.

若 \(c\) 的素因子中包含若干个 \(2\)，由于 \(2 = 1^2 + 1^2\)，我们可以将 \(c\) 的所有偶素因子 \(2\) 约去，接下来只需要考虑 \(c\) 的所有奇素因子.

显然 \(c\) 的所有奇素因子 \(p\) 都满足 \(p \not \equiv 2 \pmod{4}\)，因此这些奇素因子都只能是 \(4k + 1\) 或 \(4k + 3\) 的形式.

1. 若 \(p_i \equiv 1 \pmod{4}\)，根据费马平方和定理，\(p_i\) 可以被表示为两个整数的平方和，故可以将 \(p_i\) 约去.

2. 若 \(p_i \equiv 3 \pmod{4}\)，那么需要判断 \(p_i\) 在 \(c\) 因式分解中的幂次.

   • 若 \(p_i\) 在 \(c\) 因式分解中的幂次为偶数，由于 \(p_i^{2k} = (p_i^k)^2 + 0^2\)，故可以将 \(p_i^{2k}\) 约去.
   • 若 \(p_i\) 在 \(c\) 因式分解中的幂次为奇数，那么 \(c\) 一定不能表示为两个整数的平方和.

如此一直约去，直到 \(c^*\) 满足费马平方和定理或 \(c^*\) 是素数的偶数次方.

综上所述，得到结论如下：

结论

如果 \(c\) 所有的素因子 \(p\) 均满足下列条件之一，那么 \(c\) 一定可以表示为两个整数的平方和：

• \(p = 2\).
• \(p \equiv 1 \pmod{4}\).
• \(p \equiv 3 \pmod{4}\) 且 \(p\) 在 \(c\) 因式分解中的幂次为偶数.

若存在一个素因子 \(p\) 不满足上述任一条件，那么 \(c\) 一定不能表示为两个整数的平方和.

这个结论其实就是 二平方和定理

接下来开始遍历 \(c\) 的所有素因子.

对 \(c\) 的素因子的枚举，只需要枚举到 \(\sqrt{c}\) 即可.

为什么

如果 \(x\) 是 \(n\) 的因子，那么 \(\dfrac{n}{x}\) 也是 \(n\) 的因子. 故 \(n\) 的所有因子 \(x\) 都满足 \(x \leq \sqrt{n}\).

完整题解

import math

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        # 先验判断
        if c % 4 == 3:
            return False

        # 枚举 c 的所有素因子
        for p in range(2, int(math.sqrt(c)) + 1):
            if c % p == 0:
                exp = 0
                # exp = p[i] 在因式分解中的幂次
                while c % p == 0:
                    c //= p
                    exp += 1

                # 素因子不满足上述条件
                if p % 4 == 3 and exp % 2 != 0:
                    return False

                # 除此以外的其他情况均继续验证 p[i+1]
                # 即 else: continue

        return c % 4 != 3  # 判断最后一个素因子是否仍然满足条件

复杂度分析

我们只需要遍历 \([2, \sqrt{c}]\) 的数，故时间复杂度为 \(O(\sqrt{c})\)，

空间复杂度为 \(O(1)\)。

还是比双指针快的

评论