프로젝트 오일러 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\) 가 서로 소인지를 확인하는 것이 시간을 조금 더 절약해 준다는 것을 알 수 있었다. (물론 시행착오를 거쳐서)

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