Graphics Programming

포함-배제의 원리 본문

Season 1/Problem solving

포함-배제의 원리

minseoklee 2016. 12. 24. 11:45

포함-배제의 원리는 합집합의 크기 ($ n(A_1 \cup A_2 \; \cup \; ... \; \cup \; A_k) $) 를 세는 데 활용할 수 있는 기법이다.


다음은 수학 정규교육에서 집합을 배울 때 나오는 간단한 공식이다.


$$ n(A \cup B) = n(A) + n(B) - n(A \cap B) $$


위키피디아를 보면 위 공식을 k개 집합에 대해 일반화한 공식이 나온다.


{\displaystyle {\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|={}&\sum _{i=1}^{n}|A_{i}|-\sum _{1\leq i<j\leq n}|A_{i}\cap A_{j}|+\cdots {}\\&{}\cdots +\sum _{1\leq i<j<k\leq n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}}

출처: 위키피디아


하지만 위 공식을 코드로 구현하라면 가능할지 모르겠다. 대신 재귀적인 형태를 살펴보자.


($ 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번 문제는 단순하게 전수 검사해도 풀리는 것 같다.


전체 코드



Comments