사용자 도구

사이트 도구


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))에 계산 가능하다
  • 관련 문제
  • 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)

토론

댓글을 입력하세요:
I E B D L
 
ps/정수론적_함수.txt · 마지막으로 수정됨: 2021/09/19 05:43 저자 teferi