给定一个非负整数 c ,你要判断是否存在两个整数 a 和 b,使得 a 2 +b 2 =c 。如果存在,则输出任意一组满足要求的 a 和 b;如果不存在,则输出-1。 注意:有限制运行时长,请尽量优化代码逻辑。 提示:使用java.lang.Math中的方法辅助运算。
时间: 2024-10-18 20:11:46 浏览: 36
给定一个非负整数num,反复将各个位上的数字相加,直到结果为一位数 .pdf
这个问题描述的是著名的“寻找平方和”(也叫“二元二次同余方程”)问题,即找到两个正整数 a 和 b,使得它们的平方和等于给定的一个非负整数 c。可以采用暴力枚举的方式来解决,但是为了提高效率,我们可以利用数学性质。
对于每个可能的 b(从0到 Math.sqrt(c)),计算 a 的值为 sqrt(c - b^2),然后检查 a 是否为整数。这是因为根据勾股定理,a 和 b 构成直角三角形的两条边,其斜边长度就是 c,所以 a^2 + b^2 必须等于 c。若计算出的 a 为整数,说明找到了解;若超过 sqrt(c),则没有必要再继续搜索,因为不可能存在大于 sqrt(c) 的 b 使得 a^2 + b^2 = c。
以下是Java代码实现:
```java
public int squareRoot(int c) {
for (int i = 0; i <= Math.sqrt(c); ++i) {
int a = Math.sqrt(c - i * i);
if (a * a == c) {
return a * i;
}
}
return -1;
}
```
阅读全文