ps:정수론적_함수
목차
정수론적 함수
f(N)을 계산
- 1부터 sqrt(N)까지 증가시키면서 찾는다. O(sqrt(N))
f(1)+f(2)+...+f(N)을 계산
- 어떤 함수들에 대해서는 $\sum_{i=1}^{n} f(i) = \sum_{d=1}^{n} g(d)[{n \over d}] $ 로 표현 가능하다
- f(x) = τ(x) (x의 약수의 갯수) ⇒ $ \sum_{i=1}^{n} \tau(i) = \displaystyle \sum_{d=1}^{n} [{n \over d}] $
- f(x) = σ(x) (x의 약수의 합) ⇒ $ \sum_{i=1}^{n} \sigma(i) = \displaystyle \sum_{d=1}^{n} d[{n \over d}] $
- 이렇게 표현한 식은 [N/1]+[N/2]+...+[N/N] 을 계산의 방법을 이용해서 O(sqrt(N))에 계산 가능하다
- 관련 문제
- 정확해 - ∑τ(x)를 구하는 문제
- Fear Factoring - ∑σ(x)를 구하는 문제
- https://rkm0959.tistory.com/190의 방법은 좀더 일반적인 multiplicative function들에 대해서 적용할수 있는 방법인듯 하다. O(N^(2/3))까지 최적화가 가능하다는것 같은데 제대로 안읽어봤다.
[N/1]+[N/2]+...+[N/N] 을 계산
- Lemma: 어떤 n에 대해서 [n/i] (1≤i≤n) 이 가질 수 있는 값의 종류는 2[√n]개 이하이다.
- https://ahgus89.github.io/algorithm/Harmonic-Lemma/ 참고. 이 블로그에서는 이것을 Harmonic lemma 라고 부르는데, 따로 검색이 안되는 것을 보면 일반적으로 통용되는 명칭은 아닌것 같다.
- 관련 질문이 math.stackexchange.com 에도 올라와있지만, 따로 명칭은 없다.
- 이것을 활용하면, ∑[n/i] 를 O(√n) 시간복잡도로 계산할 수 있다
- 나이브하게, 모든 i에 대해서 [n/i]를 구해서 더하면 O(n)이다
- [n/i]=K가 되는 i의 범위 [x,y]를 찾는다. i의 최대값 y는 [n/[n/i]] 으로 구할수 있다. 이제 x≤i≤y 범위에서 ∑[n/i] 는 [n/x]*(y-x+1) 로 O(1)에 바로 계산할 수 있다. 이러한 범위가 O(√n)개이므로, 전체 값을 O(√n)에 계산가능.
- 코드는 이런식이 된다
answer = 0 while i <= num: j = num // (num // i) answer += num // i * (j - i + 1) i = j + 1 return answer
- 이 방법은 이 식 자체를 계산하는 것 보다는, f([N/1])g(1)+f([N/2])g(2)+…+f([N/N])g(N) 을 구하는 용도로 확장해서 사용하는 것이 핵심이다. 예를 들어 모든 약수의 합을 구할때에는 Fear Factoring 처럼 구현한다
- 만약 이 식(=약수의 갯수)만 계산하는 것이 목적이라면, 다음의 공식을 활용해서 같은 O(√n)의 시간복잡도로 보다 간단하게 구할수 있다.
- $\sum_{i=1}^n\lfloor\frac ni\rfloor=2\sum_{i=1}^k\lfloor\frac ni\rfloor-k^2$ for $k=\lfloor\sqrt n\rfloor$
- 코드는 이렇게 된다
sqrt = math.isqrt(num) answer = 2 * sum(num // i for i in range(1, sqrt + 1)) - sqrt * sqrt
- 관련문제
f(1), f(2), ... ,f(N)을 모두 계산
- Linear sieve를 이용한다. O(N)
ps/정수론적_함수.txt · 마지막으로 수정됨: 2021/09/19 05:43 저자 teferi
토론