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)의 계산
- 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
- 관련 문제
약수함수
- τ(p^k) = k+1
- σ(p^k) = (p^(k+1)-1) / (p-1)
ps/곱셈적_함수.txt · 마지막으로 수정됨: 2023/03/20 04:06 저자 teferi
토론