개요

오늘의 문제는 1016.제곱 ㄴㄴ 수를 푼 겸 원리 자체가 비슷해보이는 1557.제곱 ㄴㄴ 입니다.

공교롭게도 문제 번호가 참 낯이 익습니다. 

 

참고로 전 이 문제를 풀고 플레티넘을 찍었습니다.

 

 

 

 

문제

어떤수 N이 1이 아닌 제곱수로 나누어지지 않을 때, 이 수를 제곱ㄴㄴ수라고 한다. 제곱수는 4, 9, 16, 25와 같은 것이고, 제곱ㄴㄴ수는 1, 2, 3, 5, 6, 7, 10, 11, 13, ...과 같은 수이다.

K가 주어졌을 때, K번째 제곱ㄴㄴ수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 K가 주어진다. \((1 ≤ K ≤ 1,000,000,000)\)

 

출력

첫째 줄에 K번째 제곱ㄴㄴ수를 출력한다.

 

테스트 케이스

입력 출력
13 19

 

 

 

 

풀이

아이디어 정리

제곱 ㄴㄴ 수 = 제곱인수가 없는 정수 = Square-free Integer = 무승수(無乘數)

편의상 제곱 ㄴㄴ 수는 이 글에서 무승수라고 칭하겠습니다. 너무 길어서 그래요.

 

일단 k번째 무승수를 구하기 위해서 단순 브루트포스로 접근을 해봅시다.

1씩 증가하는 변수 \(a\)와 등장한 무승수가 몇번째인지를 담을 \(b\)라는 변수를 하나 둡니다. 그리고 \(a\)를 1부터 1씩 증가 시켜가며 \(a\)가 무승수인지 판단합니다. 그리고 \(a\)가 무승수라면 \(b\)를 1 증가 시킵니다.

 

이 과정을 \(b\)가 \(k\)와 같아질때까지 반복한 뒤에 \(b\)가 \(k\)와 같아진다면 그 때의 \(a\) 값이 \(k\)번째 무승수입니다.

 

하지만 딱봐도 말도 안되는 연산량을 요하죠. \(k\)의 값은 1,000,000,000까지 치솟고 시간 복잡도는 무승수 판별에 \(O(\sqrt{k})\), 그걸 \(k\)번 연산하니 최종 시간 복잡도는 \(O(k \times \sqrt{k}) = O(k^{\frac{3}{2}})\)로 그냥 미쳐 돌아갑니다.

 

딱봐도 브루트포스의 방식으론 불가능합니다.

그러니 다른 아이디어를 찾아봐야겠죠.

 

 

특정한 자연수 \(a\)를 넣으면 1부터 \(a\)까지 등장한 무승수가 몇개인지 알려주는 함수 \(f(a)\)를 둬봅시다.

 

이 \(f(a)\)의 값으로 \(k\)번째 무승수를 알아낼 수 있습니다. \(f(a)\)가 일전에 적어뒀던 \(b\)의 역할과 일치하니, 단순하게 \(f(a)\)가 \(k\)인지 확인해서 \(f(a)\)가 \(k\)와 같다면 \(a\)가 바로 \(k\)번째 무승수라는 뜻이겠죠. 

 

하지만 겨우 그정도 조건으론 \(k\)번째 무승수와 비슷한 값 정도만 확인할 수 있습니다. 예를 들어봅시다.

$$f(1) = 1$$

$$f(2) = 2$$

$$f(3) = 3$$

$$f(4) = 3$$

$$f(5) = 4$$

 

이와 같이 \(a\)가 3일때와 4일때 전부 3이라는 값이 나오는데 3은 무승수, 4는 무승수가 아닙니다. 그러니 저희는 \(f(a)\)가 처음으로 k가 되는 \(a\)의 값이 \(k\)번째 무승수라는 것을 알 수 있습니다.

 

물론 이것도 1부터 \(k\)까지 증가시키면서 하나하나 확인하기엔 \(O(k)\)의 시간 복잡도가 발생하니 \(f(1)\)를 left로 \(2k\)를 right로 두고 이분 탐색을 진행할겁니다.

