[백준] 제곱 ㄴㄴ 수 c++

제곱 ㄴㄴ 수 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

69723

13993

9899

22.262%

문제

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

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

---

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	long min, max;

	cin >> min >> max;

	//min과 max의 길이만큼 vector를 설정
	vector<bool> check(max - min + 1);

	int count = 0;

	//첫번째 for문은 제곱수만큼 돌아가도록 설정.
	for (long i = 2; i * i <= max; i++)
	{
		//현재 제곱수
		long pow = i * i;

		//제곱수가 처음 등장하는 위치를 min/pow로 가져온다.
		//다만, 처음에 등장하는 값이 배수가 아닐 수도 있기 떄문에 아니라면 +1을 해 맞춘다.
		long startIndex = min / pow;

		if (min % pow != 0)
		{
			startIndex++;
		}

		for (long j = startIndex; pow * j <= max; j++)
		{
			//현재 위치 계산. 배열은 0 부터시작하기에 -min을 해줘야 제대로 된 위치를 가져온다.
			int index = (int)(pow * j) - min;

			check[index] = true;
		}
	}

	for (int i = 0; i < check.size(); i++)
	{
		if (false == check[i])
		{
			count++;
		}
	}

	cout << count;
}

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