[Euler Project 091] 직각삼각형 갯수 구하기

50, 50 격자 안에서 한 꼭지점이 원점에 있고, 꼭지점이 격자점에 위치하는 직각삼각형의 갯수 구하기. 오일러 프로젝트 91번 문제이다. 직각이 원점에 있는 경우, 직각이 축에 위치하는 경우, 그리고 나머지 경우에 대해 나누어 갯수를 구했다.

---

#!/usr/bin/env python



# http://projecteuler.net/index.php?section=problems&id=91



def get_cnt_when_right_angle_is_O(max):

        ''' P is (0, [1 ... max]) and Q is ([1 ... max], 0)'''

        return max * max



def get_cnt_when_right_angle_is_on_axis(max):

        ''' When P is (0, y), Q is ([1 ... max], y).

            When Q is (x, 0), P is (x, [1 ... max]).'''

        return max*max + max*max



def gcd(a, b):

        if a > b :

                min, max = b, a

        else:

                min, max = a, b

        while max%min != 0:

                min, max = max%min, min

        return min



def get_cnt_when_right_angle_on(x, y, max):

        g = gcd(x, y)

        u1 = [ y/g, -x/g ]

        #print(u1)

        cnt1 = 0

        while max >= x + (cnt1+1)*u1[0]  and x + (cnt1+1)*u1[0] >= 0 and max >= y + (cnt1+1)*u1[1] and y + (cnt1+1)*u1[1] >= 0:

                #print(cnt1, x+(cnt1+1)*u1[0], y+(cnt1+1)*u1[1])

                cnt1+=1

        u2 = [ -u1[0], -u1[1] ]

        #print(u2)

        cnt2 = 0

        while max >= x + (cnt2+1)*u2[0]  and x + (cnt2+1)*u2[0] >= 0 and max >= y + (cnt2+1)*u2[1] and y + (cnt2+1)*u2[1] >= 0:

                #print(cnt2, x+(cnt2+1)*u2[0], y+(cnt2+1)*u2[1])

                cnt2+=1

        return cnt1 + cnt2



MAX=50

count = 0

count += get_cnt_when_right_angle_is_O(MAX)

print(count)

count += get_cnt_when_right_angle_is_on_axis(MAX)

print(count)

for x in range(1, MAX+1):

        for y in range(1, MAX+1):

                c = get_cnt_when_right_angle_on(x, y, MAX)

                if c != 0:

                        print(x, y, c)

                count += c

print(count)

---

http://marocchino.blogspot.com/2009/11/%EC%98%A4%EC%9D%BC%EB%9F%AC-%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8-91-%ED%8C%8C%EC%9D%B4%EC%8D%AC.html