Möbius 함수의 정의와 활용
by nyan101
얼마 전 코드포스에서 흥미로운 문제를 접했다. 대회 당시에는 풀지 못했는데, 에디토리얼을 읽어보던 중 뫼비우스 함수(Möbius function)에 대한 언급이 있어 이에 대해 좀더 자세히 알아보았다.
Möbius function의 정의
뫼비우스 함수(Möbius function)는 자연수 n에 대해 다음과 같이 정의된다. (p는 소수)
μ(n)={(−1)kifn=p1p2⋯pk(pi≠pj)0ifp2|n다시 말해, n이 서로 다른 k개 소수들의 곱이면 μ(n)은 (−1)k이, 중복 소인수가 있으면(=어떤 제곱수를 약수로 가지면) 0이 되는 함수라고 할 수 있다. (이때 μ(1)=1)
뫼비우스 함수의 정의를 살펴보면 두 자연수 a,b에 대해 다음 성질이 성립함을 쉽게 알 수 있다.
μ(ab)=μ(a)μ(b)ifgcd(a,b)=1이밖에도 다양한 성질들이 있지만 이번 글에서는 알고리즘적 측면에서의 활용에 집중하기로 한다.
포함-배제의 원리
다음 벤 다이어그램을 살펴보자.
전체 합집합의 넓이는 어떻게 구할 수 있을까? 색칠을 해보면 다음 식을 어렵지 않게 구할 수 있다.
|A∪B|=|A|+|B|−|A∩B||A∪B∪C|=|A|+|B|+|C|−|A∩B|−|B∩C|−|C∩A|+|A∩B∩C|같은 원리를 확장하면 n개 집합에 대해 다음을 얻을 수 있다.
|n⋃i=1Ai|=n∑i=1|Ai|−∑i,j:1≤i<j≤n|Ai∩Aj|+∑i,j,k:1≤i<j<k≤n|Ai∩Aj∩Ak|− ⋯ +(−1)n−1|A1∩⋯∩An|이를 포함-배제의 원리라고 한다.
약수 관계에서의 포함-배제의 원리
이제 이를 약수-배수 관계에서 생각해보자. 자연수 n이 주어졌을 때 Sn을 정의할 수 있고, m이 n의 배수일 때 Sm⊂Sn 이 성립한다고 하자. 다시 말해, 각 집합끼리의 포함관계가 약수-배수 관계에 따라 정해지는 상황이다. 잘 와닿지 않는다면 간단히 Sn을 (max 이하의 자연수들 중) n2의 배수들의 집합1이라고 가정하고 읽어보자. 모든 자연수 n에 대해 |⋃ni=2Si| 를 구하려면 어떻게 해야 할까?
먼저 다음과 같은 성질을 알 수 있다.
- 자연수 a에 대해 Sa를 고려했으면 Sa2,Sa3 등은 고려할 필요가 없다
- ⋃ni=2Si 은 소수 pi들만을 고려한 ⋃piSpi 와 같다.
그렇다면 포함-배제의 원리에 따라 |⋃ni=2Si|는 다음과 같이 구할 수 있다.
- 소수 pi들에 대해 ∑i|Spi| 를 구해 더한다
- i<j 에 대해 ∑i<j|Spi∩Spj|를 구해 뺀다
- i<j<k 에 대해 ∑i<j<k|Spi∩Spj∩Spk|를 구해 더한다
- (이하 반복)
고려해야 할 경우의 수가 작으면 O(2n) 복잡도를 가지는 알고리즘으로 전체 경우의 수를 구할 수 있다. 그러나 수가 증가할수록 모든 경우를 고려하는 복잡도는 크게 증가한다. 뫼비우스 함수를 이용하면 이와 같은 포함-배제를 비교적 간단히 처리할 수 있다.
|n⋃i=2Si|=−n∑i=2μ(i)|Si|여기서는 단순히 집합의 크기만을 고려했지만 S=⋃ni=2Si에 대해 소속 원소의 함수값들의 aggregation을 구하는 경우, 즉 ∑x∈Sf(x) 나 ∏x∈Sf(x) 를 구하는 상황으로도 어렵지 않게 확장할 수 있다.
프로그래밍 언어로의 구현 (C++)
마지막으로 mu의 계산에 대해 알아보자. 주 원리는 다음과 같다.
- 모든 자연수 s는 m×p 형태로 표현할 수 있다. (p는 s의 가장 작은 소인수)
- 이때 m이 p의 배수이면 s는 제곱수를 인자로 가진다.
그러면 n 이하의 소수 리스트 vector<int> pvec
을 이용해 다음과 같이 int mu[n]
배열을 채울 수 있다.
int mu[n+1];
bool isPrime[n+1];
vector<int> pvec;
fill(isPrime, isPrime+n+1, true);
fill(mu, mu+n+1, -1);
mu[1] = 1;
for(int i=2;i<=n;i++)
{
if(isPrime[i])
pvec.push_back(i);
for(int p : pvec)
{
if(i*p > n) break;
isPrime[i*p] = false;
if(i%p == 0)
{
mu[i*p] = 0;
break;
}
mu[i*p] = mu[i]*mu[p];
}
}
연습문제
-
- [BOJ 1557번] 제곱 ㄴㄴ
- 본문에서 예시로 든 상황과 정확히 같다. “K 이하의 제곱 ㄴㄴ수”가 아닌 “K번째 제곱 ㄴㄴ수”임에 유의하자.
-
- [Codeforces] D. Steps to One (Round #548, Div.2)
- 포함배제를 O(2^n)에 진행할 수도 있지만 뫼비우스 함수와 Linearity of Expectation을 이용해 해결하는 풀이가 존재한다. “마지막 (1이 아닌) gcd가 k의 배수였을 때, 길이의 기대값”을 생각해보고 k=6인 상황은 k=2인 경우와 k=3인 경우 양쪽으로 해당될 수 있다는 점을 염두에 두면서 풀어보자.
-
단순히 “n의 배수들의 집합”이라고 할 수도 있지만, 그 경우 ⋃ni=2Si이 지나치게 단순해지므로 그보다는 약간 복잡한 정의를 선정. ↩
Subscribe via RSS