양의 정수 a,b,c,d가 ab=cd=N이고 a+b=c+d+1인 경우, 양의 정수 N은 은밀하다고(stealthy) 한다.
예를 들어, 36=4x9=6x6은 은밀하다.
106 이하에는 2851개의 은밀한 숫자(Stealthy Numbers)가 있다.
1014 이하에는 몇 개의 은밀한 숫자가 있는가?
--------------------------------------------------------------------------
문제는 그리 까다롭지 않아, 문제에서 요구한 것만 구현하면 코드가 그리 길지 않다. 숫자의 약수를 구해서, 약수가 n개인 경우 n/2개까지 두 숫자를 각각 a, c로 두고, b, d를 연산을 통해 구하고, a+b=c+d+1인 경우를 찾도록 만들었다.
하지만, 예시로 나온 1백만 이하에 몇 개가 있는지 검증하는데 벌써 속도 문제를 만나게 되었다. 문제에서 요구한대로 했을때 구해지는 답을 보고 4의 배수만 나오기 때문에 그것으로 성능을 조금 개선했다. 그래도, 약수를 구하는 부분에서 시간이 많이 소요되어서, 대상 숫자를 보니 전체 약수의 가운데 부근에 있었다. 예를 들어 설명하면 약수가 10개인 경우 4,5번째 숫자 또는 3,4번째 숫자가 a,c가 되는 것이었다. 그렇게 해서 속도를 개선하니 1백만 개 이하의 은밀한 숫자 갯수를 맞게 구할 수 있어서 문제에서 요구한 대로 구현했음을 알 수 있었다.
하지만, 1백만 개에 9초의 시간이 필요했으면, 문제에서 요구한 1경 개를 대상으로 구하려면 적어도 900000000초(250000시간)의 시간이 필요한 상황임을 알 수 있었다. 그 말은 문제를 있는 대로 구현하는 것이 아니고 새로운 알고리즘을 찾는 것을 요구하는 정수론 문제라는 것이었다.
인터넷을 검색해 보니, 깃헙에 누군가가 구현한 내용에서 bipronics라는 명칭으로 x*(x+1)*y*(y+1)을 구하는 정수 배열을 활용해서 구했다고 설명했는데, 그 정수 배열이 문제에서 요구하는 답과 동일한 것이었다. 왜 약수 중에 a+b=c+d+1인 약수와 x*(x+1)*y*(y+1)이 동일한지 이해는 안되었지만 그렇다고 한다. 처음 접근한 방법으로 안되었을 때, 숫자 리스트를 만들고 a+b=c+d+1을 만족하는 경우에 flag을 바꾸는 형태로 해결할 수 있을지 고민하다가, 변수가 너무 많아 포기했는데 조금은 비슷한 접근인 것 같기도 했다.
이 개념으로 구현하니 1백만 개는 0.04초만에 구할 수 있었는데, 그래도 1경 개를 구하는 데에는 시간이 꽤나 걸렸다. 조건에 맞는 리스트를 구하는 것보다 중복을 제거하는 데 시간이 더 많이 걸린 것이 함정이었다. 파이썬의 list(set())의 조합으로 중복을 제거했는데, 7천만 개 이상 리스트에서 중복 제거하는 데 많은 시간을 필요로 했다. 대충 1분 이내에 조건에 맞는 리스트를 구했는데 거기에서 중복을 제거하는 데 10분 이상 소요되었다.