[백준] 1016번: 제곱 ㄴㄴ 수 [C++]

 

알고리즘 분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체

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

1016번: 제곱 ㄴㄴ 수

 

 

 

 

 

【 풀이 】

 

에라토스테네스의 체를 활용하여 해결하는 문제이다.

 

처음엔 2부터 하나씩 제곱해 가면서 4, 9, 16, 25, 36.. 등의  제곱수들로 나누어 떨어지는 지를 체크해서 하나씩 제거해 가는 아이디어를 떠올렸다.

하지만 가능한 min 값이 0부터 1,000,000,000,000, 즉 1조나 된다.

최악의 예시로 min이 1조가 될 경우 for문의 반복 횟수가 굉장히 많아지므로 당연히 시간초과가 날 수밖에 없다.

 

그런데 제한을 보면 min ≤ max ≤ min + 1,000,000 이라고 했으므로

막상 살펴봐야 할 숫자는 최대 100만 개 밖에 되지 않는다.

이는 제곱수로 나눠지는 수를 처음부터 제거하는 것이 아닌, min 부터 max 까지만 제거하면 된다는 것이다.

즉, 범위 내 제일 작은 제곱수의 배수부터 시작해서 제곱수의 배수들을 모두 제거하면 된다.

 

예를 들어 min = 50, max = 100 이라고 하자.

풀이 과정은 다음과 같다.

 

1. 첫 제곱수인 (2 * 2) 부터 시작해서 min을 나눈 몫을 구한다. 50 / (2 * 2) = 50 / 4 = 12
2. 12 * (2 * 2) = 48 이므로 min 범위보다 작다는 것을 알 수 있다.
3. min 범위보다 작다면 몫에 +1 을 한다. 
4. 그 몫과 제곱수를 다시 곱하면 범위 내 최소 제곱수의 배수가 된다. 13 * 4 = 52
5. 13 * (2 * 2) 부터 max 까지 제곱수의 배수들을 모두 제거한다.
6. 13 * (2 * 2) = 52 제거, 14 * (2 * 2) = 56 제거, 15 * (2 * 2) = 60 제거, ... 25 * (2 * 2) = 100 제거
7. max 범위까지 완료했다면 (3 * 3), (4 * 4), (5 * 5),... 다음 제곱수들도 1번부터 진행

 

 

【 코드 】

#include<iostream>
using namespace std;

// 제곱 ㄴㄴ 수를 체크하는 배열
int isSqr[1000021];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	long long min, max;
	cin >> min >> max;

	// 정답으로 출력할 제곱 ㄴㄴ수의 개수이다.
    	// 제곱 ㄴㄴ 수를 체크하면서 하나씩 줄여나갈 것
	long long cnt = max - min + 1;

	for (long long i = 2; i * i <= max; i++) {
		long long ret = min / (i * i);	// 몫
		if (min % (i * i) != 0)		// 몫이 min 보다 작을 경우
			ret++;
            	
		while (ret * (i * i) <= max) 	// max 범위까지 제곱 ㄴㄴ 수 체크. 위 과정에서 6번에 해당함
		{	
			if (isSqr[ret * (i * i) - min] == false) {
				isSqr[ret * (i * i) - min] = true;
				cnt--;
			}
			ret++;
		}
	}

	cout << cnt;

	return 0;
}