当我们想要知道 [1,106][1, 10^6] 区间内每个数的因数个数。

方法一：

我们直接遍历找出所有因数。

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

int f[N];

inline void F(int x)
{
	f[1] = 1;
	for (int i = 2; i <= x; i++)
	{
		int j = 1;
		for (; j < i / j; j++) if (!(i % j)) f[i] += 2;
		if (j * j == i) f[i]++;
	}
	return ;
}

signed main()
{
	F(1000000);
	return 0;
}

时间复杂度为 O(nn)O(n\sqrt{n})。

方法二：

我们先将其质因数分解，再用约数个数定理[1] d(n)=∏i=1k(pi+1)d(n) = \prod_{i=1}^k (p_i+1)，计算出因数个数。

int f[N];
vector<pair<int, int> > p[N];

inline void F(int x)
{
	f[1] = 1;
	for (int i = 2; i <= x; i++)
	{
		int k = i;
		for (int j = 2; j <= k / j; j++)
		{
			if (k == 1) break;
			if (k % j) continue;
			int lst = p[i].size();
			p[i].push_back({j, 0});
			while (!(k % j)) k /= j, p[i][lst].second++;
		}
		f[i] = 1 + (k > 1);
		for (auto ite : p[i]) f[i] *= (ite.second + 1);
	}
	return ;
}

时间复杂度为 O(nn)O(n\sqrt{n})。

方法三：

在方法二的基础上，质因数分解只遍历质数。

int f[N];
vector<pair<int, int> > p[N];
vector<int> prime;

inline void F(int x)
{
	f[1] = 1;
	for (int i = 2; i <= x; i++)
	{
		int k = i;
		for (auto j : prime)
		{
			if (k == 1 || j > k / j) break;
			if (k % j) continue;
			int lst = p[i].size();
			p[i].push_back({j, 0});
			while (!(k % j)) k /= j, p[i][lst].second++;
		}
		f[i] = 1 + (k > 1);
		for (auto ite : p[i]) f[i] *= (ite.second + 1);
		if (f[i] == 2) prime.push_back(i);
	}
	return ;
}

时间复杂度为 $\sum_2 ^n O(n \cdot \pi(\sqrt{n})) = O(\frac{n\sqrt{n}}{\ln n})$[2][3]。

方法四：

因为当 gcd⁡(a,b)=1\gcd(a, b) = 1 时 d(ab)=d(a)⋅d(b)d(ab) = d(a) \cdot d(b)[4]，所以我们可以依此来求出因数个数。

例如令 $n = {p_1}^{a_1} \times {p_2}^{a_2} \times \cdots {p_k}^{a_k}$，则我们可以找到其最小因数 p1p_1，然后不停将 n÷p1n \div p_1 直到其中没有因数 p1p_1 得到最终结果为 xx，则 $x = {p_2}^{a_2} \times {p_3}^{a_3} \times \cdots {p_k}^{a_k}, \frac{n}{x} = {p_1}^{a_1}$。

显然 gcd⁡(x,nx)=1\gcd(x, \frac{n}{x}) = 1，故 d(n)=d(x)⋅d(nx)d(n) = d(x) \cdot d(\frac{n}{x})。

额外会有一些特殊情况需要去讨论。

int f[N];

inline void F(int x)
{
	f[1] = 1;
	for (int i = 2; i <= x; i++)
	{
		int k = i, cnt = 0;
		for (int j = 2; j <= i / j; j++)
		{
			if (f[j] > 2) continue;
			if (i % j) continue;
			while (!(k % j)) k /= j, cnt++;
			break;
		}
		if (k == i) f[i] = 2;
		else if (k == 1) f[i] = cnt + 1;
		else f[i] = f[k] * f[i / k];
	}
	return ;
}

时间复杂度为 O(nnln⁡n)O(\frac{n\sqrt{n}}{\ln n})。

方法五：

在方法四的基础上在遍历最小因数时遍历质数。

int f[N];
vector<int> prime;

