백준 9359: 서로소

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

 

간단화

이 문제는 누적 합을 푸는 요령으로 비슷하게 해결할 수 있다는 것은 금방 알았다.

f(x, n) = 1~x 사이에 n과 서로소의 갯수

라 정의 하면

f(B, N) - f(A - 1, N)

으로 간단화할 수 있다.

 

문제는 어떻게 f(x, n)을 구할 수 있을까다.

 

소인수분해

이것을 구하기 위해서 서로소의 정의를 다시 기억해보자.

서로소는 두 정수를 나눌 수 있는 양의 정수가 1밖에 없을 때를 서로소라한다.

이 말은 즉, 약수를 공유하지 않는다는 것이다.

 

그러면, 1 ~ X사이에 특정 수를 약수로써 가진 수는 몇개일까?

예를 들어, 2라면? 2, 4, 6, 8, 10 ... 

3이라면? 3, 6, 9, 12, 15 ...

즉, 특정 약수를 D라 정의했을 때, 1~X 사이에서 D를 약수로 가진 수의 갯수는 floor(X / D)다.

따라서 서로소의 갯수는 N - floor(X / D)

 

그렇다면, N을 소인수분해해서, 각 약수를 구하면 정답을 구할 수 있다.

 

좀 더 파고 들어보자.

 

만약 N = 12이라 할 때, 약수는 1, 2, 3, 4, 6, 12이다. 1과 12를 배제하면 남는 것은 2, 3, 4, 6 이다.

여기서, 4, 6을 살펴볼 필요가 있을까?

4, 6은 또한 2, 3을 약수로 두고 있기 때문에 2, 3만 살펴보면 된다.

따라서 이 문제에서 소인수분해를 했을 때, 지수 혹은 중복된 수는 필요없다.

포함 배제의 원리

이제 이 2, 3을 각각 N - floor(X / D)하고 더하면 될까? 아니다.

위에서 언급되었듯

 

2는 2, 4, 6, 8, 10 ... 

3은 3, 6, 9, 12, 15 ...

 

각각이 약수로 가지고 있다. 그런데, 6이 중복된다. 따라서 6을 약수로 가지고 있을때를 제외해야한다.

그렇다면 2, 3, 5는? 여기서 떠오른 것이 포함배제의 원리이다.

 

간단히 말하면, A, B, C, D... 각각의 집합의 합집합을 구하기 위해서는 각 집합을 더하고,

각 집합을 두개 씩 묶었을 때, 그 간의 교집합을 빼고,

각 집합을 세개 씩 묶었을 때, 그 간의 교집합을 더하고,

각 집합을 네개 씩 묶었을 때, 그 간의 교집합을 빼고

이런 식으로 반복한다.

https://ko.wikipedia.org/wiki/%ED%8F%AC%ED%95%A8%EB%B0%B0%EC%A0%9C%EC%9D%98_%EC%9B%90%EB%A6%AC

포함배제의 원리 - 위키백과, 우리 모두의 백과사전

그렇다면, N이 2, 3, 5로 소인수 분해 될때, 답은 다음과 같이 구할 수 있다.

(2의 서로소 갯수) + (3의 서로소 갯수) + (5의 서로소 갯수) - (6의 서로소 갯수) - (10의 서로소 갯수) - (15의 서로소 갯수) + (30의 서로소 갯수)

재귀를 활용하면 손 쉽게 구현할 수 있다.

#include <iostream>
#include <vector>
#include <set>

using namespace std;
using ll = long long;
int T;
ll A, B, N;
ll brute(set<ll>& f, int idx, ll cnt, ll m, ll l, ll a)
{
	if (l == cnt)
	{
		return a / m;
	}
	if (idx == f.size()) return 0;
	ll ret = 0;
	ret += brute(f, idx + 1, cnt, m, l, a);
	auto iter = f.begin(); advance(iter, idx);
	ret += brute(f, idx + 1, cnt + 1, m * (*iter), l, a);
	return ret;
}
ll solve(ll l, ll n)
{
	set<ll> s;
	for (ll i = 2; i * i <= n; i++)
	{
		while (n % i == 0)
		{
			n /= i;
			s.insert(i);
		}
	}
	ll ret = 0;
	if (n > 1) s.insert(n);
	for (int i = 1; i <= s.size(); i++)
		ret += ((i % 2 > 0) ? 1 : -1) * brute(s, 0, 0, 1, i, l);
	return l - ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> T;
	for (int t = 1; t <= T; t++)
	{
		cin >> A >> B >> N;
		ll ans = solve(B, N) - solve(A - 1, N);
		cout << "Case #" << t << ": " << ans << '\n';
	}
}

원래라면, set 사용은 잘 안하는데, 사소한 버그로 인해 여러 시도를 하다보니 사용을 하게 되었다.

그 사소한 버그도 long long 타입을 사용해야할 것을 int형으로 사용해서 발생한 전혀 상관없던 버그라서 더더욱 눈의 띈다.그래서 코드는 깔끔해졌으니, 넘어가자.