• m > 2인 경우에 k(m)은 짝수이다.
• 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다.
• k(m) ≤ m² - 1
• k(2ⁿ) = 3×2^(n-1)
• k(5ⁿ) = 4×5ⁿ
• k(2×5ⁿ) = 6n
• n > 2라면, k(10ⁿ) = 15×10^(n-1)

지문에 이렇게 나와있는데

게시판에서 밑의 코드를 우연히 보았습니다.

저의 의문점은 2<=M<=1000000 의 데이터 범위에서  k(m) ≤ m² - 1 라는 조건이 있는데 최악의 경우를 생각했을 때 M이 백만에 가까우면서 나머지 조건들에 충족이 되지 않으면 do while문을 M^2에 가깝게 돌게 될텐데 저 코드로 제출하니까 4ms밖에 소요가 안되더라구요.

그래서 나머지 조건들에의해 k(m)값이 너무 커지기 전에 찾게 된다던가 뭐 그런거 때문에 시간초과가 발생하지 않는건지 제가 생각하지 못한부분이 어디인지 알려주시면 감사하겠습니다.

(코린이+글솜씨 X ,양해부탁드립니다)