题目大意
从题目可知，本题要求求出\(l \sim r\)的因子个数和。
题目分析
我们可以将这个问题分解为两个问题，变成求\(1 \sim r\)的因子个数和减去\(1 \sim l-1\)的因子个数和，然后我们考虑如何求\(1 \sim n\)的因子个数和
首先，如果正着做很难的话，我们可以考虑反着做。
对于一个数\(x\)，因为在\(1 \sim n\)中，有\(\lfloor n \div x \rfloor\)个数能被\(x\)整除，所以它对于因子个数的贡献为\(\lfloor n \div x \rfloor\)。
根据这个原理，我们可以写出一个时间复杂度为\(\mathcal{O}\left(n\right)\)的TLE程序：
#include<bits/stdc++.h>
#define int long long
const int N = 1e5+5;
const int Mod = 1e9+7;
using namespace std;
int l, r;
int f(int n)
{int cnt = 0;for(int i = 1; i <= n; i++){cnt += n / i;}return cnt;
}
signed main()
{cin >> l >> r;cout << f(r) - f(l - 1) << endl;return 0;
}
看来我们要把时间复杂度降到\(\mathcal{O}\left(\sqrt n\right)\)才可以。
可以想到，对于每一个数，他的因数必然是成对的（平方数除外），那么我们只需要遍历到\(\lfloor \sqrt n \rfloor\)，最后再乘以二即可。但是我们会发现，这样计算的结果比正确结果大很多，为什么呢？因为会有重复。所以我们要把重复的减去，这样才可以得到正确的结果。
那么现在我们要考虑哪些部分会重复。
我们以\(n\)为\(9\)为例：
| 数字 | 因数 |
|---|---|
| \(1\) | \(1\) |
| \(2\) | \(1,2\) |
| \(3\) | \(1,3\) |
| \(4\) | \(1,2,4\) |
| \(5\) | \(1,5\) |
| \(6\) | \(1,2,3,6\) |
| \(7\) | \(1,7\) |
| \(8\) | \(1,2,4,8\) |
| \(9\) | \(1,3,9\) |
我们的贡献统计是这样的：
| 数字 | 贡献数字对 |
|---|---|
| \(1\) | \(1\times\red1,1\times2,1\times3,1\times4,1\times5,1\times6,1\times7,1\times8,1\times9\) |
| \(2\) | \(\red2\times\red1,2\times\red2,2\times3,2\times4\) |
| \(3\) | \(\red3\times\red1,\red3\times\red2,3\times\red3\) |
通过观察重复的标红部分，我们发现每个数刚好重复了\(\lfloor \sqrt n \rfloor\)次！为什么会这样呢？因为每一个数乘上另外一个数，如果反过来还在表里面，那么就会重复。在表里面有\(\lfloor \sqrt n \rfloor\)个数，每个数会重复\(\lfloor \sqrt n \rfloor\)次，所以总共会重复\(\lfloor \sqrt n \rfloor\times\lfloor \sqrt n \rfloor\)次。
于是我们便可以完成最后的代码：
AC Code
#include<bits/stdc++.h>
#define int long long
const int N = 1e5+5;
const int Mod = 1e9+7;
using namespace std;
int l, r;
int f(int n)
{int cnt = 0, sqr = sqrt(n);for(int i = 1; i <= sqr; i++){cnt += n / i;}return cnt * 2 - sqr * sqr;
}
signed main()
{cin >> l >> r;cout << f(r) - f(l - 1) << endl;return 0;
}
