# UVa 11401

## Summary

Calculate the number of non-congruent non-degenerate scalene triangles with integer sides with maximum side length n.

## Explanation

The number of triangles with longest side ${\displaystyle n}$ is ${\displaystyle f(n)=(n-3)+(n-5)+(n-7)+...}$ for as long as that sequence remains positive. Notice that, for ${\displaystyle n>3}$, ${\displaystyle f(n)+f(n-1)={n-2 \choose 2}}$. From here, find a recurrence relation (or two) for ${\displaystyle F(n)=n\sum _{k=3}^{n}{f(k)}}$ and solve it to be able to complete the problem within the time limit.

## Gotchas

• The program should terminate for any input value less than 3, but 3 itself needs to be processed.

## Implementations

• Using long long integers is sufficient for the problem.

## Input

5
8
3
1000000
2

## Output

3
22
0
83332958333750000