왜 \(f(1,000,000,000)\)이 아니라 \(2k\)냐? 그냥 넉넉하게 잡고 하기 위해섭니다, \(k\)번째 무승수는 당연하게도 \(k\)보단 클것이고 그 증가폭에 따라 추측을 해보면 \(2k\)보단 작다는걸 알 수 있습니다. 그래서 그냥 \(2k\)로 잡는겁니다. 

 

대충 이런 느낌이에요.

left = 1, right = 2k
while (left < right):
mid = (left + right) // 2
if f(mid) < k: left = mid + 1
else: right = mid

이분 탐색이 끝났을 때의 left값이 최종 답안입니다.  

 

 

그러니 일단 1016.제곱 ㄴㄴ 수의 아이디어를 일부 견인해봅시다. 이 문제는 어떠한 범위 사이에 무승수가 몇개인지 구하는 문제에요.

소수 판정은 아니지만 이곳 저곳에서 많이 쓰이는 에라토스테네스의 체를 사용하여 제곱수의 배수를 싹 걸러내는 방법으로 풀었었죠.

이건 그 소스코드입니다.

long long min, max;
cin >> min >> max;

long long n = max - min + 1;

vector<bool> square_free(n, false);
long long  answer = n; // 일단 모두 제곱ㄴㄴ수라고 단정
for (long long i = 2; i * i <= max; i++)
{
	long long square = i * i;
	long long start = (min + square - 1) / square * square; // 범위 설정
	for (long long j = start; j <= max; j += square) // 제곱수의 배수 순회
	{
		if (!square_free[j - min]) // 제곱ㄴㄴ수가 아닌데 맞다고 체킹 되어 있을 경우
		{
			square_free[j - min] = true; // 제곱ㄴㄴ수가 아니라고 체킹 후에
			answer--; // 카운트 감소
		}
	}
}

cout << answer;

 

이 코드를 그대로 갖다 써서 min을 1로, max를 \(2k\) 정도로 고정할 경우 충분히 풀 수 있습니다.

하지만? \(k\)는 1,000,000,000까지 올라가죠? 1,000,000,000보다 더 큰 크기의 vector를 사용할 수는 없겠죠.

 

그래서 숫자를 세는 방법을 바꿔야합니다. 어떻게 할거냐?

1부터 \(k\)까지의 수는 총 \(k\)개죠? 여기서 적당히 값을 빼줄거에요.

일단 4의 배수를 모두 뺍니다. 1부터 k까지 4의 배수의 개수는 \((k \div 4)\)개죠. 그리고 9의 배수, 16의 배수... 순차적으로 뺍니다.

 

단순하게 생각하면 \(f(a)\)는 다음과 같이 표현할 수 있어 보입니다.

$$f(a) = a -  (a \div 4) - (a \div 9) - (a \div 16) \cdots$$

 

하지만 당연히 아니죠! 그렇게 쉽지 않습니다. 이 문제가 다이아 5인 이유가 있어요.



이 풀이는 공통 배수를 간과했습니다. 예를 들어 36이라는 수를 봅시다.

이 수는 4로도 나누어지며 9로도 나누어집니다. 하지만 위에서 4의 배수로 36을 뺐는데 9의 배수로 36을 또 빼고 있어요.

 

이걸 해결하기 위해 사용하는 것이 포함-배제의 원리입니다. 

 

 

포함-배제의 원리

포함-배제의 원리는 간단하게 말해서 특정 집합에서 그냥 포함과 배제를 계속해서 반복하는거에요. 그게 끝입니다.

무엇을 포함하고 무엇을 배제할것이냐가 관건이죠.

 

