11467 - Pythagorean Triangles

[baodog]

Hi,

I can only come up with O(n^4) algo for generating answers from 1...2000, but is too slow.
How is O(n^3) possible? Some hint is appreciated. Thanks!

[baodog]

Ahh, I found O(n^2logn) or Or O(n^3logn) for all 2000 cases.
Just shoot rays from single point.

[Monsoon]

can anyone verify my output, thx

Code: Select all

1
2
100
500
911
1000
1500
1999
2000
0

Code: Select all

4
44
360484740
302474108252
3667235277376
5400281116712
29018935378348
79411432484400
79574509024528

[Victor Barinov]

My AC program gives the same answer except two last.

My answer for two last is:

1999
95302811479600

2000
95500247758096