C++ / 백준 / 1016 / 제곱 ㄴㄴ 수

문제

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

1016번: 제곱 ㄴㄴ 수

문제풀이

정수 min은 굉장히 크다. 모든 정수에 대한 배열을 선언하긴 어려우므로

min과 max 차의 최댓값은 1,000,000인 점을 이용하여 min-min ~ max-min으로 배열을 만들면 된다.

 

1부터 10까지의 수중에서는 제곱 ㄴㄴ수가 1, 2, 3, 5, 6, 7, 10 이렇게 7가지이다.

1부터 10까지의 수중에서 제곱인 수 4, 9와 제곱인 수를 다른 값과 곱한 8을 빼면 제곱ㄴㄴ수가 된다.

 

처음에는 소수끼리의 곱셈을 이용하여 구해보려고 하다 포기했다.

그러다가 에라토스테네스의 체를 이용하여 소수를 구하는 방법을 조금 변형하여 구해보고자 했다.

 

이중 for문을 이용하여 idx는 2부터, max의 제곱근까지 탐색한다.

idx2는 min을 idx^2으로 나눈 값부터 max를 idx^2으로 나눈 값까지 탐색한다.

 

min = 100, max = 1000, idx = 2일때, idx2는 25부터 250까지 탐색한다.

4*25, 4*26, 4*27, ..., 4*250

배열은 0부터 사용할 것이기 때문에, idx^2 * idx2 - min이 배열의 인덱스가 된다.

모든 탐색을 마쳤으면 0부터 answer의 크기만큼 돌면서 true일 때만 개수를 +1 해주면 된다.

 

 

코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

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

	long long idx(0), idx2(0), cnt(0);
	long long min_n(0), max_n(0);	

	cin >> min_n >> max_n;

	vector<bool>answer(max_n - min_n + 1, true);

	for (idx = 2; idx <= sqrt(max_n); ++idx) {
		for (idx2 = min_n / (idx * idx); idx2 <= max_n / (idx * idx); ++idx2) {
			if ((idx * idx * idx2 - min_n) >= 0) {
				answer[idx * idx * idx2 - min_n] = false;
			}
		}
	}

	for (idx = 0; idx < answer.size(); ++idx) {
		if (answer[idx] == true)
			cnt++;
	}

	cout << cnt;
}