목차

곱셈적 함수 (Multiplicative Function)
- 예
- f(x)의 계산
  - 오일러 피 함수
  - 약수함수
토론

곱셈적 함수 (Multiplicative Function)

gcd(m,n)==1 일때, f(mn) = f(m)f(n) 이 성립하는 함수들

예

φ(n): 오일러 피 함수. n보다 작고 n과 서로소인 자연수의 갯수
- 오일러 파이로 읽는 경우랑 오일러 피로 읽는 경우가 혼재한다.. 한글 위키피디아에서 조차 한 문서 내에서 파이라고 썼다가 피라고 썼다가 왔다갔다 하고 있다 ㅋㅋㅋ
τ(n): n의 약수의 갯수
σ(n): 시그마 함수. n의 약수의 합
μ(n): 뫼비우스 함수. n이 제곱인수를 포함하면 0, 그렇지 않으면 소인수의 갯수가 홀수이면 -1, 짝수이면 1.

f(x)의 계산

x가 소수의 거듭제곱이면, 즉 f(p^k)에 대해서는 식이 깔끔하게 정의되는 경우가 많다. 따라서 일반적인 n에 대한 함수값을 구할때는 n을 소인수분해해서 p_i*k_i 의 곱으로 표현한 뒤에, 각 p_i*k_i에 대해서 계산한 뒤에 모두 곱해주면 된다.
시간복잡도는 소인수분해의 시간 복잡도에 바운드된다.
- O(n^1/2) (trial division 사용시), O(n^1/4) (폴라드 로 사용시)

오일러 피 함수

φ(p^k)= p^(k-1) * (p-1) = p^k*(p-1)/p 를 이용해서 계산하면 된다.

실제로는 식을 좀더 정리하면 더 깔끔하게 구할수 있다

def euler_phi(n):
    for p in prime_factorization(n):
        n -= n // p
    return n

관련 문제
- GCD(n, k) = 1

약수함수

τ(p^k) = k+1
σ(p^k) = (p^(k+1)-1) / (p-1)