Möbius inversion formula (BOJ 1792)

Möbius inversion formula
g와 f가 수론적 함수(arithmetic function)이며
$g(n)=\sum_{d\mid n}{f(d)}$ 이면 $f(n)=\sum_{{d\mid n}}g(d)\mu (n/d)$ 이다.

뫼비우스 반전공식을 시작하기에 앞서 갖춰야할 사전지식들이 있다.

1. 수론적 함수
   모든 양의 정수에서 값이 정의되는 함수로, 복소수의 수열이라고 볼 수 있다.
2. 뫼비우스 함수
   $n$이 $k$개의 소인수를 갖는 제곱 인수가 없는 정수라면 $\mu (n)=(-1)^{k}$이다.
   $n$이 제곱 인수가 없는 정수가 아니라면, $\mu (n)=0$이다.

뫼비우스 함수를 보고 제곱 ㄴㄴ 문제를 떠올리신 분도 있을 것 같다.

이 때 위에서 기술한 공식이 성립하는데, 이렇게 뫼비우스 함수가 뭔지 알고 보아도 이해가 안가는 식인건 마찬가지이다.

간단히 말하자면 $g(n)$이 n의 모든 양의 약수 d에 대해 $f(d)$의 누적합으로 표현될 때, $f(n)$을 $g(d)$를 이용해서 구할 수 있다는 말이다.

그러면 여기에서 다음과 같은 정리를 유도해낼 수 있다. 뫼비우스 반전공식에 대한 자세한 설명은 위키피디아를 참고하면 될 것 같다.

이제 공약수 문제를 다시 보자.

세 개의 정수 $a, b, d$가 주어지면, 다음의 세 조건을 만족하는 자연수 순서쌍 $(x, y)$의 개수를 구하는 프로그램을 작성하시오.

• $1 ≤ x ≤ a$
• $1 ≤ y ≤ b$
• $x$와 $y$의 최대공약수는 $d$이다.

식으로 표현하면 다음과 같다.

$\sum^a_{i=1}\sum^b_{j=1}[(gcd(i,j)=d]$

$i=\alpha d, j=\beta d$라고 하자. 이 때, 위 식은 아래와 같이 쓸 수 있다.

$\sum_{\alpha=1}^{\lfloor\frac{a}{d}\rfloor}\sum^{\lfloor\frac{b}{d}\rfloor}_{\beta=1}i(\gcd(\alpha,\beta))$

여기서 $i(\gcd(\alpha,\beta))$에 뫼비우스 반전공식을 적용하자.

그러면 다음과 같은 식을 만들 수 있다.

$\sum_{\alpha=1}^{\lfloor\frac{a}{d}\rfloor}\sum^{\lfloor\frac{b}{d}\rfloor}_{\beta=1}\sum_{d|gcd(\alpha,\beta)}\mu(d)$

이는 다음과 같이 정리되고, $(n = min({\lfloor\frac{a}{d}\rfloor, \lfloor\frac{b}{d}\rfloor)})$

$\sum_{\alpha=1}^{\lfloor\frac{a}{d}\rfloor}\sum^{\lfloor\frac{b}{d}\rfloor}_{\beta=1}\sum_{k=1}^{n}[k|gcd(\alpha,\beta)]\mu(k)$

이는 다시 아래와 같이 정리할 수 있다.

$\sum_{\alpha=1}^{\lfloor\frac{a}{d}\rfloor}\sum^{\lfloor\frac{b}{d}\rfloor}_{\beta=1}\sum_{k=1}^{n}[k|\alpha][k|\beta]\mu(k)$

이는 같은 변수끼리 묶었을 때, 아래처럼 쓰여지고,

$\sum_{\alpha=1}^{\lfloor\frac{a}{d}\rfloor}[d|\alpha]\sum^{\lfloor\frac{b}{d}\rfloor}_{\beta=1}[d|\beta]\sum_{k=1}^{n}\mu(k)$

최종적으로 우리가 구하고자하는 값은
$\sum_{k=1}^{n}\mu(k) \lfloor\frac{a}{kd}\rfloor\lfloor\frac{b}{kd}\rfloor$

로 처음보다 훨씬 계산횟수가 줄어든다.
이제 저 숫자는 뫼비함수의 구간합을 이용해서 빠르게 구할 수 있다.

참고자료 : Codeforce - Möbius inversion formula