단계별로 접근해봅시다. 결과 값은 \(R\)이라고 선언 해두죠.

 

 

  1. [포함]| 첫 단계입니다. 1부터 \(2k\)번째 까지의 모든 수를 포함합니다.
      \(R = 2k\)

  2. [배제] | 가장 기본적인 제곱 수들의 배수를 배제합니다. 여기서 기본적인 제곱 수란 소수의 제곱수 입니다.
      \((R = R \div 2^2 -  R \div 3^2 - R \div 5^2 - R \div 7^2 \cdots)\)
      소수의 제곱수 만을 배제하는 이유는 소수의 제곱수 만으로 모든 제곱 수의 배수를 배제할 수 있기 때문입니다.

  3. [포함] | 중복해서 빼내진 수를 다시 포함합니다.
      36은 4의 배수이므로  \(R \div 2^2\)에서 이미 고려되었습니다. 동시에, 36은 9의 배수이므로 \(R \div 3^2\)에서 또한 고려되었습니다. 즉 36은 두 번 빠졌기에 다시 포함 시켜야합니다.
      하지만 이러한 수를 하나하나 일일이 알아낼 수 없기에 규칙을 찾아내야합니다. 규칙은 간단하죠. 서로 다른 두 소수 \(p, q\)가 있을 때 \((p \times q)^2\) 형태의 수가 중복해서 빼내진 수라는 것을 알 수 있습니다.

  4. [배제] | 너무 많이 포함된 수를 다시 배제합니다.
      900이라는 수를 봅시다. \(900 = 2^2 \times 3^2 \times 5^2\)
      첫번째 배제에서 900은 4, 9, 25의 배수로써 3번 배제되었습니다. 동시에, 이전 단계에서 900은 \(2^2 \times 3^2 = 36\), \(2^2 \times 5^2 = 100\), \(3^2 \times 5^2 = 225\)의 배수라서 3번 포함되었습니다. 이런 수를 다시 배제합니다.

 

이걸 이제 반복하면 돼요. 근데 너무 복잡해보이고 포함 배제를 총 몇번까지 해야할지 명확히 감이 잘 안잡히죠. 그래서 사용하는 게 뫼비우스 함수라는 겁니다.

 

 

뫼비우스 함수

뫼비우스 함수는 어떠한 정수의 약수로 소수의 제곱이 있는지 보고, 알아서 -1, 1, 0으로 정리해주는 깔끔한 도구입니다.

 

뫼비우스 함수는 \(\mu\) 기호로 나타내며, \(\mu(n) (단, n은 정수)\)에 대해 다음과 같이 정의됩니다.

$$\mu(1) = 1$$

\(n\)의 약수 중 하나가 소수의 제곱 수 일경우 \(\mu(n) = 0\)

\(n\)의 소수 인수 개수가 짝수개면 \(\mu(n) = 1\)

\(n\)의 소수 인수 개수가 홀수개면 \(\mu(n) = -1\)

 

이걸 통해 \(\mu(n)\)이 0일땐 무승수이고 1혹은 -1일땐 무승수가 아니라는 걸 알 수 있습니다. 

 

그리고 위에서 봤던 포함-배제의 순서를 보면 짝수일때 포함, 홀수일때 배제를 한다는 사실을 알 수 있죠. 그러니 이 뫼비우스 함수를 통해서 포함-배제를 가릴 수 있는겁니다.

 

 

그러면 대충 어떻게 함수를 짜야할지 보이죠? 대충... 이런 꼴인데요.

$$f(n) = \sum_{i=1}^{\lfloor\sqrt{n}\rfloor} \mu(i) \left\lfloor \frac{n}{i^2} \right\rfloor$$

 

솔직히 너무 몬생겼으니까 간단한 코드로 대체합시다.

int f(int n)
{
	int result = 0; // 최종 값을 담을 변수
    for(int i = 1; i * i <= n; i++)
    {
    	result += mobius(i) * (n / (i * i)); // n까지의 수에서 i^2의 배수를 포함 혹은 배제
    }
    return result;
}

 

뫼비우스의 함수의 반환값이 0일경우, 그 수는 무승수가 아니기 때문에 최종 값에 변화를 줄 수 없습니다.

-1일 경우 인수의 개수가 홀수이기 때문에 배제(뺄셈)를 진행 합니다. 

1일 경우 인수의 개수가 짝수이기 때문에 포함(덧셈)을 진행 합니다.

 

이정도면 쉽죠?

이제 대충 아이디어 자체는 다 떠올린 것 같으니 코드로 구현해봅시다.

 

 

코드로 풀기

일단 입력을 받아줍시다.

