multiplicative function

수학에서 하도 자주 얻어맞아서, 이제 두드려 맞을 때마다 어디서 머리가 깨졌는지 적어놓기로 했다.

 

오늘은 https://codeforces.com/problemset/problem/757/E 이 문제를 풀다 막혔는데, 어느 정도 성질을 찾은 다음 그걸로 최적화하려고 한참 애쓰다 실패했다.

 

그리고 힌트를 좀 얻고 싶어서 breakun님에게 수학 찬스를 쓴 결과.. 어느 정도의 사전 지식이 필요하다는 것을 알게 됐다. 이 문제를 해결하기 위해 필요했던 multiplicative function에 관한 성질을 아래에 정리해둔다.

정의

어떤 양의 정수 $n$ 에 대해, $ab = n, gcd(a, b) =1$ 이라고 하자. 이런 모든 $a, b$에 대해 $f(n) = f(a)f(b)$ 가 성립할 경우 함수 $f$를 multiplicative function이라고 부른다.

성질

위 문제에서 $f_0(n)$ 이 multiplicative function임은 쉽게 증명할 수 있다. 어떤 수 $n$의 소인수가 $k$개인 경우 $f_0(n) = 2^k$이기 때문에 자연스럽게 성립한다.

 

 또, $f_r(n) = \sum_{d \mid n} f_{r-1}(d)$가 성립한다. 즉, $f_r(n)$은 자신의 모든 약수에 대해 $f_{r-1}$ 을 적용한 것을 모두 더한 것과 같다. 이건 주어진 식을 전개해보면 쉽게 알 수 있는 사실이다.

 

여기까지 전개하고 나면, multiplicative function의 성질을 이용해야 한다. multiplicative function $f$에 대해, 함수 $g$를 다음과 같이 정의하자.

 

$g(n) = \sum_{d \mid n} f(d)$

 

이 경우, 함수 $g$ 역시도 multiplicative function이 된다. 간단하지만 아주 강력한 성질이다. 이 성질을 응용하면 $f_0(n), f_1(n), f_2(n), \cdots, f_r(n)$이 연쇄적으로 전부 multiplicative function이 되므로 해당 성질을 이용해 최적화해서 문제를 해결할 수 있게 된다. 이런 성질이 성립한다는 것만 알게 되면 원 문제를 해결하는 것 자체는 별로 어렵지 않으므로 생략.

 

그러면, 이제 왜 저런 성질이 성립하는지 한 번 증명해보자.

증명

multiplicative function $f$에 대해 함수 $g$를 $g(n) = \sum_{d \mid n} f(d)$과 같이 정의했다고 하자.

 

$g(n) = \sum_{d \mid n} f(d)$

 

$ab = n, gcd(a, b) = 1$ 이라고 하자. 이 경우, 위 식은 아래와 같이 쓸 수 있다.

 

$g(n) = \sum_{d \mid ab} f(d)$

 

여기서, $x \mid a, y \mid b$ 인 $x$와 $y$를 생각해보자. 각각 $a$, $b$의 약수이고 $gcd(a,b) = 1$이므로 $gcd(x,y) =1$이다. 이 때, 위 식을 아래와 같이 바꿀 수 있다.

 

$g(n) = \sum_{x \mid a, y \mid b} f(xy)$

 

$ab$의 약수는 임의의 $a$의 약수와 $b$의 약수를 곱한 것으로 표현되어야하기 때문이다. 여기서 $f$가 multiplicative function 이라는 것과, $gcd(x, y) = 1$이라는 성질을 이용해 $f(xy) = f(x)f(y)$로 풀어쓸 수 있다.

 

$g(n) = \sum_{x \mid a, y \mid b} f(x)f(y)$

 

이제 $x$와 $y$가 독립적이므로,

 

$g(n) = \sum_{x \mid a} f(x) \cdot \sum_{y \mid b} f(y)$

 

왼쪽 오른쪽이 각각 $g$의 정의와 일치하므로,

 

$g(n) = g(a)g(b)$

 

따라서, 함수 $g$ 역시도 multiplicative function이 됨을 알 수 있다.

응용

정수론 문제에서 어떤 함수가 주어져있을 때, 접근이 막막하면 위 성질이 성립하는지 한 번 시도해보는 것은 좋은 방법일 것 같다. 일단 오일러 피 함수, 약수의 k제곱의 합 등의 함수도 모두 multiplicative function의 성질을 만족한다고 한다. 뭔가 이게 성립하는 함수가 생각보다 많은 듯.

 

이 성질 자체가 그냥 웰노운인 것 같은데 나는 이걸 이 문제를 풀면서 오늘 처음 알았다(...) 수학 관련한 지식은 다들 어디서 배우는걸까? 흑흑