UVA 11401 Triangle Counting

You are given n rods of length 1, 2…, n. You have to pick any 3 of them & build a triangle. How many distinct triangles can you make? Note that, two triangles will be considered different if they have at least 1 pair of arms with different length.

Input

The input for each case will have only a single positive integer n (3<=n<=1000000). The end of input will be indicated by a case withn<3. This case should not be processed.

Output

 

For each test case, print the number of distinct triangles you can make.

Sample Input                                                  Output for Sample Input

5 8 0

3 22

题意：

告诉你一个数n  问1到n之内的数能组成的三角形有多少种  每个数字不能重复使用  （2 3 4）和（3 2 4）是一种情况

分析：

题目给的n的范围太大，所以不能用暴力  o(n^3)或o（n^2）来做  会直接超时的

所以得用一些数学处理方法，

设最长边为x的三角形数为w[x]  则  n的值就是w[1]+w[2]+……+w[n]即可；

由于三边关系 x+y>z

所以 z-x<y<z

手写一下几项的数目不难看出  对x为奇数还是偶数分两种情况讨论   而且关系不难发现 

代码：

#include<iostream>
#include<string.h>
#include<math.h>
#include<stdio.h>
#include<iomanip>
using namespace std;

long long int a[1000003];


int main()
{
    a[4]=1;
    for(long long int i=5;i<=1000000;i++)
    {
        if(i%2==0)
        a[i]=a[i-1]+(i/2-1)*(i/2-2)+(i/2-1);
        else if(i%2==1)
        a[i]=a[i-1]+(i/2)*(i/2-1);
    }
    long long int n;
    //freopen("aa.txt","r",stdin);
    while(cin>>n)
    {
        if(n<3)
            break;
        else
            cout<<a[n]<<endl;
    }
    return 0;
}