找到這個題了，順便A掉美滋滋。

這道題用到一個非常有用的結(jié)論。沒這個結(jié)論還沒得做：

\[\sum_{i=1}^{n}{d_1(i)} = \sum_{i=1}^{n}{\lfloor \frac{n}{i} \rfloor \times i}\]

注意：整體還有等于，一個的話沒有等于。

如果這個范圍小一點的話可以用線性篩搞掉，但是范圍太大了無法開下數(shù)組。所以轉(zhuǎn)換為右邊那種。

右邊這種的話就有除法分塊可以用了。不懂的話自己舉個例子看看就可以了。

原理是會有一些地方的商是相同的，直接一次性算掉。

據(jù)說復(fù)雜度是\(O(\sqrt{n})\)的。

對了，要用差分的思想，求出兩個之后減一下就是答案了。

只要開long long就可以了。

代碼:

#include<cstdio> #include<algorithm> #define ll long longll solve(ll n) {ll ans = 0;ll pos = 1;while(pos <= n){ll val = n / pos;ll endpos = std::min(n / val, n);ans += ((pos + endpos) * (endpos - pos + 1) / 2) * val;pos = endpos + 1;}return ans; } int main() {ll x, y; scanf("%lld%lld", &x, &y);ll temp1 = 0, temp2 = 0;temp1 = solve(y);temp2 = solve(x - 1);printf("%lld\n", temp1 - temp2);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Garen-Wang/p/9747596.html

總結(jié)

以上是生活随笔為你收集整理的P2424 约数和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。