UVa 11401

From Algorithmist
Jump to navigation Jump to search

11401 - Triangle Counting[edit]

Summary[edit]

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

Explanation[edit]

The number of triangles with longest side is for as long as that sequence remains positive. Notice that, for , . From here, find a recurrence relation (or two) for and solve it to be able to complete the problem within the time limit.

Gotchas[edit]

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

Implementations[edit]

  • Using long long integers is sufficient for the problem.

Input[edit]

5
8
3
1000000
2

Output[edit]

3
22
0
83332958333750000