====== 곱셈적 함수 (Multiplicative Function) ======
  * gcd(m,n)==1 일때, f(mn) = f(m)f(n) 이 성립하는 함수들

===== 예 =====
  * φ(n): 오일러 피 함수. n보다 작고 n과 서로소인 자연수의 갯수
    * 오일러 파이로 읽는 경우랑 오일러 피로 읽는 경우가 혼재한다.. [[https://ko.m.wikipedia.org/wiki/%EC%98%A4%EC%9D%BC%EB%9F%AC_%ED%94%BC_%ED%95%A8%EC%88%98|한글 위키피디아]]에서 조차 한 문서 내에서 파이라고 썼다가 피라고 썼다가 왔다갔다 하고 있다 ㅋㅋㅋ
  * τ(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 를 이용해서 계산하면 된다.
  * 실제로는 식을 좀더 정리하면 더 깔끔하게 구할수 있다
    * <dkpr py>
def euler_phi(n):
    for p in prime_factorization(n):
        n -= n // p
    return n
</dkpr>
  * 관련 문제
    * [[ps:problems:boj:11689]]

==== 약수함수 ====
  * τ(p^k) = k+1
  * σ(p^k) = (p^(k+1)-1) / (p-1)