標籤：

OI 數學數論

一個不大於n的正整數的約數個數期望意義下是多少？

01-05

嘗試證明某演算法時間複雜度時遇到的，比較糾結，想要把它算出來。

$O(ln n)$ 。

具體來說，記這個期望是 $x_n$ ，則明顯 $x_n=frac1nsum_{i=1}^nsigma_0(i)$ ，其中 $sigma_0(n)$ 表示 $n$ 的約數個數。考慮約數個數的意義並更換一下求和的次序，可以得到 $sum_{i=1}^nsigma_0(n)=sum_{i=1}^nsum_{dmid i}1=sum_{d=1}^nsum_{dmid i}1=sum_{d=1}^{n}leftlfloorfrac n d ight floor$ ，其本質是從枚舉約數改為枚舉倍數。而顯然 $sum_{d=1}^{n}leftlfloorfrac n d ight floorlesum_{d=1}^{n}frac n d=nH_n=O(nln n)$ ，因此 $x_n=O(ln n)$ 。

還有一種剛剛想到的更好理解的解釋。因為期望有線性性，所以我們只需考慮每個數是你選出的數的約數的概率即可。而 $d$ 整除你選出的數的概率顯然是 $frac 1 ncdotleftlfloorfrac n d ight floor$ ，求個和就能得到一樣的結論。

我們有

$sum_{n leq x} au(n) = sum_{n leq x} sum_{ab=n}1 = sum_{ab leq x}1$

所以要求的其實是第一象限內雙曲線ab=x下的整點個數，把求和區域切割一下就得到了

$sum_{ab leq x}1 = 2 sum_{d leq sqrt{x}} [frac{x}{d}]-[sqrt{x}]^2$

對右邊使用一個簡單的漸近公式

$sum_{n leq x}frac{1}{n}=log x + gamma+ O(frac{1}{x})$

就能算出來

$sum_{n leq x} au(n) = sum_{ab leq x}1 = x(log x + 2gamma - 1)+O(sqrt{x})$

從而看出來均階是 $log x$

一個有趣的問題是上面式子的余項的階最好能到多少，猜測是 $O(x^{1/4 +varepsilon})$ ，但是到目前為止依然是open的。

啊，這個簡單，n以內的數的約數也是n以內的數，對k來說，有[n/k]個數的約數中包含了k，按k求個和就得到所有數約數個數大概是n ln n，平均每個就接近ln n

期望為Divisor summatory function 除n,

所以期望 $D(n)/nsimeq ln(n)+2gamma-1$

其中 $gamma$ 為Euler-Mascheroni常數，約等於0.5772

在大n下該近似誤差不大，因為余項 $Delta(n)/nsim O(n^{ heta+epsilon-1}) o0$

既然是OI就要用OI的思維嘛233.估計是要分析 $sum_{xle n}sigma(x)$ 的值吧...

反過來想，考慮每個元素去找他的倍數來計算對答案的貢獻，有原式為：

$sum_{xle n}frac {n}{x} = nH_n$ ，其中 $H_n$ 為前n個調和數的和，利用積分解上下界，容易知道原式為 $O(nln n)$ 。平均來看就是 $O(ln n)$ 了。

推薦閱讀：

※為什麼在SPFA演算法中，判斷負權迴路的條件是任一節點進隊次數超過總結點數？
※在 codeforces 等信息學競賽平台，比賽被hack的瞬間是一種什麼樣的心情？
※如何評價NOI2016冬令營的題目？
※當你絞盡腦汁也想不明白一個演算法或者數據結構的時候，你會怎麼做？
※bfs能否解決一切dfs 問題？

TAG:數學 | 數論 | OI |