连续正整数的因子和之和问题

题目大意

已知正整数$x<y$, 求:

$$\sum _{i=x}^y\sum _{j|i}j$$

数据范围：

对于$50\mathrm{\%}$的数据，有：$0<x,y<=1\times {10}^6$

对于$100\mathrm{\%}$的数据，有：$0<x,y<=2\times {10}^9$

保证结果在long long范围内

题目分析

题面非常的直白。令$\sigma (x)=\sum _{i|x}x,D(x)=\sum _{i=1}^x\sigma (i)$，那么显然，我们所求的东西就是$D(y)-D(x-1)$。

接下来的问题就是，如何快速的求$D(x)$。

显然我们有一个$O(n)$的解法，就是枚举每一个数，求区间内他的倍数出现次数，得到$D(x)=\sum _{i=1}^{x}i\lfloor \frac{x}{i}\rfloor$。但这显然无法满足全部数据的要求。我们需要更快的解法。在此我们给出一个$O(\sqrt{n})$的解法。

先给出一个结论：

$$\begin{array}{rl}D(x)& =\sum _{i=1}^x\sigma (i)\\ & =x^2-\sum _{i=1}^x(xmodi)\end{array}$$

---

对于这个结论的证明（可以先跳过）：

$$\begin{array}{rl}D(x)& =x^2-\sum _{i=1}^x(xmodi)\\ & =\sum _{i=1}^{x}x-\sum _{i=1}^x(xmodi)\\ & =\sum _{i=1}^x(x-(xmodi))\\ & =\sum _{i=1}^{x}i\lfloor \frac{x}{i}\rfloor \\ & =\sum _{i=1}^x\sigma (i)\end{array}$$

---

那么我们的问题就是如何快速的求出这个$\sum _{i=1}^x(xmodi)$。

显然我们不可能直接枚举求它，这就不算优化了。这个东西乍一看比较困难。我们尝试求一下$x=100$时每一项的值：

0, 0, 1, 0, 0, 4, 2, 4, 1, 0, 1, 4, 9, 2, 10, 4, 15, 10, 5, 0,
16, 12, 8, 4, 0, 22, 19, 16, 13, 10, 7, 4, 1,
32, 30, 28, 26, 24, 22, 20, 18, 16, 14, 12, 10, 8, 6, 4, 2, 0,
49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 
24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 
6, 5, 4, 3, 2, 1, 0

我们可以发现：从某一项开始，他的值是由几段连续的等差数列拼成的，并且这几个等差数列的公差还是单调下降的一段连续自然数。这启发我们把它分解成几段连续的等差数列计算。

接下来就要考虑每段等差数列的起点问题。观察100的数据，我们发现，等差数列的起点分别是x/2+1, x/3+1, x/4+1, x/5+1等。那么我们只要枚举这个分母，然后利用等差数列求和即可。

---

关于这个等差数列的感性证明：

首先我们从大到小考虑。对于一个$i<x$，假如$i\in (\lfloor \frac{2}{x}\rfloor ,x]$，那么很显然$xmodi=x-i$。那么当$i$从$\lfloor \frac{2}{x}\rfloor$开始增大到$x$时，这显然就是一段等差数列。同样这也可以推广到分母为别的数的时候。

---

但是我们仍然没有解决实际问题。枚举分母这个过程仍然是线性时间的。但是我们可以只枚举分母到平方根，求出$\sqrt{x}\sim x$这几项的和。而对于小于$\sqrt{x}$的部分我们可以直接求对应项的和，这样就可以实现在$O(\sqrt{n})$时间内求解这个问题。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
static ll x, y;
static ll ans;
static ll num, s, t, curr, res, ori;
ll calc(ll x) {
  num = 1, curr = 1, res = 0, ori = x;
  while (x * x > ori) {
    s = ori % x;
    t = ori % (ori / curr + 1);
    num = x - ori / curr;
    res += (s + t) * num / 2;
    x = ori / curr;
    ++curr;
  }
  while (x) {
    res += ori % x;
    --x;
  }
  return ori * ori - res;
}
int main() {
  cin >> x >> y;
  ans = calc(y) - calc(x - 1);
  cout << ans << endl;
  return 0;
}