统计一个序列所有数的因子个数

做很多题目时，经常会需要实现这么一种需求 “输入一串数字，需要统计所有因子的出现个数（比如存到cnt数组里）”。今天做题时学到了一种时间复杂度\(O(nloglogn)\)的做法，让只会\(O(n\sqrt{n})\)算法的我大开眼界。然而和同学一讨论发现这已经是人均算法了（悲。于是写一篇笔记记录一下。

---

入门 \(O(n\sqrt {n})\)

朴素的暴力算法。

对于每一个数\(x\)，从\(2\) ~ $ \sqrt{x}$枚举它的所有因子，如果 \(i\) 是 \(x\) 的因子，那么同时 \(\frac{x}{i}\) 也是 \(x\) 的因子，将这两个数的cnt增加\(1\)即可。对于 \(i * i = x\) 的情况需要特殊处理，避免使同一个因子增加两次。

大致代码

int cnt[maxn + 10];
for (int i = 1; i <= n; i++) {
	int x;
	cin >> x;
	for (int j = 2; j * j <= x; j++) {
		if (x % i == 0) {
			if (i * i == x)
				cnt[i]++;
			else {
				cnt[i]++;
				cnt[x / i] ++;
			}
		}
	}
}

这就是算法初学者（比如我）常学的简单做法，然而这个需求还可以做的更快

---

更快更强\(O(nloglog n)\)

直接上代码

先对值域进行欧拉筛

/////欧拉筛组件
 
bool f[maxn + 10];
vector<ll> primes;
void prime() {
	for (ll i = 2; i <= maxn; i++) {
		if (!f[i])
			primes.emplace_back(i);
		for (auto p : primes) {
			if (p * i > maxn)
				break;
			f[p * i] = true;
			if (i % p == 0)
				break;
		}
	}
}
/////

然后就可以算啦

prime();
for (int i = 1; i <= n; i++) {
	int x;
	cin >> x;
	cnt[x]++;
}
for (auto i : primes) {
	for (int j = maxn / i; j; j--)
		cnt[j] += cnt[i * j];
}

这个做法的时间复杂度与埃氏筛类似，可以达到\(O(nloglog n)\)，然而我数学捉急，并不会证（悲。具体证明过程和埃氏筛类似，可以通过oiwiki筛法页面进一步了解学习。

---

这个做法是在做Problem - D2 - Codeforces这道题时遇到的，如果有兴趣，也可以去做一做。