Zeldain Garden

链接：https://ac.nowcoder.com/acm/contest/7817/E

题目大意

给定一个区间$[n,m]$,统计这个区间内所有数的因数个数之和（包括1和自身），$1\leqslant n \leqslant m\leqslant 10^{12}$

题目分析

考虑一个数m的情况：由于所有因数总是成对出现，我们只需要枚举$[1,\sqrt{m}]$即可找出m的所有因数。

引申到区间，首先我们发现，$[n,m]$中所有数的因数对中，较小的那一个一定会小于$\sqrt{m}$,写成命题的话就是：

如果$a*b=x且x\in[n,m]，那么min\{a,b\}\leqslant\sqrt{m} $

根据这个性质，我们从1到$\sqrt{m}$枚举其中一个因子 $x$,找到这样两个整数$l$，$r$使得：

$$x\leqslant l\leqslant r ,且 n\leqslant l*x \leqslant r*x\leqslant m$$

为什么$l,r$要比x大呢？这是为了防止重复计算。如果我们有这样一个数$y$使得

$$n \leqslant y * y \leqslant m且y * (y-1) \geq n$$

那么在缺少这个限制时$y$和$y-1$这一对因数就会在$x=y,x=y-1$时分别被计算一次，答案就比正确答案大2。($ y-2,y-3…$同理)

这样，$[n,m]$中所有以x为因子的数的个数就是$r-l+1$，由于因数成对出现，我们就找到了$2*(r-l+1)$个因数。

值得注意的是平方数会多算一个因数，最后要把多余的数减掉。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 50;
typedef long long ll;

ll n, m, ans;

ll calc(ll k) {
    ll l = n / k + (n % k ? 1 : 0), r = m / k;
    l = max(l, k); //防止重复统计
    return 2 * (r - l + 1);
}

int main() {
    cin >> n >> m;
    for (ll i = 1; i * i <= m; ++i) {
        ans +=  calc(i);
        if (i * i >= n) ans--;
    }
    cout << ans << endl;
}