정수론

잡다한 지식

시간복잡도 계산을 위해, 어떤 수의 약수의 개수(= τ(n)) 가 필요할때에는 O(n^1/3) 으로 두면 대충 맞는다.
- 수학적으로는 근거도 없고 맞지도 않는다. 그러나 PS에서 사용하는 수의 범위 (10^18 이하?)에서는 대충 비슷하게 맞는다 (출처: https://codeforces.com/blog/entry/14463)
- 정확히는.. n<10^9 에서 가장 많은 약수의 갯수는 1344개, n<10^18 에서 가장 많은 약수의 갯수는 103680 이다
  - 출처: http://oeis.org/A066150
1부터 n까지의 모든 수에 대해서, 약수의 개수의 합을 구한 값, $D(n) = \sum_{1 \le k \le n}{\tau(k)}$ 은 대략 O(nlogn) 이다.
- 출처: Divisor summatory function
- D(10^5) = 1,166,750 = 11.6 * 10^5
- D(10^6) = 13,970,034 = 13.8 * 10^6
- D(10^7) = 162,725,364 = 16.2 * 10^7
- D(10^8) = 1,857,511,568 = 18.5 * 10^8