inline void F(int x)
{
	f[1] = 1;
	for (int i = 2; i <= x; i++)
	{
		int k = i, cnt = 0;
		for (auto j : prime)
		{
			if (j > i / j) break;
			if (i % j) continue;
			while (!(k % j)) k /= j, cnt++;
			break;
		}
		if (k == i) f[i] = 2, prime.push_back(i);
		else if (k == 1) f[i] = cnt + 1;
		else f[i] = f[k] * f[i / k];
	}
	return ;
}

时间复杂度为 O(nnln⁡n)O(\frac{n\sqrt{n}}{\ln n})。

方法六：

用 Pollard-Rho[5] 单次 O(n14)O(n^{\frac{1}{4}}) 对每个数进行质因数分解，再用约数个数定理计算出因数个数。

using ll = long long;
int f[N];

inline ll mul(ll a, ll b, ll m)
{
	ll r = 0;
	a %= m; b %= m;
	while (b)
	{
		if (b & 1) r = (r + a) % m;
		a = (a + a) % m;
		b >>= 1;
	}
	return r;
}

inline ll power(ll a, ll b, ll m)
{
	ll r = 1; a %= m;
	while (b)
	{
		if (b & 1) r = mul(r, a, m);
		a = mul(a, a, m);
		b >>= 1;
	}
	return r;
}

inline bool is_prime(ll n)
{
	if (n < 2) return false;
	if (n == 2 || n == 3) return true;
	if (n % 2 == 0) return false;
	ll d = n - 1, s = 0;
	while (d % 2 == 0) d /= 2, s++;
	for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37})
	{
		if (a >= n) continue;
		ll x = power(a, d, n);
		if (x == 1 || x == n - 1) continue;
		bool composite = true;
		for (ll r = 0; r < s; r++)
		{
			x = mul(x, x, n);
			if (x == n - 1)
			{
				composite = false;
				break;
			}
		}
		if (composite) return false;
	}
	return true;
}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll pollard_rho(ll n)
{
	if (n % 2 == 0) return 2;
	if (n % 3 == 0) return 3;
	while (true)
	{
		ll c = uniform_int_distribution<ll>(1, n - 1)(rng);
		auto f = [&](ll x) { return (mul(x, x, n) + c) % n; };
		ll x = 2, y = 2, d = 1;
		while (d == 1)
		{
			x = f(x);
			y = f(f(y));
			d = __gcd(abs(x - y), n);
		}
		if (d != n) return d;
	}
}

inline void factorize(ll n, vector<ll>& factors)
{
	if (n == 1) return;
	if (is_prime(n))
	{
		factors.push_back(n);
		return;
	}
	ll d = pollard_rho(n);
	factorize(d, factors);
	factorize(n / d, factors);
	return ;
}

inline void F(int x)
{
	f[1] = 1;
	for (int i = 2; i <= x; i++)
	{
		if (is_prime(i))
		{
			f[i] = 2;
			continue;
		}
		vector<ll> factors;
		factorize(i, factors);
		unordered_map<ll, int> cnt;
		for (ll p : factors) cnt[p]++;
		f[i] = 1;
		for (auto &kv : cnt) f[i] *= (kv.second + 1);
	}
	return ;
}

时间复杂度为 O(n⋅n14)=O(n54)O(n \cdot n^{\frac{1}{4}}) = O(n^{\frac{5}{4}})[6]。

方法七：

在方法六的基础上，先线性筛一遍 [1,106][1, 10^6] 的区间，然后将 is_prime() 函数改为单次 O(1)O(1) 查询。

欸？线性筛……？你怎么知道我忘记线性筛怎么写了？[7]

using ll = long long;
int f[N];
bool isp[N];
vector<int> prime_table;

inline void linear_sieve(int n)
{
	fill(isp, isp + n + 1, true);
	isp[0] = isp[1] = false;
	for (int i = 2; i <= n; i++)
	{
		if (isp[i]) prime_table.push_back(i);
		for (int p : prime_table)
		{
			if (i * p > n) break;
			isp[i * p] = false;
			if (!(i % p)) break;
		}
	}
	return ;
}

