백준 1016번 제곱 ㄴㄴ 수

문제

어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다.

아이디어는 같지만 1조의 범위를 모두 탐색하는 것에서 시간초과

그럴 필요가 없다 min과 max의 차이는 100만이므로 그 안에서의 제곱 ㄴㄴ 수는

최대 100만개이기 때문

 

따라서 i는 2부터 i제곱이 max보다 작은 수에 대해서 

min을 i제곱으로 나눈 몫 부터 (몫 x i 제곱 이상일 것이므로 min이) , 이 때 만약 나머지가 존재한다면 

min이 해당 몫과 제곱수를 곱한것 이상범위란 뜻이므로 몫 값을 1 늘려준다.

몫을 1씩 늘려가면서 max 이하인 것에 체크 

그리고 0부터 (0은 min의 값을 의미)

max -min 까지 탐색하면서 체크 안된 것 만큼 카운트

 

#include <iostream> 
using namespace std;

bool isSqr[1000001];

int main() {
	long long min, max;
	cin >> min >> max;

	for (long long i = 2; i * i <= max; i++) {
		long long tmp = i * i;
		long long start = min / tmp;
		if (start * tmp != min) start++;
		for (long long j = start; tmp * j <= max; j++) {
			isSqr[tmp * j - min] = true;
		}
	}
	int count = 0;
	for (int i = 0; i <= max - min ; i++) {
		if (!isSqr[i]) count++;
	}
	cout << count << endl;

	return 0;
}