====== 정수론적 함수 ======

===== f(N)을 계산 =====
  * 1부터 sqrt(N)까지 증가시키면서 찾는다. O(sqrt(N))

===== f(1)+f(2)+...+f(N)을 계산 =====
  * [[https://ahgus89.github.io/algorithm/Harmonic-Lemma/]] 를 참고.
  * 어떤 함수들에 대해서는 $\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}] $
      * [[wp>Divisor summatory function]] 이라고 부른다
    * f(x) = σ(x) (x의 약수의 합) => $ \sum_{i=1}^{n} \sigma(i) = \displaystyle \sum_{d=1}^{n} d[{n \over d}] $
  * 이렇게 표현한 식은 [[#n1_n2__nn_을_계산|[N/1]+[N/2]+...+[N/N] 을 계산]]의 방법을 이용해서 O(sqrt(N))에 계산 가능하다
  * 관련 문제
    * [[ps:problems:boj:1457]] - ∑τ(x)를 구하는 문제
    * [[ps:problems:boj:15106]] - ∑σ(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 라고 부르는데, 따로 검색이 안되는 것을 보면 일반적으로 통용되는 명칭은 아닌것 같다.
      * [[https://math.stackexchange.com/questions/1069460/how-many-distinct-values-of-floorn-i-exists-for-i-1-to-n|관련 질문]]이 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)에 계산가능.
  * 코드는 이런식이 된다
    * <dkpr py>
answer = 0
while i <= num:
    j = num // (num // i)
    answer += num // i * (j - i + 1)
    i = j + 1
return answer
</dkpr>
  * 이 방법은 이 식 자체를 계산하는 것 보다는, f([N/1])g(1)+f([N/2])g(2)+...+f([N/N])g(N) 을 구하는 용도로 확장해서 사용하는 것이 핵심이다. 예를 들어 모든 약수의 합을 구할때에는 [[ps:problems:boj:15106]] 처럼 구현한다
    * 만약 이 식(=약수의 개수)만 계산하는 것이 목적이라면, 다음의 [[https://math.stackexchange.com/questions/487401/sum-of-floor-of-harmonic-progression-sum-i-1n-lfloor-frac-ni-rfloor-2-sum|공식]]을 활용해서 같은 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$
      * 코드는 이렇게 된다
        * <dkpr py>
sqrt = math.isqrt(num)
answer = 2 * sum(num // i for i in range(1, sqrt + 1)) - sqrt * sqrt 
</dkpr>
  * 관련문제
    * [[ps:problems:boj:15897]] 

===== f(1), f(2), ... ,f(N)을 모두 계산 =====
  * Linear sieve를 이용한다. O(N)