long long k;
cin >> k;

 

 

그리고 이제 모든 배열의 limit을 만들어줄거에요. 이 limit은 생각보다 난해할 수 있습니다. 제가 그랬거든요.

int limit = sqrt(2 * k) + 1;

 

일단 이 limit은 소수 판정 배열에서도, 뫼비우스 함수를 캐싱해두는 배열에서도 사용합니다.

(뫼비우스 함수를 일일히 모든 수에서 계산하는건 굉장히 큰 오버헤드기 때문에 한번에 계산해두고 갖다 쓸겁니다. DP를 생각하면 이해하기 편해요.)

 

 

아무튼 limit을 두는 이유는 \(2k\)까지 모든 뫼비우스 함수의 값을 구할 필요는 없기 때문입니다. 또한, 소수 판정도 마찬가지죠. 위에서 적었던 코드를 볼까요?

 

 

보면 \(i^2 \leq n\)이라는 조건 식이 눈에 띄죠. 이건 \(i\)가 \(\sqrt{n}\)보다 작을때까지만 한다는 뜻이에요. 그러면? mobius 함수를 미리 캐싱해둘때 굳이 \(2k\)까지 캐싱을 할 필요가 없겠죠? 그래서 limit을 \(\sqrt{2k} + 1\)로 두는겁니다.

 

 

뭐 아무튼, 이제 늘 먹던 소수판정을 해줍니다.  이건 이제 에라토스테네스의 체라서 이런 문제 풀어보면 도움이 잘 됩니다.

vector<bool> isPrime(limit, true); // 소수판단
isPrime[0] = isPrime[1] = false;

for (int i = 2; i * i < limit; i++)
{
	if (isPrime[i])
	{
		for (int j = i * i; j < limit; j += i)
		{
			isPrime[j] = false;
		}
	}
}

 

 

그리고 이제 뫼비우스 함수의 반환값을 저장할 배열을 만들어줄겁니다. 초기값은 1로 고정합니다. 

vector<int> mobius(limit + 1, 1); // 뫼비우스 함수의 반환값 저장

 

 

 

일단 코드를 자르기 애매해서 그냥 통으로 가져왔습니다.

for (int i = 2; i < limit; i++)
{
	if (isPrime[i]) // 만약 소수라면
	{
		for (int j = i; j < limit; j += i) // i의 배수들을 쭉 돌면서 배수를 반전 시킴. 그러니까 이제 기본값이 1이니 인수가 하나 늘었다고 알려주는거임.
		{
			mobius[j] *= -1;
		}

		long long sqr = i * i;
		if (sqr < k * 2) // 그리고 i^2이 범위를 넘지 않았다면
		{
			for (long long j = sqr; j < limit; j += sqr) // i^2의 배수를 순회하며 0으로 바꿈.
			{
				mobius[j] = 0;
			}
		}
	}
}

 

 

간단하게 설명해보자면,
반복문을 돌면서 limit까지 값을 쭉 올려줍니다. 그리고 소수일 경우 또 다른 반복문에 진입합니다.

그리고 i의 배수들을 쭉 돌면서 부호를 반전시킵니다.
이걸 왜 하느냐? i는 소수이고 뫼비우스 함수는 소인수의 개수를 세서 -1 혹은 1을 뱉어줘야 하죠. 그러니 소인수가 하나씩 발견될 때 마다 -1을 곱해서 뫼비우스 함수에게 인수가 하나 늘었다고 알려주는겁니다.

그 뒤에 무승수 판단을 시작합니다.
\(i\)는 소수이니 \(i^2\)의 배수들은 무승수가 아니죠. 그러니 뫼비우스 함수의 값을 0으로 바꿔줍니다.

여기까지 했다면 이제 뫼비우스 함수 값 저장은 끝입니다.


그리고 드디어 지금까지 입이 닳도록 말했던 함수 \(f(n)\)을 구현해보도록 할게요.

long long getSquareFreeCount(vector<int>& mobius, long long n)

 

 

일단 이런식으로 함수를 만들어줍니다.

그 뒤에 위에서 말했던 그 코드를 그냥 고대로 옮겨줍니다.