inline ll mul(ll a, ll b, ll m)
{
	ll r = 0;
	a %= m; b %= m;
	while (b)
	{
		if (b & 1) r = (r + a) % m;
		a = (a + a) % m;
		b >>= 1;
	}
	return r;
}

inline ll power(ll a, ll b, ll m)
{
	ll r = 1; a %= m;
	while (b)
	{
		if (b & 1) r = mul(r, a, m);
		a = mul(a, a, m);
		b >>= 1;
	}
	return r;
}

inline bool is_prime(ll n) 
{
	return isp[n];
}

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
inline ll pollard_rho(ll n)
{
	if (n % 2 == 0) return 2;
	if (n % 3 == 0) return 3;
	while (true) {
		ll c = uniform_int_distribution<ll>(1, n - 1)(rng);
		auto f = [&](ll x) { return (mul(x, x, n) + c) % n; };
		ll x = 2, y = 2, d = 1;
		while (d == 1)
		{
			x = f(x);
			y = f(f(y));
			d = __gcd(abs(x - y), n);
		}
		if (d != n) return d;
	}
}

inline void factorize(ll n, vector<ll>& factors) 
{
	if (n == 1) return;
	if (is_prime(n))
	{
		factors.push_back(n);
		return;
	}
	ll d = pollard_rho(n);
	factorize(d, factors);
	factorize(n / d, factors);
	return ;
}

inline void F(int x)
{
	linear_sieve(x);
	f[1] = 1;
	for (int i = 2; i <= x; i++) 
	{
		if (is_prime(i))
		{
			f[i] = 2;
			continue;
		}
		vector<ll> factors;
		factorize(i, factors);
		unordered_map<ll, int> cnt;
		for (ll p : factors) cnt[p]++;
		f[i] = 1;
		for (auto &kv : cnt) f[i] *= (kv.second + 1);
	}
	return ;
}

时间复杂度为 O(n⋅n14)=O(n54)O(n \cdot n^{\frac{1}{4}}) = O(n^{\frac{5}{4}})[8]。

方法八：

线性筛即可求出因数个数。

欸？线性筛……？你怎么知道我忘记线性筛怎么写了？

int f[N], e[N];
vector<int> prime;

inline void F(int x)
{
	f[1] = 1;
	for (int i = 2; i <= x; i++)
	{
		if (!f[i]) prime.push_back(i), f[i] = 2, e[i] = 1;
		for (int p : prime)
		{
			if (i * p > x) break;
			if (i % p) f[i * p] = f[i] << 1, e[i * p] = 1;
			else
			{
				f[i * p] = f[i] / (e[i] + 1) * (e[i] + 2);
				e[i * p] = e[i] + 1;
				break;
			}
		}
	}
	return ;
}

时间复杂度为 O(n)O(n)。

  1. 约数个数定理介绍 - 百度百科 ↩︎

  2. π\pi 函数介绍 - 知乎专栏 ↩︎

  3. 由质数公式可得 - 百度百科 ↩︎

  4. dd 函数为积性函数的说明 - 博客园 ↩︎

  5. Pollard-Rho 介绍 - 知乎专栏 ↩︎

  6. 文中的代码实现常数极大，疑似 is_prime() 函数的单次 O(log⁡3n)O(\log^3 n) 所导致。 ↩︎

  7. 回收标题。 ↩︎

  8. 时间复杂度不变，但改用线性筛单次 O(1)O(1) 后效率翻了 1010 余倍[9]。 ↩︎

  9. 数据由 [未知] 计算机得到[10]。 ↩︎

  10. 版本信息、测评信息暂不公开。 ↩︎

0 条评论

目前还没有评论...
105
已通过
0
题解被赞
  1. Language
  2. 兼容模式
  3. 主题
  2. 浙ICP备2025180669号
  3. Worker 0, 20ms
  4. Powered by Hydro v5.0.0-beta.5 Community