题意：给定一个n表示有n个1~n的数，现在要从这里面选出3个不同的整数问可以组成三角形的个数
思路：
1 n的上限是10^6，O(n^2)以上的时间复杂度都无法满足要求
2 设最大的变长为x，另外两边的为y和z并且x y 和z是不同的，那么有y+z > x，因此就有x-y < z < x
根据这个不等式我们知道，y = 1时无解，y = 2时有1个解 ........ y = x-1式有x-2个解。总的就是0+1+2.......+x-2 = (x-1)*(x-2)/2
3 但是上面的等式并不是正确的数值。因我上面的解包含了y = z的情况，而且每个三角形算了两遍，因为y和x的地位是等价的。我们怎么解决上面的问题呢？
先解决y = z的情况吧，当y = z的时候x - z < z < x，那么就有x < 2z，有x/2 < z < x，因此满足的z个数有(x-1)-(x/2+1)
那么只要扣掉这些解，再除以2即可。
4 根据上面的推理分析，我们可以知道题目实际上要求的是“最大边长不超过n的三角形的个数”，因为最大变长的范围从3～n，枚举是不可能的。但是我们仔细分析，我们可以事先打好表，ans[n]表示最大边长不超过n的三角形的个数，那么ans[n] = ans[n-1] + [(x-1)*(x-2)/2 - (x-1)-(x/2+1)]/2
代码：
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int64;
const int MAXN = 1000010;
int64 n , ans[MAXN];
int64 getVal(int64 x){
return ((x-1)*(x-2)/2-(x-1)/2)/2;
}
void init(){
ans[3] = 0;
for(int64 i = 4 ; i < MAXN ; i++)
ans[i] = ans[i-1]+getVal(i);
}
int main(){
init();
while(cin>>n && n >= 3)
cout<<ans[n]<<endl;
return 0;
}
