백준 1016 - 제곱 ㄴㄴ 수

문제 설명

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

https://www.acmicpc.net/problem/1016

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 min과 max사이의 수 중 제곱수로 나누어 떨어지지 않는 수의 개수를 세면 된다.

 

해당 문제는 에라토스테네스의 체를 응용하여 풀 수 있다.

문제에서 말한 제곱 ㄴㄴ수는 소수의 조건과 유사하다.

i에 제곱으로 나누어 떨어지지 않는지 확인하면 되기 때문이다.

따라서 소수 판별 알고리즘은 에라토스테네스의 체를 응용하여 개수를 확인하면 된다.

 

 

2부터 시작하여 제곱으로 min을 나눈 몫부터 시작하여 false를 체크해준다.

만약 아직 체크되지 않은 숫자라면 개수를 하나씩 줄여나가면 된다.

auto cnt = Max - Min + 1;

for (long long i = 2; i * i <= Max; i++)
{
	auto n = Min / (i * i);
	if (Min % (i * i)) n++;

	while (n * i * i <= Max)
	{
		if (!dp[n * i * i - Min])
		{
			cnt--;
			dp[n * i * i - Min] = true;
		}

		n++;
	}
}

 

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
#define MAX 987654321

using namespace std;
long long Min, Max;

vector<bool> dp(1000001, false);

int main()
{
	INPUT_OPTIMIZE;
	
	cin >> Min >> Max;
	auto cnt = Max - Min + 1;

	for (long long i = 2; i * i <= Max; i++)
	{
		auto n = Min / (i * i);
		if (Min % (i * i)) n++;

		while (n * i * i <= Max)
		{
			if (!dp[n * i * i - Min])
			{
				cnt--;
				dp[n * i * i - Min] = true;
			}

			n++;
		}
	}

	cout << cnt;

	return 0;
}

---