Primitive Right Triangles

Difficulty: 2000 6000 ms 128 MB

number-theory

Count the primitive Pythagorean triples (a, b, c) with a² + b² = c², gcd(a, b, c) = 1, and hypotenuse c ≤ N.

Input: one integer N.

Output: the number of primitive triples with c ≤ N.

Constraints:

• 1 ≤ N ≤ 2×10⁶

Sample Tests

20

3

5

1

Read the Editorial