【題解】P2424 約數和

啊，幾個月來第一篇題解，再掙紮兩下

\(Description\)

對于一個數X，函數f(X)表示X所有約數的和。例如：f(6)=1+2+3+6=12。對于一個X，Smart可以很快的算出f(X)。現在的問題是，給定兩個正整數X,Y(X<Y)，Smart希望盡快地算出f(X)+f(X+1)+……+f(Y)的值，你能幫助Smart算出這個值嗎？

\(Sample\) \(Input\)

123 321
           

\(Sample\) \(Output\)

72543
           

\(Hint\)

\(n\leqslant 2e9\)

\(Solution\)

我們簡單的考慮一下這道題，

約數的和......

哦，我會約數和定理！

時間複雜度 \(\mathcal O(n^2logn)\)

我們考慮不能直接求每個數的約數和但是我們可以考慮每個數的貢獻。

比如對于 \(i\) 我們考慮他作為約數對答案的貢獻，假設我們要做到 \(n\) 。

那麼有 \(\lfloor\frac{n}{i}\rfloor\) 個約數每個約數是 \(i\) 那麼 \(i\) 對 \(f(n)\) 的貢獻是\(\lfloor \frac{n}{i}\rfloor * i\)

是以我們可以得到一個快速求 \(f(n)\) 的辦法：

\(f(n)=\sum_{i=1}^{n} \lfloor \frac{n}{i}\rfloor * i\)

時間複雜度：\(\mathcal O(n)\)

好像還是過不了(那講個鬼啊

但是這提示了正解，我們看到除法在這樣一個式子裡我們是不是可以考慮除法分塊呢？

把商相同的直接一次算完。

我們把商相同的區間的左右端點叫做 \(l,r\)

我們現在隻要求 \(l,r\) 就可以

顯然 \(l=r+1\)

\(\frac{n}{l}\) 是商,右端點就是 \(n/\frac{n}{l}\) 。

之後隻要把目前這個商提出來再等差數列求個和

\(f(n)=\sum_{i=1}^{n} (r-l+1)*(l+r)/2*(n/l)\)

時間複雜度 \(\mathcal O(\sqrt n)\)

#include <bits/stdc++.h>
using namespace std;

#define int long long

inline int sum(int n){
	int ans=0;
	for(int L=1,R=0;L<=n;L=R+1){
		R=n/(n/L);
		ans+=(L+R)*(R-L+1)/2*(n/L);
	}
	return ans;
}

signed main(){
	int l,r;
	scanf("%lld%lld",&l,&r);
	printf("%lld\n",sum(r)-sum(l-1));
	return 0;
}