数学问题的解题窍门——《挑战程序设计竞赛》

发表于 | 分类于 | 浏览次数
字数统计: 433 字 | 阅读时长 ≈ 2 分钟

2.6.2 有关素数的基础算法

埃氏筛法

素数的个数：
给定整数n，请问n以内有多少个素数？

首先将2到n范围内的所有整数写下来，其中最小的数字2是素数，将表中所有2的倍数都划去，表中剩余的最小数字是3，它不能被更小的数整除，所以是素数，再将所有3的倍数划去。以此类推：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int prime[MAX_N]; //第i个素数
bool is_prime[MAX_N + 1];
//返回n以内素数的个数
int sieve(int n)
{
	int p = 0;
	for(int i=0;i<=n;i++)is_prime[i]=true;
	is_prime[0] = is_prime[1] = false;
	for(int i=2;i<=n;i++)
	{
		if(is_prime[i])
		{
			prime[p++] = i;
			for(int j=2*i;j<=n;j+=i) is_prime[j] = false;
		}
	}
	return p;
}

埃氏筛法的复杂度仅有$O(n\log\log n)$。

2.6.4快速幂运算

[https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=947]: “Carmicheal Numbers”

我们把对任意的1<x<n都有$x^n\equiv x(mod n)$成立的合数n称为Carmichael Numbers。对于给定的整数n，判断它是不是Carmichael Number。

考虑加速幂运算的方法，如果$n=x^k$，可以将其表示为

只要做k次平方运算就可以轻松求得。因此我们可以先将n表示成2的幂次的和：

就有：

只要依此求$x^{2^{k_i}}$，最终可以得到$O(\log n)$的计算幂运算的复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
typedef long long ll;
ll mod_pow(ll x, ll n, ll mod)
{
	ll res = 1;
	while(n>0)
	{
		if(n&1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}

在遍历n，即可得解，复杂度为$O(n\log n)$。