K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
勾股三元组指满足$a^2 + b^2 = c^2$的三个正整数$a、b、c$,本题要求$a \leq b \leq c$且三个数均不超过100。
$a$的枚举上界可优化为70,因为$a \leq b$,故$2a^2 \leq a^2 + b^2 = c^2 \leq 100^2$,推导得$a \leq \sqrt{10000/2} \approx70.7$,取整数上界70
$b$的枚举范围可优化为从$a$到$floor(\sqrt{100^2 - a^2})$,因为$b \geq a$且$a^2 + b^2 \leq 100^2$
可以直接取消$c$的枚举循环,计算$c=\sqrt{a^2 + b^2}$后判断$c$是否为正整数且$\leq100$即可,可将时间复杂度从$O(N^3)$降为$O(N^2)$
最优枚举方案下,$a$的上界可优化为33,因为$a \leq b \leq c$,故$3a \leq a + b + c \leq 3*100$,推导得$a \leq 100/3 \approx33.3$,取整数上界33