Graphics Programming
포함-배제의 원리 본문
포함-배제의 원리는 합집합의 크기 ($ n(A_1 \cup A_2 \; \cup \; ... \; \cup \; A_k) $) 를 세는 데 활용할 수 있는 기법이다.
다음은 수학 정규교육에서 집합을 배울 때 나오는 간단한 공식이다.
$$ n(A \cup B) = n(A) + n(B) - n(A \cap B) $$
위키피디아를 보면 위 공식을 k개 집합에 대해 일반화한 공식이 나온다.
출처: 위키피디아
하지만 위 공식을 코드로 구현하라면 가능할지 모르겠다. 대신 재귀적인 형태를 살펴보자.
($ A = A_1 $) , ($ B = A_2 \; ... \; A_k $) 를 대입하면
$$ n(A_1 \cup A_2 \; \cup \; ... \; \cup \; A_k) = n(A_1) + n(A_2 \cup \; ... \; \cup A_k) - n(A_1 \cap (A_2 \cup \; ... \; \cup A_k )) $$
각각의 ($ n(A_i) $)는 쉽게 계산할 수 있지만 합집합의 크기는 바로 세기 어려울 때 위와 같은 형태의 포함-배제의 원리를 활용하여 재귀적으로 문제를 해결할 수 있다.
문제: BOJ 9359 (서로소)
자연수 A, B, N이 주어질 때 A 이상 B 이하면서 N과 서로소인 자연수의 개수를 세는 문제다. A 이상 B 이하인 모든 정수 X에 대해 gcd(X, N) = 1 인지 검사해보면 될 것 같지만 A와 B의 차이가 최대 ($ 10^{15} $) 이기 때문에 시간 초과다.
($ N = {p_1}^{a_1} {p_2}^{a_2} ... {p_k}^{a_k} $) 으로 소인수분해하면 N의 소인수들의 집합 ($ \lbrace p_1, p_2, ..., p_k \rbrace $) 을 얻을 수 있다. 후보는 총 ($ B - A + 1 $) 개이고 ($ A_i = \text{(} p_i \text{로 나누어 떨어지는 수들의 집합)} $) 이라 하면 위의 공식을 이용해 이 중 N과 서로소가 아닌 수의 개수를 셀 수 있다. 후보의 개수에서 이 개수를 빼면 정답이 나온다.
소인수들의 목록이 주어질 때, 이 중 적어도 한 소인수의 배수인 수들의 개수를 세는 함수 recurse()를 다음과 같이 정의한다.
typedef long long ll;
ll recurse(vector<ll>& ps, int i, ll soFar, ll bnd) {
if(i == ps.size() || ps[i] * soFar > bnd) return 0;
ll ret = (bnd / ps[i]) / soFar;
ret += recurse(ps, i+1, soFar, bnd);
ret -= recurse(ps, i+1, ps[i] * soFar, bnd);
return ret;
}
ps는 소인수의 목록, i는 현재 소인수의 인덱스, soFar는 지금까지 포함된 소인수들의 곱, bnd는 상한선이다. N의 소인수들을 ps라 하면 N과 서로소가 아닌 수의 개수는 recurse(ps, 0, 1, B) - recurse(ps, 0, 1, A-1)이 된다. 이 수를 B - A + 1에서 빼면 원하는 서로소의 개수가 나온다.
위와 같은 재귀 함수로 포함-배제의 원리를 구현하는 방법은 한 탑코더 해설에서 배웠다. BOJ 1016 (제곱 ㄴㄴ수)도 같은 방법으로 풀 수 있다. 단 다른 사람들의 코드를 보니 1016번 문제는 단순하게 전수 검사해도 풀리는 것 같다.
전체 코드
