사용자 도구

사이트 도구


ps:곱셈적_함수

곱셈적 함수 (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)의 계산

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

오일러 피 함수

  • φ(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
  • 관련 문제

약수함수

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

토론

댓글을 입력하세요:
D P L Y S
 
ps/곱셈적_함수.txt · 마지막으로 수정됨: 2022/06/02 07:49 저자 teferi