难度: Medium
给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
示例 1：
输入：c = 5 输出：true 解释：1 * 1 + 2 * 2 = 5
示例 2：
输入：c = 3 输出：false
提示：
0 <= c <= 231 - 1
Submission
运行时间: 48 ms
内存: 16.6 MB
class Solution:
def judgeSquareSum(self, c: int) -> bool:
if not c:
return True
while c % 2 == 0:
c //= 2
if c % 4 == 3:
return False
sqrt = int(math.sqrt(c))
for i in range(3, sqrt + 1, 4):
count = 0
while c % i == 0:
c //= i
count += 1
if count % 2 != 0:
return False
return True
Explain
该题解是基于数论知识和费马平方和定理来解决问题的。它首先判断特殊情况，如果c为0，则直接返回True。然后对c进行预处理，将c中的所有2的因子除尽。接下来，利用费马平方和定理的一个推论：一个正整数如果是4k+3的形式，那么它不能表示为两个整数的平方和。如果c满足这种情况，则直接返回False。最后，通过枚举c的因子，检查是否存在奇数次的因子为4k+3的形式，如果存在则返回False，否则返回True。
时间复杂度: O(sqrt(c) * log c)
空间复杂度: O(1)
class Solution:
def judgeSquareSum(self, c: int) -> bool:
# 特殊情况判断
if not c:
return True
# 预处理，除去c中的所有2的因子
while c % 2 == 0:
c //= 2
# 若c是4k+3的形式，根据费马平方和定理，不能表示为两个整数的平方和
if c % 4 == 3:
return False
# 枚举c的因子
sqrt = int(math.sqrt(c))
for i in range(3, sqrt + 1, 4):
count = 0
while c % i == 0:
c //= i
count += 1
# 若存在奇数次的因子为4k+3的形式，不能表示为两个整数的平方和
if count % 2 != 0:
return False
return True
Explore
在处理平方数之和的问题时，去除2的因子是为了简化问题。根据费马平方和定理，一个数如果可以表示为两个整数的平方和，那么它的每个因子也同样可以表示为两个整数的平方和。数字2可以被表示为1^2 + 1^2，因此任何包含因子2的数可以简化去除这些2的因子，不影响最终结果。这样做可以减少后续处理的复杂度，只需关注剩余部分是否可以表示为两个整数的平方和。
这个判断基于费马平方和定理的一个重要推论。具体来说，如果一个正整数可以表示为两个整数的平方和，那么它在质因子分解后，形式为4k+3的质因子（如果有的话）必须出现偶数次。如果一个数本身是4k+3的形式（其中k是整数），并且不能进一步分解为其它质因子的乘积，那么这个数就不能表示为两个整数的平方和。因此，这一步是针对不能进一步分解的情况进行快速判断。
费马平方和定理指出，一个正整数可以表示为两个整数的平方和（即n = a^2 + b^2）的条件是：它的每一个形式为4k+3的素数因子的指数都是偶数。这个定理对解题有直接影响，因为它提供了一个判断数是否可以表示为两个整数的平方和的数学基础。通过这个定理，我们可以通过检查数的质因子分解来确定是否满足条件，从而避免了盲目的搜索或过于复杂的运算。
选择从3开始，步长为4进行枚举是因为我们特别关注形式为4k+3的因子。这是因为，根据费马平方和定理，形式为4k+3的素数因子在质因子分解中必须具有偶数次幂才能使该数表示为两个整数的平方和。当从3开始以4为步长枚举时，你会得到3, 7, 11, 15, ..., 这确保了每个枚举的数都是形式为4k+3的数，从而直接定位到可能的关键因子，提高了效率。