【蓝桥杯】算法笔记1

1.暴力枚举

给定一个正整数n，请找出所有满足a² + b² = n的整数对(a, b)，其中a和b都是正整数，且a ≤ b。

输入格式：一个正整数n (1 ≤ n ≤ 10⁶)
输出格式：所有符合条件的(a, b)对，每行一对，按a的升序排列。如果没有符合条件的对，输出"No solution"。

问题分析：我们需要找到所有满足a² + b² = n的正整数对(a, b)，其中a ≤ b。

枚举策略：由于a和b都是正整数且a ≤ b，a的最大可能值是√(n/2)，因为如果a > √(n/2)，那么a² > n/2，b² = n - a² < n/2 < a²，这将导致b < a，与a ≤ b矛盾。

算法选择：采用枚举算法，遍历a的所有可能取值，对于每个a，计算b² = n - a²，然后检查b是否为整数。

优化：在枚举a时，只需要枚举到√(n/2)即可，减少不必要的计算。

import mathdef find_num(n):result=[]max_a=math.isqrt(n//2)  #计算n//2的整数平方根for a in range(1,max_a+1):remainder=n-a*ab=math.isqrt(remainder)if b*b==remainder and b>=a:result.append((a,b))return resultn=int(input("请输入一个整数："))
pairs=find_num(n)if not pairs:print("No solution")
else:for a,b in pairs:print(a,b)

input()