We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #91: Right triangles with integer coordinates
  4. Discussions

Project Euler #91: Right triangles with integer coordinates

Sort by

recency

|

5 Discussions

|

  • beta_projects
     + 0 comments

    For a detailed explanation check out Project Euler 91

    import math
N = int(input())
t = sum(min(x*m//y, m*(N - y)//x)
        for x in range(1, N+1)
        for y in range(1, N)
        for m in [math.gcd(x, y)])
print(2*t + 3*N*N)

  • antonbyv
     + 0 comments
    Python 
    from math import gcd

N = int(input())

result = 3 * N ** 2
for x in range(1, N+1):
    for y in range(1, x+1):
        den = gcd(x, y)
        d_x, d_y = x // den, y // den
        
        found = 0
        n_x, n_y = x - d_y, y + d_x
        while n_x >= 0 and n_y <= N:
            found += 1
            n_x, n_y = n_x - d_y, n_y + d_x
            
        n_x, n_y = x + d_y, y - d_x
        while n_y >= 0 and n_x <= N:
            found += 1
            n_x, n_y = n_x + d_y, n_y - d_x
            
        result += found * 2 if x != y else found
        
print(result)

  • bhavikgevariya
     + 1 comment

    what's ans for 2500?

  • kitchent
     + 0 comments

    The key for this problem is to find out different kinds of triangle that can be formed in this setting. You won't want to iterate every pair of points to check whether a right triangle can be formed or not. Instead, you get a right triangle and check whether it is within the upper bound.

    Certain triangles are easy to get. Those with two side along x-axis and y-axis respectively. Those with one side along either axis where the axis itself is not hypotenuse. With some further observation you can get the rest based on the above triangles with rotation and gcd.

  • Kingofthekings
     + 1 comment

    I dont understand this question. In the given example why is the triangle formed by (0,1) , (1,0) , (1,1) not present in the list.

No more comments