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

문제

[C++] 백준 1016: 제곱 ㄴㄴ 수 GOLD 1
https://www.acmicpc.net/problem/1016

 

---

 

접근 방법

구간 [Min,Max][Min, Max][Min,Max] 안에 있는 수들 중에서 어떤 소수 p에 대해 p^2로 나누어떨어지지 않는 수(= 제곱 ㄴㄴ 수)의 개수를 세는 문제이다.

 

즉, 구간 안에서 2^2, 3^2, 5^2, ... 이런 제곱수들로 나누어 떨어지는 수는 다 제외하고 남는 숫자의 개수를 세면 된다.

 

하지만 여기서 중요한 제약은 

이와 같기 때문에,

• 단순히 1 ~ Max까지 배열 만들어서 에라토스테네스 같은 걸 돌리거나
• 매 수마다 제곱수 나눠보는 방식으로는 시간/메모리 초과가 난다.

그래서 이 문제는 “전체를 다 보는 게 아니라, [Min, Max] 구간만 슬라이딩해서 체크하는 방식”을 써야 하고, 그게 바로 세그먼트 방식의 마킹 아이디어다.

 

상세 아이디어

1. 구간을 인덱스로 옮기기

우리가 보고 싶은 실제 숫자: Min ~ Max

이걸 배열 인덱스로 옮기면: 숫자 k (Min ≤ k ≤ Max) 에 대응되는 인덱스는 👉 k - Min

vector<bool> check(Max - Min + 1, false);

이렇게 잡아두면

• check[0] → 실제 숫자 Min
• check[1] → 실제 숫자 Min + 1
• ...
• check[i] → 실제 숫자 Min + i

를 의미한다.

 

여기서 check[i] == true 라는 건 “이 숫자는 어떤 제곱수로 나누어떨어지는 숫자다”라는 의미로 쓰고,
끝까지 남은 false가 제곱 ㄴㄴ 수가 된다.

 

2. 어떤 제곱수들까지 보면 될까?

제곱수는 i * i 꼴.
우리가 보는 범위는 Min ~ Max 이니까, 최소한 i * i ≤ Max까지만 보면 됨.

for (long long i = 2; i * i <= Max; i++)
{
    long long pow = i * i;
    ...
}

여기서 pow는 현재 보고 있는 제곱수 i^2

이 pow로 나누어떨어지는 수들은 전부: j * pow (j는 정수) 꼴이고,

그중 Min ≤ j * pow ≤ Max 를 만족하는 것만 골라서 지워주면 된다.

 

3. 시작점(start) 계산하기

우리는 j * pow가 구간 안에 들어오는 처음 위치부터 마킹을 시작해야 한다.

수식으로 쓰면:

j * pow ≥ Min
j ≥ Min / pow

 

따라서 j의 최소값은 j = ceil(Min / pow) 이다.

 

이를 코드로 구현한 게 바로 이 부분:

long long start = (Min / pow);

if (Min % pow != 0)
    start++;

• Min / pow → 정수 나눗셈이라 floor(Min / pow) 값이 나오고,
• 나머지가 있으면(Min % pow != 0) → 올림을 해줘야 하니까 start++

그래서 결국 start는 start = ceil(Min / pow)와 동일한 역할을 한다.

 

이제 j = start부터 시작해서:

for (long long j = start; j * pow <= Max; j++)
	check[(int)((j * pow) - Min)] = true;

이렇게 하면 pow로 나누어 떨어지는 모든 수들이 check 배열에서 true가 된다.

 

4. 마지막으로 남은 false 개수 세기

여기까지 마킹하고 나면:

• check[i] == true → 어떤 제곱수로 나누어 떨어짐 → 제거
• check[i] == false → 어떤 제곱수로도 나누어떨어지지 않음 → 제곱 ㄴㄴ 수

이므로 단순히 한 번 쭉 돌면서 false의 개수를 세주면 끝:

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

 

구현 시 주의할 점

• Min, Max, i*i 계산은 반드시 long long을 사용해야 한다.
• 구간 인덱스는 항상 (값 - Min) 형태로 접근해야 한다.
• 시작 배수는 단순 나눗셈이 아니라 올림(ceil) 개념으로 계산해야 한다.

 

---

 

코드

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

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

	long long Min = 0, Max = 0;
	cin >> Min >> Max;

	vector<bool> check(Max - Min + 1, false);
	for (long long i = 2; i * i <= Max; i++)
	{
		long long pow = i * i;
		long long start = (Min / pow);

		if (Min % pow != 0)
			start++;

		for (long long j = start; j * pow <= Max; j++)
			check[(int)((j * pow) - Min)] = true;
	}
	int cnt = 0;
	for (int i = 0; i < check.size(); i++)
	{
		if (check[i] == false)
			cnt++;
	}
	cout << cnt;
}