最多约数问题 （C++代码）

解题思路:

首先，考虑如何求解一个数有多少个约数，1的约数只有1个，其他的数字，对其进行质因数分解

可以得到 a = b1^c1 * b2^c2 * b3^c3 * ....如下结果，根据排列组合原理可以得到其约数个数为(c1+1)*(c2+1)*(c3+1)*....

而对于一个数质因数分解的效率，最暴力的方法为sqrt(n)，就算进行优化，也只能接近logn

对于本题的数据范围而言,nlogn（n=500w）时间来说效率还是太低。

所以我们需要O(n)的算法。

考虑的质因数分解实质上是质数的提取过程，我们可以利用线性素数筛法来O(n)的计算n里面的素数个数

同时，线性筛的原理或者说过程的操作，其实恰好符合了约数个数的求解过程。

对于

a = b1^c1 * b2^c2 * b3^c3

d = b1^（c1+1） * b2^c2 * b3^c3

上述两个数的约数关系就是 div(d) = div(a) / (c1+1) * (c1+2)

所以可以直接在线性筛的过程中求解出每个数的约数个数，然后就是循环求最大值了。

注意事项: 特判 1 1 这组测试数据

参考代码:

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 5e6 + 10;
int f[N], p[N], d[N];
int l, r;

int main() {
	scanf("%d%d", &l, &r);
	int ans = 1, t = 0;
	for (int i = 2; i <= r; i++) {
		if (!f[i]) p[t++] = i, f[i] = d[i] = 2;
		for (int j = 0; j < t && i * p[j] <= r; j++) {
			f[i * p[j]] = 2;
			d[i * p[j]] = d[i] * 2;
			if (i % p[j] == 0) {
				f[i * p[j]] = f[i] + 1;
				d[i * p[j]] = d[i] / f[i] * f[i*p[j]];
				break;
			}
		}
		if (i >= l) ans = max(ans, d[i]);
 	}
	printf("%d\n", ans);
	return 0;
}