第31006题 单选题
在求解100以内满足要求的勾股三元组时,以下关于枚举范围优化的说法错误的是?

勾股三元组指满足$a^2 + b^2 = c^2$的三个正整数$a、b、c$,本题要求$a \leq b \leq c$且三个数均不超过100。

A

$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

$b$的枚举范围可优化为从$a$到$floor(\sqrt{100^2 - a^2})$,因为$b \geq a$且$a^2 + b^2 \leq 100^2$

C

可以直接取消$c$的枚举循环,计算$c=\sqrt{a^2 + b^2}$后判断$c$是否为正整数且$\leq100$即可,可将时间复杂度从$O(N^3)$降为$O(N^2)$

D

最优枚举方案下,$a$的上界可优化为33,因为$a \leq b \leq c$,故$3a \leq a + b + c \leq 3*100$,推导得$a \leq 100/3 \approx33.3$,取整数上界33

程序运行统计
暂无判题统计
提交0次 正确率0.00%
答案解析