好数是指由一对正整数 a<b 按照 a
2
+ab+b
2
这个规则生成的数,a 和 b 就称为这个好数的源头。例如 91 就是一个好数,因为 5
2
+5×6+6
2
=91,于是数对(5,6)就是 91 的源头。而对于一个好数,其源头并不一定唯一,例如(1,9)就是 91 的另一个源头。
本题就要求你编写程序,判断一个给定的数字是否好,并且输出好数的所有源头。
输入格式:
输入在第一行给出一个不超过 100 的正整数 N,随后 N 行,每行给出一个不超过 10
4
的正整数。
输出格式:
对于每一个输入的数字,如果其是好数,则首先在一行中输出 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 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。