정수론적 함수

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}]$
  - Divisor summatory function 이라고 부른다
- 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))까지 최적화가 가능하다는것 같은데 제대로 안읽어봤다.

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
관련문제
- 잘못 구현한 에라토스테네스의 체