프로젝트 오일러 127번

The radical of $n$, ${\rm rad}(n)$, is the product of distinct prime factors of $n$. For example, $504=2^3 \times 3^2 \times 7$, so ${\rm rad}(504)=2 \times 3 \times 7 = 42$.

We shall define the triplet of positive integers $(a, \;b,\;c)$ to be an abc-hit if:

1. ${\rm GCD}(a, \;b)={\rm GCD}(a, \;c) = {\rm GCD}(b, \;c)=1$

2. $a<b$

3. $a+b=c$

4. ${\rm rad}(abc)<c$

For example, $(5, \;27, \; 32)$ is an abc-hit, because:

1. ${\rm GCD}(5, \;27)={\rm GCD}(5, \;32) = {\rm GCD}(27, \;32) =1$

2. $5<27$

3. $5+27=32$

4. ${\rm rad}(4320)=30<32$

It turns out that abc-hits are quite rare and there are only thirty-one abc-hits for $c<1000$, with $\sum c = 12523$.

Find $\sum c$ for $c<120000$.

---

${\rm rad}(n)$ 은 자연수 $n$ 의 소인수들을 모두 곱한 값이다. 예를 들어, $504=2^3 \times 3^2 \times 7$ 이기 때문에 ${\rm rad}(n)=2\times 3 \times 7 =42$ 가 된다.

또한 세 자연수 $(a, \;b,\;c)$ 가 다음의 네 가지 조건을 만족시키면 abc-hit 이라고 한다. (${\rm GCD}(a, \;b)$ 는 $a, \;b$의 최대 공약수를 나타낸다.)

1. ${\rm GCD}(a, \;b)={\rm GCD}(a, \;c) = {\rm GCD}(b, \;c)=1$

2. $a<b$

3. $a+b=c$

4. ${\rm rad}(abc)<c$

예를 들어, $(5, \;27, \; 32)$ 는 abc-hit 가 된다. 왜냐하면 네 가지 조건

1. ${\rm GCD}(5, \;27)={\rm GCD}(5, \;32) = {\rm GCD}(27, \;32) =1$

2. $5<27$

3. $5+27=32$

4. ${\rm rad}(4320)=30<32$

를 만족시키기 때문이다. 

이러한 abc-hit은 매우 드물게 발생하기 때문에 $c<1000$ 일 때, $31$ 가지 경우만 있고, $31$ 가지 경우에 대해서 모든 $c$ 값들을 더하면 $\sum c =12523$ 이 된다.

$c<120000$ 에 대해서 abc-hit 가 되는 모든 경우의 $c$ 값들을 더한 $\sum c$ 를 구하시오. 

이 문제를 풀기 위해서 꼭 알아야 할 것이 바로 유클리드 호제법이다. 유클리드 호제법은 $a, \;b \;\;( a >b)$ 의 최대 공약수는 $a$ 를 $b$ 로 나눈 나머지 $r$과 $b$ 의 최대공약수와 같다는 것이다. "유클리드 호제법" 게시물을 참고하기 바란다. 

유클리드 호제법에 의하면 $a, \;c$ 가 서로소이면 유클리드 호제법과 위의 세 번째 조건에 의하여 자연스럽게 $a, \;b$ 와 $b, \;c$ 도 서로소가 된다. 따라서 우리가 체크해야 할 것은 $a, \;c$ 가 서로소인지 아닌지만 확인하면 된다.

다음으로 $c$ 값은 $3 \le c <120000$ 범위에서 루프를 돌리고, 이 때 $b=c-a$ 이고 $a<b$ 이어야 하므로 다음과 같은 $a$ 의 범위에서 두 번째 루프를 돌리면 된다.

1. $c$ 가 홀수이면 $1 \le a \le c // 2$   (단, $c // 2$ 는 $c$ 를 $2$ 로 나눈 몫)

2. $c$ 가 짝수이면 $1 \le a \le (c // 2) -1$

이제 위의 네 번째 조건을 만족시키는지 확인만 하면 되는데, 이것은 이미 124번에서 ${\rm rad}$ 를 구하는 방법을 배웠으므로 $1 \le n \le 120000$ 범위에서 ${\rm rad}(n)$ 을 구하여 이 값을 사용하면 된다. 따라서 ${\rm rad}(a) \times {\rm rad}(c-a) \times {\rm rad}(c) < c$ 인지 확인만 하면 되는 것이다.

첫 번째 시도에서는 $a$와 $c$ 가 서로소인지를 먼저 확인하고 나서 ${\rm rad}(a) \times {\rm rad}(c-a) \times {\rm rad}(c) < c$ 조건을 확인했는데, 생각해보니 abc-hit 가 되는 경우가 매우 드물게 발생한다고 했으므로, 먼저 ${\rm rad}(a) \times {\rm rad}(c-a) \times {\rm rad}(c) < c$ 인지 확인하고 나서 $a, \;c$ 가 서로 소인지를 확인하는 것이 시간을 조금 더 절약해 준다는 것을 알 수 있었다. (물론 시행착오를 거쳐서)

이런 방법으로 문제에서 요구하는 답을 구해낼 수 있다. 하지만 여전히 시간이 상당히 오래 걸린다. 뭔가 더 나이스한 방법이 있을 것 같은데, 아직까지 내 머리에서 나올 수 있는건 여기까지 인듯....ㅠㅠ