uva11401(Triangle Counting)

計算は1、2、3、…からnでは3つの異なる整数を選択し,それらを辺長として三角形の個数を構成できるようにした.
考え方:一般的な方法で三重サイクルが必要で、時間の複雑度はO(n^3)で、必ずタイムアウトするので、数学の方法で問題を分析することができます.最大辺長をxの三角形にc(x)個、その他の両側長をy,zとすれば、x-yを得ることができます
以上の解析から,最大辺長がnを超えない三角形の数はf(n)=c(1)+c(2)+...+c(n)であることが分かった.

#include
long long f[1000005],x;
int main()
{
	int n;
	f[3]=0;
	for(x=4;x<=1000000;x++)//  +    
		f[x]=f[x-1]+((x-1)*(x-2)/2-(x-1)/2)/2;
	while(scanf("%d",&n)==1)
	{
		if(n<3) break;
		printf("%lld
",f[n]);
	}
	return 0;
}