안녕하세요 선생님들. 풀이에서 시간복잡도를 계산했을 때 제한시간내로 연산이 안되는데 왜 이게 되는지 궁금해서 질문드립니다.

저는 이 문제를 브루트포스로 풀었을 때(아무런 최적화 없이 모든 숫자에 대해 1부터 나눠보는 풀이로) 시간복잡도가 O(kn)이라고 계산했습니다.

즉, 최대 300 * 10⁶ = 3*10⁸ 정도의 연산을 하게 된다고 생각했습니다(추가적으로 테스트케이스도 나눠져 있습니다..)

그래서 for loop 연산 1억번당 1초라고 가정했을 때, 이 풀이가 안된다고 판단하고 다른 것들을 고민해봤는데 도저히 답이 안나와서 다른 분들의 풀이를 참고하니 다들 그냥 브루트포스로 푸셨더군요.

어떻게 이게 가능한가 싶어 테스트를 해봤습니다.

제 코드를 보면 100,000을 넘어가는 나누기를 처리하는 순간 while문을 탈출하도록 처리했습니다.

정적으로 1,001, 10,001, 100,001, 1,000,001 4가지로 나눠 테스트했는데 100001부터 답처리가 되더군요(이러면 최대 3*10⁷ 이므로 어찌저찌 가능)

혹시 이게 제가 모르는 간단한 정수론이 존재하는걸까요? 아니면 순수하게 테스트케이스가 부족한건가요?

아니면 for loop 1억번 연산시에 걸리는 시간이 1초라고 가정하는 것이 틀린걸까요?

알려주시면 감사하겠습니다..

아래 코드 제출 번호는 72639014 번 입니다.