LCC '22 Contest 5 S2 - Triple Triangulation Trouble

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

Jimmy and Patrick are hanging out when the topic suddenly comes to triangles, and they discuss their triangular preferences. Jimmy is a fan of right triangles. In fact, he believes that right triangles are superior to other triangles. Hearing this, Patrick says "Oh yeah? Name every right triangle." Of course, this is unreasonable, and a fight breaks out between Jimmy and Patrick. Joshua comes along and stops the fight by asking this puzzling question: how many right triangles have integer side lengths with an area under or equal to A?


1 \le A \le 5 \times 10^5

Subtask 1 [10%]

1 \le A \le 10^4

Subtask 2 [90%]

No further constraints.

Input Specification

The first and only line of input contains an integer A.

Output Specification

Output the total number of right triangles with integer side lengths under or equal to area A.

Sample Input 1


Sample Output 1


Sample Explanation

There are 2 right triangles with area less than or equal to 25, 3-4-5 and 8-6-10. Note, 3-4-5 and 4-3-5 are the same triangle.


There are no comments at the moment.