[BOJ 1016] 제곱 ㄴㄴ 수

- 문제 요약

 

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다

min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

(1 <= min 1,000,000,000,000 / min <= max <= min + 1,000,000)

 

 

- 알고리즘 정리

 

문제에서 제공한 min의 범위를 확인해보면, 최대 1조까지라는 것을 확인할 수 있습니다.

그러므로 단순히 반복문을 돌기만 하면, 제한시간 내에 문제를 해결할 수 없습니다.

 

min <= max <= min + 1,000,000

문제에서는 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수를 구하라고 했습니다.

위 조건을 보고 다시 문제를 읽어보면, 봐야할 범위는 100만이라는 것을 알 수 있습니다. (눈속임.)

 

그러므로 위 사실과 에라토스테네스의 체를 이용해서 조건에 맞는 수를 구해주면 됩니다.

(수 저장용 배열도 하나 만들어줍니다.)

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 1000001
typedef long long ll;
ll mn,mx,result,arr[MAX];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>mn>>mx;
	for(ll i=2;i*i<=mx;i++){
		ll w=mn/(i*i);
		if(mn%(i*i)){
			w++;	
		}
		while(i*i*w<=mx){
			arr[i*i*w-mn]=1;
			w++;
		}
	}
	for(int i=0;i<=mx-mn;i++){
		if(arr[i]==0){
			result++;
		}
	}
	cout<<result;
}

코드 제출 결과