在求解100以内满足要求的勾股三元组时，以下关于枚举范围优化的说法错误的是？

st827648 单选题共个子题

勾股三元组指满足$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

正在加载题目数据…

第空

已答 /

子题

第空

提示

该题型需在试卷/作业中作答，单题练习暂不支持

答案解析