Java 已知直角三角形周长，求整数边

直角三角形周长

题目链接：https://www.cupacm.com/newsubmitpage.php?id=1094
这是一道非常典型的枚举题目，以下会一步一步分析如何对枚举进行优化。

题目描述
一个直角三角形的周长是120的话，那么它的三边可以是20，48，52，或者24，45，51，还有30，40，50，有3种不同的解。现在你想知道如果给定一个直角三角形的周长，那么这个周长最多能有多少解呢？假设边长为整数。

输入
第一行一个T TT,表示T TT组测试数据。1≤T≤10000 1\leq T\leq 100001≤T≤10000
每组测试数据占一行仅含一个整数A AA。0≤A≤100000 0\leq A\leq 1000000≤A≤100000

输出
根据每组测试数据请求出以整数A为周长的直角三角形的个数。（边长都为整数的直角三角形且周长为整数A）
输入.

	200
	12
	120

输出.

	1
	1
	3

题解
这是一道非常典型的枚举题目，以下会一步一步分析如何对枚举进行优化，希望能对其他枚举问题有所启发。

1.三重循环

看到这道题，首先会想到枚举三条边，如果能符合三条边加在一起等于周长，符合勾股定理，则满足条件并计数
出现问题：最普通的枚举时间超限
代码.

	public static int cum1(int l) {
		int count=0;
		for (int i = 1; i < l; i++) {	
			for (int j = 1; j < l; j++) {	
				for (int k = 1; k < l; k++) {	
					 if (i + j + k == l && i * i + j * j == k * k) {
			                count++;
			         }
				}
			}	
		}
		return count/2;	
	}

2.二重循环

现在，做一点优化，指定i≤j 这样可以避免i 与j重复枚举（例如345，435是同一个答案）来节约时间，k作为斜边，直接通过i j和周长便可以计算出k，减少一重循环。

代码.

	public static int cum2(int l) {
		int count=0;
		for (int i = 1; i < l; i++) {	
			for (int j =i; j < l; j++) {	
				int k = l - i - j;	
				if ( i * i + j * j == k * k) {
		               count++;
		        }				
			}	
		}
		return count;	
	}

还会超时，做一个优化

2.1优化二重循环

已知：
i+j+k=l;
0<i<j<k;
解得：i<l/3; j<l/2; k<i+j

代码.

	public static int cum3(int l) {
		int count=0;
		for (int i = 1; i < l / 3; i++)  {	
			  for (int j = i; j < l / 2; j++) {	
				int k = l - i - j;	
				if (k < i + j && i * i + j * j == k * k) {
		               count++;
		        }				
			}	
		}
		return count;	
	}

3.一重循环

已知 i+j+k=l;
i^2 +j^2 = k^2;
解出：
j=l−l^2 /(2l−2i) 。

以下为最优代码

代码.

	public static int cum(int l) {
		int count=0;
		for (int i = 1; i < l/3; i++) {			
			double j=l-(double)l*l/(2*l-2*i);
			if(i<j&&j-(int )j<1e-5) {
				count ++;
			}
		}		
		return count;
	}

参考： [CUPOJ] 直角三角形周长 枚举优化 题解，C++版本