1. 互质勾股数

只过了　86，求大佬指点

思路1：暴力

维护一个数组，数组的第　i 　位保存， i^2

然后暴力判断即可。。

思路２：找规律

见代码

import math

"""
假设勾股数满足 a^2 = b^2 + c^2， a, b, c互质
那么有 b^2 = (a+c)(a-c) 且 a b c一定是两奇数一偶数
其中 a+c 和 a-c 一定是 m^2 和 n^2 ,并且 m n 互质
下面的结论证明比较复杂，之前做题的时候看过这个证明。
简单说下上面的证明: 3 偶数，不行； 2偶数，不行，0 偶数，不行；只能是一奇数两偶数

有了这个结论，只需要一个数组保存某些数是否访问过，并且做一些边界判断即可.
然后寻找复合条件的 m 和 n，并把符合条件的a b c的倍数置为 True
"""

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


is_visited = [False for i in range(10 ** 7)]


def get_result(number):
    result = 0
    n_sqrt = int(math.sqrt(number))

    for i in range(1, n_sqrt + 1):
        for j in range(i + 1, number, 2):
            if i ** 2 + j ** 2 > number:
                break
            if gcd(i, j) != 1:
                continue
            result += 1

        minus = j ** 2 - i ** 2
        mul = 2 * i * j
        add = i ** 2 + j ** 2

        tmp_vis = 1
        while add * i <= number:
            is_visited[mul * tmp_vis] = is_visited[add * tmp_vis] = is_visited[minus * tmp_vis] = True

    return result


if __name__ == '__main__':
    while True:
        number = input()
        if not number:
            break
        number = int(number)

        print(get_result(number))

２．数组最大和

给定一个正数和一个负数，相邻的　７　个元素之和小于０，求数组最大和。

思路见代码或参考：

https://www.nowcoder.com/discuss/108052?type=2&order=0&pos=5&page=1

# encoding: utf-8
import math


def get_result(pos, neg):
    array = [0 for i in range(17)]

    # 找到连续 7 个元素最大可以有多少正数
    max_pos = 0
    for i in range(8):
        j = 7 - i
        if pos * i + neg * j < 0:
            max_pos = i
        else:
            break

    # 可以想象有这么一个滑动窗口，每次向右滑动一个位置。从左边去掉一个，右边补充一个相同的元素。
    # 那么问题实质是一个贪心问题，怎么使补充的元素是正数的数量最多？ 因此需要把最开始的 7 个元素，按照左边是正数，右边是负数的顺序排列
    # 然后依次重复就好了，剩下的 17 - 2*7 = 3 个元素，判断最多正数的数量和这个的大小即可。
    if max_pos >= 3:
        pos_num = 2 * max_pos + 3
    else:
        pos_num = 2 * max_pos + max_pos

    return pos_num * pos + (17 - pos_num) * neg


if __name__ == '__main__':
    while True:
        line = input()
        if not line:
            break
        pos, neg = list(map(int, line.strip().split()))

        print(get_result(pos, neg))