1016 제곱ㄴㄴ수

드디어 해결하지 못했던 문제를 풀었다! 범위가 커서, 에라토스테네스의 체를 이용하여 계산하려고 하였는데

이경우 중복되는 숫자(예를들어서 4 9 는 36이 중복된다든지....등등) 를 고려해야 하기에

소수 만을 이용하여 배수가 되는 수를 제거해주는 꼴로 계산하였다!

범위의 경우 HINT가 될 수 있는것은 min ~ max 차이가 1,000,000 이라는것! (시간초과가 나려면 1억정도는 되어야 시간초과!)

따라서 기존 에라토스테네스 식에서,

 1) 범위를 max까지 

 2) 방문한것에 대해서는 visit 배열을 통해 확인! 이미 제곱의 배수가 되는 수에 대해서는 더이상 고려하지 않을것!!

 3) 처음 min의 숫자가 제곱인 수에 포함되는지 예외처리!

 4) 방문하지 않은, 즉 제곱 ㄴㄴ수에 대해서 bool 변수를 통해 count 개수 세기!

(이러한 규칙성에 대해서는 제곱ㄴㄴ수 관련 많은 블로그에서 공통으로 알 수 있다. 

 더 효율적인 방법을 찾아보았으나, 이게 최선인것같다!)

<소스코드>

#include <cstdio>

bool visit[1300001];
long long cnt,minn,maxx,start;

int main() {

	scanf("%lld%lld", &minn, &maxx);

	for (long long i = 2; i*i <= maxx; i++) {

		long long two = i*i;

		start = minn / two;

		if (minn % two != 0) start++;

		for (long long j = start; two*j <= maxx; j++) {

			if (!visit[two*j - minn]) visit[two*j - minn] = true;

		}

	}

	for (long long i = minn; i <= maxx; i++) {

		if (!visit[i-minn]) cnt++;

	}

	printf("%lld\n", cnt);

	return 0;

}