한 소수의 제곱 X를 가지고 a에서 b 구간 사이에 제곱수가 있는지를 판별할때

a부터 b까지 하나하나 전부 볼수도있지만

a와 b사이의 처음나오는 X의 제곱수부터 시작해서 X단위로 점프한다면 시간초과를 줄일 수 있을거에요

문제는 처음나오는 X의 제곱수를 구하는 건데 이걸 한번에 구해야지만 시간초과 탈출이 가능해요

https://algospot.com/wiki/read/%EC%95%8C%EA%B3%A0%...

http://en.wikipedia.org/wiki/M%C3%B6bius_inversion...

http://en.wikipedia.org/wiki/M%C3%B6bius_function

이 세 개의 링크가 도움이 되었으면 좋겠네요.

소수의 제곱 X가 무슨말씀인지 이해가 안가네요 왜 소수의 제곱을 다루는건지요;;?

@inmypace

소수의 제곱만 다루는게 모든 수의 제곱을 다루는 것보다 시간이 훨씬 적어지기 때문입니다. 소수만 다뤄도 나눠지는 여부 판별하는 게 전부 커버가 되고요