long long res = 0;
for (long long i = 1; i * i <= n; i++)
{
	if (mobius[i] == 0)
		continue;
	res += mobius[i] * (n / (i * i));
}
return res;

 

뫼비우스 함수가 0일때 continue해주는건 정말 간단한 최적화라서 안해도 무방합니다만 그냥 하는게 좋습니다.

 

 

아무튼 이렇게 함수 \(f(n)\)이 그냥 뚝딱 나왔어요. 이제 남은건 이분 탐색 뿐입니다.

 

다시 메인으로와서, 앞서 말했듯 left는 1, right는 \(2k\)로 둬줍니다.

long long left = 1;
long long right = k * 2;

 

 

그리고 이분 탐색을 이런식으로 해주고 탈출이 됐을때 left의 값을 출력해준다면 문제 끝입니다.

while (left < right)
{
	long long mid = (left + right) / 2;
	long long cnt = getSquareFreeCount(mobius, mid);
	if (cnt < k)
	{
		left = mid + 1;
	}
	else
	{
		right = mid;
	}
}

cout << left;

 

 

 

 

 

마치는 말

뭔가 재밌어보여서 골랐던 문제였는데 슬슬 제가 프로그래밍을 하고 있는지 수학을 하고 있는지 헷갈리네요.

그래도 이거 풀고 정확히 12점 받고서 플레티넘 5 0점에 올라갔기에 만족합니다.

 

 

 

코드 전문

#include <bits/stdc++.h>
using namespace std;

#define FAST_PRINT std::ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define BEGIN_TO_END(vec) vec.begin(), vec.end()
#define MEMSET(arr, i) memset(arr, i, sizeof(arr))

long long getSquareFreeCount(vector<int>& mobius, long long n)
{
	long long res = 0;
	for (long long i = 1; i * i <= n; i++)
	{
		if (mobius[i] == 0)
			continue;
		res += mobius[i] * (n / (i * i));
	}
	return res;
}

int main()
{
	FAST_PRINT;

	long long k;
	cin >> k;

	int limit = sqrt(2 * k) + 1;
	vector<bool> isPrime(limit, true); // 소수판단
	isPrime[0] = isPrime[1] = false;

	for (int i = 2; i * i < limit; i++)
	{
		if (isPrime[i])
		{
			for (int j = i * i; j < limit; j += i)
			{
				isPrime[j] = false;
			}
		}
	}

	vector<int> mobius(limit + 1, 1); // 뫼비우스 함수의 반환값 저장

	for (int i = 2; i < limit; i++)
	{
		if (isPrime[i]) // 만약 소수라면
		{
			for (int j = i; j < limit; j += i) // i의 배수들을 쭉 돌면서 배수를 반전 시킴. 그러니까 이제 기본값이 1이니 인수가 하나 늘었다고 알려주는거임.
			{
				mobius[j] *= -1;
			}

			long long sqr = i * i;
			if (sqr < k * 2) // 그리고 i^2이 범위를 넘지 않았다면
			{
				for (long long j = sqr; j < limit; j += sqr) // i^2의 배수를 순회하며 0으로 바꿈.
				{
					mobius[j] = 0;
				}
			}
		}
	}


	long long left = 1;
	long long right = k * 2;

	while (left < right)
	{
		long long mid = (left + right) / 2;
		long long cnt = getSquareFreeCount(mobius, mid);
		if (cnt < k)
		{
			left = mid + 1;
		}
		else
		{
			right = mid;
		}
	}

	cout << left;
}

'알고리즘 > C++' 카테고리의 다른 글

[백준] | C++ | 1086. 박성원 (Bit DP, 나머지 연산)  (1) 2025.05.06
[백준] | C++ | 10942. 펠린드롬? (Top-down DP)  (2) 2025.04.20
[백준] | C++ | 4991. 로봇 청소기 (TSP, 비트마스킹)  (1) 2025.04.19
[백준] | C++ | 7453. 합이 0인 네 정수  (2) 2025.04.11
[백준] | C++ | 17626. Four Squares  (0) 2025.04.05

티스토리툴바