BOJ 1557 제곱 ㄴㄴ / BOJ 8464 Non-Squarefree Numbers

난이도 : Solved.ac 기준 다이아 5

사실상 거의 같은 문제인 1557과 8464는 둘 모두 Square Free Number의 개수에 관한 문제이다. 

풀이는 1557을 기준으로 설명하고, 마지막에 8464에 적용하는 것은 간단하다 :)

 

 

1. 문제 설명

대략 $10^{10}$ 정도 되는 $n$이 주어지고 (1557은 $10^9$), 이때 $n$번째 Square Free 인 수 구하기 / Square Free가 아닌 수 구하기. 결국은 $n$ 번째 Square free 한 수를 구하는 문제라고 생각하고 풀어 보자.

 

 

2. 풀이

$n$번째를 구하는 데 $O(n)$ 시간 미만을 쓰는 것은 어려워 보이므로 다음과 같이 생각해 보자.

$S_n$ 을 $n$보다 작거나 같은 Square Free Number (귀찮으니까 SFN 이라고 하자) 의 개수라고 정의하자. 이때, $S_n$ 은 자명하게 단조증가하므로 이 함수에 대해 Parametric Search 같은 방법을 이용해서 문제를 해결할 수 있다. 

$n$번째 SFN이 대략 어느 정도일지 예측해야 양쪽 바운드를 잡을 수 있는데, 뭔가 많아 보이니 대충 넉넉하게 $10^{12}$ 정도 잡으면 충분해 보이고, 놀랍게도 $S_n$ 이 대략 $\frac{6}{\pi^2} n$ 임이 알려져 있으므로 사실은 이보다 훨씬 타이트하게 잡아도 된다.

 

아무튼, 이 시점에서 우리가 생각하는 시간 복잡도는 

$$T(n)\log 10^{12}$$ 니까, 대충 $T(n)$ 부분이 $n = 10^{10}$에 대해 몇백만 이내로 들어와 줘야 한다. 

즉, 이 문제는 다시 주어진 수보다 작은 SFN의 개수를 세는 문제로 바뀌며, 이를 포함 배제의 원리를 이용하여 기술하면 다음과 같이 쓸 수 있다.

 

$$S_n = n - \sum_{p_1^2 \leq n} \left[ \frac{n}{p_1^2} \right] + \sum_{p_1^2 p_2^2 \leq n} \left[ \frac{n}{p_1^2p_2^2} \right] - \sum_{p_1^2 p_2^2 p_3^2\leq n} \left[ \frac{n}{p_1^2p_2^2p_3^2} \right] \cdots$$

 

이 식을 잘 관찰해 보면, $\sqrt n$ 까지의 수들 중, 소수 0개가 포함된 수 (1) 은 더하고, 소수 1개로 구성된 수 (소수들) 은 빼고, 소수 2개의 곱인 수들은 더하고... 의 형태임을 알 수 있으며, 이를 나타내는 함수는 다시 뫼비우스 함수 $\mu(x)$ 이다. 보다 정확히 말하자면, 소수의 제곱 이상이 있는 수는 합에서 고려하지 않으므로 모두 버리고, 그외에는 $t$ 가 홀수개의 소수로 구성된 경우 $[n / t^2]$ 을 빼고, 짝수개인 경우 더하는 것임을 알 수 있으며 이를 짧게 쓰면,

$$S_n = \sum_{i \leq \sqrt n} \mu(i) \left[ \frac{n}{i^2} \right]$$ 이 식을 계산하면 된다는 사실을 알 수 있다.

넉넉하게 $10^6$ 까지의 Mobius function의 값을 미리 계산해 놓는다면, 이제 $S_n$ 을 $O(\sqrt{n})$ 시간에 계산할 수 있다. 뫼비우스 함수의 값은 $x$까지 구하는데 $x \log \log x$ 정도 시간에 구할 수 있으며, 시간 복잡도를 보면 눈치챌 수 있겠지만 에라토스테네스의 체와 매우 비슷한 방법을 이용하여 구한다. 

 

당연하게도, $S_n$ 대신 $S'_n$ 을 $n$까지의 SFN이 아닌 수들의 개수로 정의하면 그것도 $O(\sqrt n)$ 시간에 똑같이 구해서 똑같이 작성할 수 있다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
using pii = pair <int, int>;
#define int ll

int mobius[1010100];
int count_squarefree(int N)
{
	int ans = 0;
	for (int i = 1; i*i<=N; i++)
		ans += (mobius[i]*(N/(i*i)));
	return ans;
}

int32_t main()
{
	for (int i = 1; i <= 1000000; i++)
		mobius[i] = 1;
	for (int i = 2; i*i <= 1000000; i++)
	{
		if (mobius[i] == 1)
		{
			for (int j = i; j <= 1000000; j += i)
				mobius[j] *= -i;
			for (int j = i * i; j <= 1000000; j += i * i)
				mobius[j] = 0;
		}
	}
	for (int i = 2; i <= 1000000; i++)
	{
		if (mobius[i] == i)
			mobius[i] = 1;
		else if (mobius[i] == -i)
			mobius[i] = -1;
		else if (mobius[i] < 0)
			mobius[i] = 1;
		else if (mobius[i] > 0)
			mobius[i] = -1;
	}
	int k;
	cin >> k;
	int lo = 0, hi = 1e12;
	while (lo + 1 < hi)
	{
		int mid = (lo + hi) / 2;
		if (count_squarefree(mid)<k)
			lo = mid;
		else hi = mid;
	}
	cout << hi << '\n';
}