백준 1016 : 제곱ㄴㄴ수

https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

 

해결 방법 :

• 검사해야 할 구간 배열을 만들고, 2부터 제곱의 배수를 탐색한다.
• 그냥 순차적으로 모든 경우를 탐색하면 당연히 시간초과 발생.
  • 임의의 정수 x의 제곱이 구간 [minimum, maximun]에 처음으로 들어오는 배수를 찾음으로써 연산 횟수를 효과적으로 줄여준다. 
  • (mn // x**2) if mn이 x**2로 나눠지면, else (mn // x** 2) + 1

import sys
input = sys.stdin.readline

def solution(mn, mx):
    candidates = [1] * (mx - mn + 1) 검사 범위
    i = 2
    while i**2 <= mx: # 제곱수 자체가 mx를 넘어가면 확인 할 필요 X
        s = i ** 2 
        j = (mn // s) if mn % s == 0 else (mn // s) + 1 # [mn, mx]구간의 첫번째 배수
        
        while s * j <= mx: # mx 이하까지 검사
            candidates[(s * j) - mn] = 0
            j += 1
        i += 1

    return sum(candidates)

if __name__ == '__main__':
    mn, mx = map(int, input().split())
    result = solution(mn, mx)
    print(result)