[Hard] TheLuckyBasesDivOne

주어진 n이 그 자체로 lucky number 라면 답은 -1 그렇지 않다면 두자리 이상으로 표현되어야 한다. 1) p진법 두자리로 표현되는 경우 a*p+b = n 이다. a*a < a*p < n , a*max(a,b)+b < a*p+b = n 이므로 이 두 조건으로 커팅하면 가능한 (a, b) 쌍이 백만개 쯤 나온다. 그 모든 (a, b) 에 대해 유효한 p가 존재하는지 확인 2) p진법 세자리로 표현되는 경우 a*p*p+b*p+c = n 이다. a*a*a < a*p*p < n , a*max(a,b)*max(a,b)+b*max(a,b) < a*p*p+b*p < n , a*max(a,b,c)*max(a,b,c)+b*max(a,b,c)+c < a*p*p+b*p+c = n 이므로 이 세 조건으로 커팅하면 가능한 (a, b, c) 쌍이 또 백만개 쯤 나온다. 그 모든 (a, b, c) 에 대해 유효한 p가 존재하는지 확인 주의할 점은 p를 구할 때 2차방정식을 풀어야 하는데, integer overflow 때문에 판별식 값을 제대로 구할 수 없다. 이분탐색으로 해를 구할 수도 있고, double로 근사값을 구해서 적당히 처리할 수도 있다. 3) p진법 네자리 이상으로 표현되는 경우 네자리일 때는 a*p*p*p+b*p*p+c*p+d = n 이다. 이 때, p^3 < a*p*p*p < n 이므로 p < n^(1/3) 다. 자리수가 길어질수록 상한은 더 줄어든다. n^(1/3)의 상한이 21만 정도 이므로 모든 p를 다 돌아보면서 n을 p진법으로 나타냈을 때 모든 자리가 lucky number 인지 직접 확인하면 된다. 모든 단계마다 integer overflow 를 조심해서 구현하자. a*b > n 을 a > n/b 로 대신 쓸 수 있다.