백준 온라인 저지의 1016번 제곱 ㄴㄴ수 문제입니다.
[링크] https://www.acmicpc.net/problem/1016
문제 조건과 설명
어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.
Input
첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다.
Output
첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다.
생각한 아이디어
solved.ac 에 Gold 1로 분류되어 있는 문제인데, 에라토스테네스의 체를 활용한다고 해서 풀어보기 시작한 문제입니다. 그런데 괜히 Gold 1이 아닌 것 같습니다. 한 번 생각하면 바로 코드를 짤 수는 있는데 그 한 번의 생각이 정말 힘든 문제였습니다.
이 문제의 가능한 min값의 최대는 1조나 됩니다. max값도 max <= min + 1,000,000 이므로 비슷한 크기입니다.
단순하게 가장 작은 제곱수인 4부터, min 부터 max까지 하나씩 나눠보기에는 반복문의 횟수가 매우 많아질 수 있으므로, 시간 초과가 분명히 날 것입니다.
극단적인 예시로 min이 1조였을 경우에 특히 그러합니다.
정확히 1조일 경우 모두 0으로 이루어진 수이므로 제곱수 4일 때 바로 나누어 떨어질 것입니다.
하지만 바로 다음 수인 1,000,000,000,001 만 해도 소인수분해를 해보면 73 * 137 * 99,990,001 입니다.
이 수를 제일 작은 제곱수인 4부터 하나씩 늘려가면서 (4, 9, 16, 25, 36, …) 나눠보고 나머지를 확인하는 것은 시간 초과가 당연해 보입니다.
그런데 숫자 자체는 크지만, 살펴봐야 할 숫자의 갯수는 그리 크지 않음을 알 수 있습니다. 살펴봐야 할 숫자의 갯수는 많아 봐야 약 100만 개임을 알 수 있습니다. 조건에서 max가 min+1,000,000 보다 작거나 같다고 하였기 때문입니다.
그러므로 모든 수를 살펴볼 수 있는데, 하나씩 일일이 나눠보지 않고 효율적으로 탐색하기 위해서 에라토스테네스의 체를 응용하게 됩니다.
기존의 에라토스테네스의 체는 소수인 것을 찾고, 그것의 배수들에는 모두 소수가 아니라는 표기를 해 놓아서 마치 체처럼 걸러내는 알고리즘이었습니다.
그럼 이 문제는, 처음으로 가장 작은 제곱수인 4로 나누어 떨어지는 숫자를 찾고, 그것에 +4씩 증가시켜 나가는 모든 숫자들에는 모두 제곱수로 나누어 떨어지는 수라는 표기를 해 놓아서 체처럼 걸러내면 되는 것입니다.
그 다음에는 제곱수 9로 처음 나누어 떨어지는 숫자를 찾고, 똑같이 +9씩 증가시켜 나간 모든 숫자들에는 표기를 해 둡니다.
이런 식으로 최댓값보다 작을 때까지 계속 해 나가면 모든 숫자에 대해서 나누어 떨어지는지 살펴보지 않고 skip할 수 있게 해 주므로 시간복잡도를 크게 낮출 수 있습니다.
소스코드와 같이 설명하기 위해, 예를 들어 min = 30이고, max = 100 이었다고 가정해 보겠습니다.
30 이상 100 이하의 숫자 중에서 제곱수 4 = (2*2)로 나누어 떨어지는 가장 작은 숫자를 구할 때는 다음과 같이 하면 됩니다.
- min 값인 30을 (2 * 2)로 나눈 몫을 구한다. = 30 / 4 = 7
- 그 몫에 다시 (2 * 2)를 곱해본다. = 7 * 4 = 28
- 28은 범위에 속하지 않는 숫자이므로, 7에 1을 더한 8에 (2 * 2)를 곱해 보면 32가 된다.
- 따라서 제곱수와 곱하여, 가장 작은 수인 32를 만드는 숫자는 8(!구하려는 수!)이 된다.
- 그러므로 8부터 ( 8 * (2 * 2), 9 * (2 * 2), 10 * (2 * 2), … , 25 * (2 * 2) ) = (32, 36, 40, … , 100) 에는 이미 나누어 떨어지는 수라는 표시를 한다.
모두 검사하면 다시 제곱수 (3 * 3), (4 * 4), …을 가지고 같은 과정을 진행합니다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#define INF 987654321
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
long long min, max;
cin >> min >> max;
long long ans = max - min + 1; // 살펴봐야 하는 숫자의 갯수
vector<bool> sieve(max - min + 1, false);
long long i = 2; // 처음 제곱수는 2*2 이므로 i=2로 초기화
// 제곱수가 max보다 작거나 같을 때만 진행
while (i * i <= max) {
// 처음으로 i*i로 나누어떨어지는 수를 찾아야 한다.
// 위에서 설명한 !구하려는 수! 를 구하기 위한 과정
long long sNum = min / (i * i);
if (min % (i * i) != 0)
sNum += 1;
// (!구하려는 수!는 1씩 증가시키고) * 제곱수 인 모든 인덱스에 true 표시하기
while (sNum * (i * i) <= max) {
if (sieve[sNum * (i * i) - min] == false) {
sieve[sNum * (i * i) - min] = true;
ans -= 1;
// true로 표시하는 과정은 모두 나누어 떨어지는 숫자이므로,
// 살펴봐야 하는 숫자의 총 갯수에서 1개씩 빼주면 된다.
}
sNum += 1;
}
i += 1; // 다음 제곱수로 넘어가기 위해 i를 1 증가시키기
}
cout << ans; // 제곱수로 나누어 떨어지지 않는 갯수가 된다.
return 0;
}