[已解决]Python：每日一题 355

zltzlt

今天的题目：

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

示例 1：

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

示例 2：

输入：3
输出：False

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

flamezyy

2020-3-19 21:47:36

import math as m

def f355(integer):

    sqrt = m.sqrt(integer)

    sqrt_int = int(sqrt)

    if sqrt % 1:

        low_lim = int(m.sqrt(integer/2))

        for i in reversed(range(low_lim,sqrt_int+1)):

            rem = m.sqrt(integer - i*i)

            if rem % 1:

                continue

            else:

                return True

        else:

            return False

    else:

        return True

跳转到最佳答案楼层

qiuyouzhi

def f355(n):
    for i in range(n+1):
        for j in range(n+1):
            if pow(i,2) + pow(j,2) == n:
                return True
    return False

print(f355(8))

改用BIF

zltzlt

qiuyouzhi 发表于 2020-3-19 17:57
闲来无事先瞎写一个：

定会超时，待会再改改

输入 4 就有错

qiuyouzhi

zltzlt 发表于 2020-3-19 17:58
输入 4 就有错

！我滴妈
瞎写了一个居然。。。。
我去改改

zltzlt

qiuyouzhi 发表于 2020-3-19 17:59
！我滴妈
瞎写了一个居然。。。。
我去改改

4 = 0² + 2²

qiuyouzhi

zltzlt 发表于 2020-3-19 17:58
输入 4 就有错

能不能给几个测试用例，防止再次

最后的魁拔

import math
num = eval(input())

flag=0
for i in range(0,int(pow(num,1/2))+1):
        for j in range(0,int(pow(num,1/2))+1):
                if pow(i,2)+pow(j,2)==num:
                        flag = 1
                        print("True")
                        break
        if flag==1:
                break
if not flag:
        print("False")

zltzlt

qiuyouzhi 发表于 2020-3-19 18:01
能不能给几个测试用例，防止再次

8 和 1 返回 True

zltzlt

最后的魁拔 发表于 2020-3-19 18:02

输入 1000000000 超时

TJBEST

import math
def fun355(c):
    def isSquare(num):#判断平方数
        temp = math.floor((num**(1/2)))
        if temp * temp != num:
            return False
        else:
            return True
    def isHuZhi(a,b):#判断互质 a > b
        while b:
            a,b = b,a%b
        if a == 1:
            return True
        else:
            return False
    def findHuZhi(a):#a > 2寻找所有比a小的与a互质的数 返回列表
        result = []
        for index in range(1,a):
            if isHuZhi(a,index):
                result.append(index)
        return result
    
    if isSquare(c):
        return True  
    gate = math.floor(((c-1)**(1/2)))
    for index in range(1,gate+1):
        temp = 1 + index ** 2
        if c % temp == 0 and isSquare(c//temp):
            return True
    other = (-1+(2*c-1)**(1/2))/2
    gate = math.floor(other)
    for index in range(2,gate+1):
        HuZhiArr = findHuZhi(index)
        for each in HuZhiArr:
            other = (-each + (c-index)**(1/2))/index
            innergate = math.floor(other)
            for k in range(1,innergate+1):
                innerNum = k * index + each
                temp = (innerNum**2)+(index**2)
                if c % temp == 0 and isSquare(c//temp):
                    return True
    return False

fan1993423

这两个整数可以相同是吧，8的话是不是2**2+2**2这样的

永恒的蓝色梦想

我的代码：

from math import sqrt,ceil

class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        if not sqrt(c)%1:
            return True
        for i in range(1,ceil(sqrt(c))):
            if not sqrt(c-i*i)%1:
                return True
        return False

力扣大神解法：(128ms)

from math import sqrt,floor

class Solution:
    def judgeSquareSum(self, c):
        left=0
        right=floor(sqrt(c))

        while left<=right:
            total=left*left+right*right
            
            if total>c:
                right-=1
            elif total<c:
                left+=1
            else:
                return True

        return False

一个账号

import math
def func(c):
    for a in range(c+1):
        for b in range(c+1):
           if math.pow(a, 2) + math.pow(b, 2) == c:
               return True
    return False

wuqramy

zltzlt 发表于 2020-3-19 18:03
8 和 1 返回 True

1 = 0**2 + 1**2

kinkon

双针法

def fun355(c):
    r = int(c**0.5)
    if c - r <= 1:
        return True
    l = int((c - r*r)**0.5)
    for i in range(l, r+1):
        num = i*i + r*r           
        if num == c:
            return True
        elif num > c:
            r -= 1
    return False

如果上面不对，试试下面的

def p355(c):
    m = int(c**0.5)
    if c - m <= 1:
        return True
    while m:    
        if c == int((c - m*m)**0.5)**2 + m*m:
            return True 
        m -= 1
    return False

fan1993423

def fun355(c):
    for i in range(int(c**0.5)+1):
        if not (c-i**2)**0.5%1:
            return True
    return False

fan1993423

kinkon 发表于 2020-3-19 18:50
一行应该够了

输入8就错了

kinkon

fan1993423 发表于 2020-3-19 18:54
输入8就错了

改了

fan1993423

kinkon 发表于 2020-3-19 18:55
改了

还是错的，8是True

mdphd

import math
def f355(x):
    a = int(math.sqrt(x / 2))
    def f(m, n):
        i = m
        c = 0
        while i <= a:
            if int(math.sqrt(x - i ** 2)) != math.sqrt(x - i ** 2):
                i += n
            else:
                print('True')
                c = 1
                break
        if c == 0:
            print("False")
    if x % 4 == 0:
        f(0, 2)
    if x % 4 == 1:
        f(0, 1)
    if x % 4 == 2:
        f(1, 2)
    if x % 4 == 3:
        print("False")