Project Euler #75 Singular integer right triangles

It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.

120 cm: (30,40,50), (20,48,52), (24,45,51)

Given that L is the length of the wire, for how many values of L ≤ 1,500,000 can exactly one integer sided right angle triangle be formed?

---

긴 철사를 구부려서 세 변이 정수인 직각삼각형을 만들 때, 그 방법이 한 가지 뿐인 경우는 12cm를 최소로 해서 아래와 같이 여러 개가 있습니다.

12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)

반면에 20cm의 경우처럼 세 변이 정수인 직각삼각형을 만들 수 없을 때도 있고, 여러 종류의 직각삼각형을 만들 수 있을 때도 있습니다. 예를 들어 120cm의 철사로는 세 가지의 서로 다른 직각삼각형이 만들어집니다.

120 cm: (30,40,50), (20,48,52), (24,45,51)

그러면 길이가 1,500,000 이하인 철사를 가지고 세 변이 정수인 직각삼각형을 만들 때, 그 길이로는 한 가지 방법으로만 만들 수 있게 되는 경우는 모두 얼마나 됩니까?

(번역은 euler.synap.co.kr에서 퍼왔습니다.)

피타고라스의 세쌍을 이용하는 문제입니다;

임의의 정수 x,y에 대해서() 직각삼각형을 이루는 세 정수의 변은 

꼴로 나타납니다.

일단 1)둘레가 150만 이하의, 직각삼각형의 세변이 다 서로소인 원시 피타고라스 쌍을 구하고, 각각의 둘레를 list에 추가시켰습니다. 

2)원시피타고라스 쌍에 상수 c를 곱해주면 그거 역시 피타고라스 쌍이 될 것입니다. 그래서 원시 피타고라스 쌍의 둘레에 자연수 n(2부터 125000까지)을 곱해줘서 그 중 150만 이하인 것만 피타고라스 쌍에 추가시켰습니다. 

3)이렇게 만들어진 가능한 직각삼각형의 둘레들의 list에서 1번만 등장하는 것들의 갯수를 구했습니다.

MATLAB으로 작성했습니다.

clc,clear

x=2;

y=1;

len=2*x*(x+y);%직각삼각형의 둘레

candi=[];%둘레들의 집합

while 2*x*(x+y)<=1500000%원시피타고라스쌍의 둘를 구해봅시다.

    while 2*x*(x+y)<=1500000 && y<=x

       if gcd(x,y)==1

        len=2*x*(x+y);

        candi(end+1)=len;

       end

       y=y+2;

    end

x=x+1;

y=1+(rem(x,2)==1);

end

n=2;%가능한 모든 직각삼각형의 둘레를 list에 추가시킵니다.

new=2*candi;%새로추가될 둘레입니다.

new=new(new<=1500000);

pytha=candi;%pytha는 가능한 둘레들의 list

pytha=[pytha new];

while n~=125000

    n=n+1;

    new=n*candi;

    new=new(new<=1500000);

    pytha=[pytha new];

end

[count num]=hist(pytha,unique(pytha));%각 둘레들이 몇번 등장했는지..

answer=length(find(count==1));%답입니다.

음... 오래 걸렸습니다. 20분 정도 걸렸나? 좀 더 효율적으로 코드를 짜야겠습니다. 문제푸는 아이디어는 진작에 잡았는데, 원시 피타고라스 쌍을 구할 때 1)x,y가 서로소이고, 2)x,y의 홀짝성이 달라야 한다는 사실을 간과해서 그간 답을 못 구했었네요 :(