首先很容易想到直接求解，對(duì)于較大的數(shù)據(jù)，\(O(n)\)做法無法通過。
注意到函數(shù)\(y=\lfloor\dfrac n x\rfloor\)的圖像如下：
(相關(guān)資料圖)
不難發(fā)現(xiàn)，隨著 \(x\) 增大 ，\(y\)單調(diào)不增，這說明對(duì)于相同值的 \(y\) 總是分布在同一塊區(qū)域。
這啟發(fā)我們根據(jù)\(y\)值，把\(x\)分組，每組“打包”算好。
這個(gè)時(shí)間復(fù)雜度顯然是 \(O(\sqrt n)\)的，時(shí)間復(fù)雜度與\(\lfloor\dfrac n x\rfloor\)的數(shù)量有關(guān)，這個(gè)數(shù)量大概是\(2\sqrt n\)。
雖然圖像上看\(y\)的數(shù)量很大，但是考慮到許多\(y\)不包含整數(shù)的\(x\),因此時(shí)間復(fù)雜度就是這樣的了。
代碼實(shí)現(xiàn)如下：
for(LL l=1,r;l<=n;l=r+1){ r=n/(n/l); ans+=(n/l)*(r-l+1);}對(duì)原式進(jìn)行推導(dǎo)：
\[\sum_{i=1}^nk\bmod i\\=\sum_{i=1}^nk-i\lfloor\frac k i\rfloor\\=nk-\sum_{i=1}^ni\lfloor\frac k i\rfloor\\\]后面的部分可以用整除分塊解決，對(duì)于每個(gè)\(\lfloor \dfrac n i\rfloor\),內(nèi)部相當(dāng)于一個(gè)等差數(shù)列。
代碼實(shí)現(xiàn)如下：
ans=n*k;for(LL l=1,r;l<=n&&l<=k;l=r+1){ r=min(k/(k/l),n); ans-=(k/l)*(r+l)*(r-l+1)/2;}函數(shù) \(f(i)\) 表示 \(i\) 所有約數(shù)的和。
求 \(\sum\limits_{i=L}^R f(i)\)。
考慮前綴和作差，問題變成\([1,R]-[1,L-1]\)。
于是不難列出式子求解，與上一題很像。
例題四\[\sum_{i=1}^n\sum_{j=1}^m (n\bmod i)(m\bmod j)\\\]這道題顯然也是推導(dǎo)。
\[\sum_{i=1}^n\sum_{j=1}^m (n\bmod i)(m\bmod i)\\=\sum_{i=1}^n(n\bmod i)\sum_{j=1}^m (m\bmod j)\\=\sum_{i=1}^n(n-i\lfloor\frac n i\rfloor)\sum_{j=1}^m (m-j\lfloor\frac m j\rfloor)\\=(n^2-\sum_{i=1}^n i\lfloor\frac n i\rfloor)(m^2-\sum_{j=1}^m m\lfloor\frac m j\rfloor)\\\]左右兩邊分開計(jì)算即可。
例題五\[\sum_{i=1}^n (n\bmod i)(m\bmod i)\\\]和上道題看著很像，不過這道題就很復(fù)雜了。
\[\sum_{i=1}^n (n\bmod i)(m\bmod i)\\=\sum_{i=1}^n (n-i\lfloor\frac n i\rfloor)(m-i\lfloor\frac m i\rfloor)\\=\sum_{i=1}^n (nm-(n+m)i\lfloor\frac n i\rfloor+i^2\lfloor\frac n i\rfloor\lfloor\frac m i\rfloor)\\=n^2m-(n+m)\sum_{i=1}^n i\lfloor\frac n i\rfloor+\sum_{i=1}^n i^2\lfloor\dfrac n i\rfloor\lfloor\frac m i\rfloor\\\]前面的式子我們已經(jīng)可以輕松求出了，對(duì)于后面的這個(gè)東西，我們還是畫圖觀察：
顯而易見，仍然滿足我們剛開始的兩個(gè)性質(zhì)，因此依舊使用之前的方式進(jìn)行整除分塊，時(shí)間復(fù)雜度依舊是\(O(\sqrt n)\)。
具體思想如下：
我們的值變化，要么是因?yàn)?\(\lfloor\dfrac n x\rfloor\) 變化了，要么是因?yàn)?\(\lfloor\dfrac m x\rfloor\) 變化了。
因此找出 \(\lfloor\dfrac n x\rfloor\) 變化的點(diǎn)和 \(\lfloor\dfrac m x\rfloor\) 變化的點(diǎn)中最近的一個(gè)，作為我們的 \(r\) 值。
后面部分的代碼實(shí)現(xiàn)如下：
for(LL l=1,r=0;l<=n;l=r+1){ r=min(n/(n/l),m/(m/l)); ans=ans+(n/l)*(m/l)*(sum(r)-sum(l-1));}這里出現(xiàn)了一個(gè)函數(shù)，它的作用是求出：\(sum_i=\sum\limits_{i=1}^ni^2\)。
公式是 \(\sum\limits_{i=1}^ni^2=\dfrac {n(n+1)\times(2n+1)} 6\)，用數(shù)學(xué)歸納法很好證明，這里不多贅述了。
