平方和

# -*- coding: utf-8 -*-

import math


#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param c int整型
# @return bool布尔型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/6eade96172be4c8ba492747156481b9b?tpId=196&tqId=40562&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        枚举x，取值范围[1, sqrt(c)]，m = c - x * x，如果y^2 == m，y为整数，那么说明有解，返回True
    复杂度：
        时间复杂度：O(n), n = sqrt(c)
        空间复杂度：O(1)
    """

    def square(self, c):
        # write code here
        sqrtC = int(math.sqrt(c))

        for x in range(1, sqrtC + 1):
            m = c - x * x
            if m == 0:
                break
            y = int(math.sqrt(m))
            if y * y == m:
                # print x, y
                return True

        return False


if __name__ == "__main__":
    sol = Solution()

    # c = 5

    # c = 25

    c = 24

    res = sol.square(c)

    print res