[1016] 제곱 ㄴㄴ 수(제곱으로 나누어떨어지지 않는 수)
·
Coding Test/Math
1016번: 제곱 ㄴㄴ 수 어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수 www.acmicpc.net 분석 min ≤ max ≤ min + 1,000,000 : 일반적인 반복문으로 구하면 시간초과 범위 A~B사이 pow(정수 제곱수)로 떨어지는 수 구함 ➔ checkList[ (A/제곱수 ~ B/제곱수)*제곱수-A]=True Fase 개수 출력 1. 제곱수인 4 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 10 j=1 : (4*1)-1=3 (3번 인덱스 제곱수 True) j=2 : (4*2)-1=7 (7번 인덱스 제곱수 T..