贝壳主机网
注意：部分文章发布时间较长，可能存在未知因素，购买时建议在本站搜索商家名称，先充分了解商家动态。
交流：唯一投稿邮箱：hostvps@88.com。
网友 251768938 说：
如果 a+b+c=1000，且 a^2+b^2=c^2（a,b,c 为自然数），如何求出所有a、b、c可能的组合?
大佬们有更优的算法吗？
发代码被拦截了，所以截图，大佬们要想**可以到
https://www.vrt.app/246.html
网友 ShadowSaint 说：
*帖最后由 ShadowSaint 于 2022-6-26 00:17 编辑
你这个算法的时间复杂度应该是O(nlo**)嘛，应该能优化到O(n)的
我的理解啊：
已知：
1、直角三角形
2、三边只和长度为1000
求：
每条边都为正整数的所有解
因为：
直角三角形一条直角边长已知，且周长已知，那么另外两条边有且仅有唯一解
如：
短直角边a
长直角边b
斜边c
当a=1时
b方+a方=c方
b方+1=(1000-1-b)方
b方+1=(1000-1)方 – 2*（1000-1）*b + b方
1=(1000-1)方 – 2*（1000-1）*b
b=( (1000-1)方 – 1) / (2*（1000-1) )
等号右边都是已知量，这时候只要b是正整数即为解，并且如果a!=b，一下就求出来两个解，这里500/根号2必不可能是整数，所以不存在等腰直角三角形的情况
所以:
只需要遍历一遍就够了，时间复杂度为O(n)
伪代码：
循环 a 从1到 500/根号2，每次循环自增1
b = ( (1000-a)方 – a方) / (2*（1000-a) )
if (b为正整数 且 b < 500)
输出 a, b, c = a, b, 1000-a-b
输出 a, b, c = b, a, 1000-a-b
大概就是这样，循环到500/根号2是因为，如果是等腰直角三角形的话边长最多就是500/根号2，再大就没有意义了，之前遍历过这样的情况
没验证，可能有bug哈
网友 xieshang 说：
*帖最后由 xieshang 于 2022-6-25 23:44 编辑
直接枚举平方数会不会要好些？(指先预处理一个平方数库;把a^2当作a1,b^2当作a2,c^2当作a3,a1和a2从平方数中枚,加起来看下是不是平方数,不是或者s*rt(a3)不等于1000-a-b就继续枚)
网友 gdtv 说：
别和我说什么算法，无脑用for循环穷举就行了
网友 2CO3 说：
穷举法,极限也就那样
网友 lsin 说：
虽然想不出更好的，但是一看你这个就压根没用到啥算法，建议读读数论
网友 bugtrap 说：
能跑就行，能出来结果就行
网友 HOH 说：
哪有什么最优，能算出来就行
网友 asd1314s 说：
算个P法，暴力强算
网友 251768938 说：
ShadowSaint 发表于 2022-6-26 00:02
你这个算法的时间复杂度应该是O(nlo**)嘛，应该能优化到O(n)的
我的理解啊：
网友 lsin 说：
试了下9楼大佬的，楼主的时间是200x，论坛居然不让发代码…
网友 VPS小白白 说：
a+b>c 令c>b>a（之后把算出来所有的满足条件的ab值交换即可得到所有可能性），因此c的值在334到499之间。(1000-c)^2-2ab=c^2 所以ab=5e5-c，如果c为偶数，a和b也为偶数，c为奇数，ab一奇一偶。
网友 VPS小白白 说：
说错了，c应该是334～500。其实我想到一种解法，固定c的值以后，画一条长为c的线段，再画一个以线段两端点为焦点的椭圆，上面的点到焦点距离和为1，再画一个以线段为直径的正圆。通过椭圆和正圆的交点就可以求出a和b的值。
网友 VPS小白白 说：
我用**打字不方便，应该是 （上面的点到焦点距离和为1000-c），因为这是个解方程题目，应该对于满足范围的每个c都能求出解，但我们只需要自然数解，所以可以不用求精确解，比如**下山法之类的，每个c的求解，复杂度在O(logN)，加上c的范围大概是O(NlogN)
网友 VPS小白白 说：
而且NlogN应该是最坏的情况，精度为1的话**下山法收敛很快的（基础不是很记得牢了），总之这个方法对数学要求较高一些。
网友 小二的cat 说：
啊这。直接abc随便取一个变量，0到1000遍历。比如把c从0到1000遍历，那这不就是求解一元二次方程的根了吗，一次遍历就结束了啊
