ps:정수론
정수론
- 특별히 여기에 쓸 내용은 없는데..
- 그냥 따로 하부페이지를 만들기 애매한 잡다한 것들을 적어보자..
잡다한 지식
- 시간복잡도 계산을 위해, 어떤 수의 약수의 개수(= τ(n)) 가 필요할때에는 O(n^1/3) 으로 두면 대충 맞는다.
- 수학적으로는 근거도 없고 맞지도 않는다. 그러나 PS에서 사용하는 수의 범위 (10^18 이하?)에서는 대충 비슷하게 맞는다 (출처: https://codeforces.com/blog/entry/14463)
- 정확히는.. n<10^9 에서 가장 많은 약수의 갯수는 1344개, n<10^18 에서 가장 많은 약수의 갯수는 103680 이다
- 1부터 n까지의 모든 수에 대해서, 약수의 개수의 합을 구한 값, $ D(n) = \sum_{1 \le k \le n}{\tau(k)} $ 은 대략 O(nlogn) 이다.
- 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
ps/정수론.txt · 마지막으로 수정됨: 2025/02/16 12:39 저자 teferi
토론