题意：从1~n中选出3个整数，使得他们三边能组成三角形，给定一个n，问能组成多少个不同的三角形？
分析：n最大能达到1000000，所以只能用O(n)来解决。
设最大边为x的三角形个数为C(x)，y+z>x , x-y<z<x,当y=1时 z无解，y=2，z一个解……y=x-1,z有x-2个解
所以0+1+2+……+x-2=(x-1)(x-2)/2，但是里面有y=z的情况。
我们将y=z的情况数单独计算，y的取值总x/2 + 1到x-1，共x-1-x/2=(x-1)/2种情况
而且里面每个三角形重复了2遍，所以c(x)=((x-1)*(x-2)/2-（x-1）/2)/2，
由于f[x]表示最长边不超过x的情况数
f[x]=f[x-1]+((x-1)*(x-2)/2-(x - 1)/2)/2。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 typedef long long LL; 5 const int N = 1100001; 6 LL f[N]; 7 int main(){ 8 f[3] = 0; 9 for(LL x = 4 ; x <= 1000000 ; x++)//这个地方要注意x要为longlong 10 f[x] = f[x - 1] + ((x - 1) * (x - 2) / 2 - (x - 1) / 2) / 2; 11 int n; 12 while(scanf("%d",&n) && n >= 3) 13 printf("%lld\n",f[n]); 14 return 0; 15 }
原文：http://www.cnblogs.com/cyb123456/p/5801383.html
