leetcode 633. 平方数之和 中等

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a*a+b*b=c 。

示例 1：

输入：c = 5
输出：true
解释：1 * 1 + 2 * 2 = 5

示例 2：

输入：c = 3
输出：false

提示：

• 

 分析：易知a和b的最大值为，因此可以枚举a的值，在计算是否存在一个满足条件的整数b。

bool judgeSquareSum(int c) {
    for(long long a=0;a*a<=c;++a)
    {
        double b=sqrt(c-a*a);
        if(b==(int)b)return true;
    }
    return false;
}

或者可以用双指针的方法改进上面这个代码。

bool judgeSquareSum(int c) {
    long long a,b,n=c;
    a=0,b=sqrt(c);
    while(a<=b)
    {
        if(a*a+b*b==c)return true;
        else if(a*a+b*b>c)b--;
        else a++;
    }
    return false;
}

最后是官方题解给出的数学方法。

费马平方和定理告诉我们：

一个非负整数 c 如果能够表示为两个整数的平方和，当且仅当 c 的所有形如 4k+3 的质因子的幂均为偶数。

证明请见 https://wstein.org/edu/124/lectures/lecture21/lecture21/node2.html。

因此我们需要对 c 进行质因数分解，再判断所有形如 4k+3 的质因子的幂是否均为偶数即可。

作者：力扣官方题解
链接：https://leetcode.cn/problems/sum-of-square-numbers/solutions/747079/ping-fang-shu-zhi-he-by-leetcode-solutio-8ydl/
来源：力扣（LeetCode）

题解代码：

bool judgeSquareSum(int c) {
    for (int base = 2; base * base <= c; base++) {
        // 如果不是因子，枚举下一个
        if (c % base != 0) {
            continue;
        }

        // 计算 base 的幂
        int exp = 0;
        while (c % base == 0) {
            c /= base;
            exp++;
        }

        // 根据 Sum of two squares theorem 验证
        if (base % 4 == 3 && exp % 2 != 0) {
            return false;
        }
    }

    // 例如 11 这样的用例，由于上面的 for 循环里 base * base <= c ，base == 11 的时候不会进入循环体
    // 因此在退出循环以后需要再做一次判断
    return c % 4 != 3;
}

原文地址：https://blog.csdn.net/2401_88085478/article/details/143494103

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！