백준 1016번 제곱 ㄴㄴ 수

문제 링크 : https://www.acmicpc.net/problem/1016

문제 풀이

(0) 생각

1보다 큰 제곱 수로 나누어지는 X 를 '제곱 ㅇㅇ 수' 라고 합시다.

저는 min ~ max 사이의 수들 중 제곱 ㅇㅇ 수를 세줄 것입니다.

정답은 min~max 사이 총 개수 -  제곱 ㅇㅇ 수 일 것입니다.

(1) 코드 15~34

 2의 제곱부터 차례로 max 전 까지 제곱 수를 모두 생각해줍니다.

 각 제곱 수의 배수들이 min~max 사이에 얼마나 들어가는지 세줍니다.

 이때 중복을 피하기 위해 배열을 하나 잡아 중복 체크를 해줍니다.

(2) 코드 25

 숫자 범위가 10^12 입니다. 굉장히 큽니다.

 그러나 min ~ max 사이 개수는 최대 10^6 입니다.

 따라서 각 제곱 ㅇㅇ 수 의 중복 체크를 해당 수로 하지 않고, 

 해당 수 - min 값 으로 해주었습니다.

(3) 시간...

 사실 2의 제곱 ~ max 전 까지 10^6 개입니다. ( 10^6 * 10^6 = 10^12 )

 각 제곱 수 마다 적당히 추가 처리가 필요합니다...

 사실 그냥 돌아갈 것 같아서 돌려보니 돌아갔습니다... 죄송합니다 ㅠ