https://vjudge.net/problem/UVA-11401
題目大意：計(jì)算從1,2,3疆偿，...，n中選出3個(gè)不同的整數(shù)济竹，使得以它們?yōu)檫呴L可以構(gòu)成三角形的個(gè)數(shù)惋啃。
思路：用一般的方法需要三重循環(huán)，時(shí)間復(fù)雜度為O（n^3）毅该，肯定超時(shí)博秫，因此可用數(shù)學(xué)的方法對問題進(jìn)行分析。設(shè)最大邊長為x的三角形有c（x）個(gè)眶掌，另外兩邊長分別為y挡育，z，則可得x-y<z<x朴爬；固定x枚舉y即寒，計(jì)算個(gè)數(shù)0+1+2+...+(x-2)=(x-1)(x-2)/2。上面的解包含了y=z的情況召噩，而且其他情況算了兩遍母赵。而y=z的情況時(shí)y從x/2+1枚舉到x-1為止有（x-1）/2個(gè)解，所以c（x）=((x-1)*(x-2)/2-(x-1)/2)/2具滴。
由以上分析可得凹嘲，最大邊長不超過n的三角形數(shù)目為f（n）=c（1）+c（2）+...+c（n）。
#include<stdio.h>
#include<algorithm>
#include <string.h>
using namespace std;
#define maxn 1000010
typedef long long LL;
LL sum[maxn];
int main()
{
int n;
sum[3]=0;
for(long long i=4;i<=1000000;i++)
{
sum[i]=sum[i-1]+((i-1)*(i-2)/2-(i-1)/2)/2;
}
while(scanf("%d",&n)!=EOF)
{
if(n<3) break;
printf("%lld\n",sum[n]);
}
}
