PAT-2021年秋季考试乙级 7-1 好数 (15 分)

原创

freesan44

修改于 2021-09-14 10:34:03

5450

修改于 2021-09-14 10:34:03

文章被收录于专栏：freesan44

题目

好数是指由一对正整数 a<b 按照 a

+ab+b

这个规则生成的数，a 和 b 就称为这个好数的源头。例如 91 就是一个好数，因为 5

+5×6+6

=91，于是数对（5，6）就是 91 的源头。而对于一个好数，其源头并不一定唯一，例如（1，9）就是 91 的另一个源头。

本题就要求你编写程序，判断一个给定的数字是否好，并且输出好数的所有源头。

输入格式：

输入在第一行给出一个不超过 100 的正整数 N，随后 N 行，每行给出一个不超过 10

的正整数。

输出格式：

对于每一个输入的数字，如果其是好数，则首先在一行中输出 Yes，然后每行输出它的一个源头，格式为 a b，按 a 的递增顺序输出；否则在一行中输出 No和比该数大的最小的好数，其间以空格分隔，然后每行输出这个好数的一个源头，格式同上。

输入样例：
3
1
91
50
输出样例：
No 7
1 2
Yes
1 9
5 6
No 52
2 6

解题思路

N = int(input())
# N = int("3")

inputList = []
for _ in range(N):
    i = int(input())
    # i = int("91")
    inputList.append(i)
maxNum = max(inputList)
import math
sqrtNum = int(math.sqrt(2*maxNum))
# sqrtNum = int(maxNum//2)
duishuDict = dict()
for i in range(1,sqrtNum):
    for j in range(i+1,sqrtNum):
        # print(i,j)
        res = (i+j)**2-(i*j)
        if res>0:
            if res in duishuDict:
                duishuDict[res] += [(i,j)]
            else:
                duishuDict[res] = [(i,j)]
# print(duishuDict)
duishuList = [int(i) for i in duishuDict.keys()]
duishuList.sort()
# print(duishuDict)
for test in inputList:
    if test in duishuDict:
        print("Yes")
        arr = duishuDict[test]
        for x,y in arr:
            print(x,y)
    else:
        #定位最近好熟
        for i in duishuList:
            if i > test:
                print("No",i)
                arr = duishuDict[i]
                for x, y in arr:
                    print(x, y)
                break

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

python

数据结构

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

python

数据结构

登录后参与评论

0 条评论

热度