[笔记]OI中的数学

发表于 | 更新于 | 阅读次数：

导言

最近在学习OI中的数学，什么线性筛、欧拉函数等等。博主觉得这些知识点太繁杂了，决定整理一下，顺便做个笔记，也帮助大家整理一下知识点。顺便NOIP2018_RP++;ヾ(´∀`o)+。（真的只是浅谈）

1. 素数筛法

关于素数筛法，有很多算法可以求解。至于算法的效率，高级算法的时间复杂度相对于暴力也有了质的飞跃。

1.1 暴力枚举筛（别逗了）

要求解$1 \sim N$所有的质数，可以枚举$1 \sim N$所有数，然后对于每个数$K$我们可以枚举$2 \sim \sqrt{K}$，一一判断是否是$K$的因数。时间复杂度$O(N \sqrt{N})$

1.2 Eratosthenes筛法

摘一段百度百科的话。。

筛法是一种简单检定素数的算法。据说是古希腊的埃拉托斯特尼（Eratosthenes，约公元前274～194年）发明的，又称埃拉托斯特尼筛法（sieve of Eratosthenes）。

好了，具体怎么实现呢？

由于一个合数总是可以分解成若干个质数的乘积，那么如果把质数（最初只知道2是质数）的倍数都去掉，那么剩下的就是质数了。

例如要查找$100$以内的质数，首先$2$是质数，把$2$的倍数去掉；此时$3$没有被去掉，可认为是质数，所以把$3$的倍数去掉；再到$5$，再到$7$，$7$之后呢，因为$8,9,10$刚才都被去掉了，而$100$以内的任意合数肯定都有一个因子小于$10(\sqrt{100})$，所以，去掉$2,3,5,7$的倍数后剩下的都是质数了。

在做EratosthenesEratosthenes的时候我们还可以考虑一个优化：

对于素数$p$，我们只筛除倍数$x \ge p$的数

为什么呢？如果$x<p$，则$x$中一定有比$p$小的素因子，$p∗x$会在前面的筛选过程中被筛除。

1
2
3
4
5
6
7
8
9
10
11
12
#define MaxN 1000000
bool isPrime[MaxN+1];
void Eratos(int n)
{
	isPrime[0]=isPrime[1]=false;
	for (int i=2; i<=N; ++i) 
		isPrime[i]=true;
	for (int i=2; i*i<=N; ++i) 
		if (isPrime[i])
			for (int j=i*i; j<=N; j+=i)
				isPrime[j]=false;
}

1.3 欧拉筛法（线性筛）

素数筛法中最出名的应该算是线性筛了，它能够在$O(N)$的时间复杂度内筛出$1 \sim N$中所有的素数。

简单来说，线性筛就是筛除素数的倍数，但是要保证每个合数只被它的最小素因子筛除。

举个栗子↓↓↓

素数表 筛除的数 素数表 筛除的数
2 {2} {4} 13 {2,3,5,7,11,13} {26,39}
3 {2,3} {6,9} 14 {2,3,5,7,11,13} {28}
4 {2,3} {8} 15 {2,3,5,7,11,13} {30,45}
5 {2,3,5} {10,15,25} 16 {2,3,5,7,11,13} {32}
6 {2,3,5} {12} 17 {2,3,5,7,11,13,17} {34}
7 {2,3,5,7} {14,21,35,49} 18 {2,3,5,7,11,13,17} {36}
8 {2,3,5,7} {16} 19 {2,3,5,7,11,13,17,19} {38}
9 {2,3,5,7} {18,27} 20 {2,3,5,7,11,13,17,19} {20}
10 {2,3,5,7} {20} 21 {2,3,5,7,11,13,17,19} {42}
11 {2,3,5,7,11} {22,33} 22 {2,3,5,7,11,13,17,19} {44}
12 {2,3,5,7,11} {24} … … …

枚举$2 \sim N$中的每一个数$i$：
如果$i$是素数则保存到素数表中;
利用$i$和素数表中的素数$prime[j]$去筛除$i \times prime[j]$，为了确保$i \times prime[j]$只被素数$prime[j]$筛除过这一次，要确保$prime[j]$是$i \times prime[j]$中最小的素因子，即$i$中不能有比$prime[j]$还要小的素因子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Euler_sieve(int N)
{
	memset(isPrime,true,sizeof(isPrime));
	prime[0]=0; //prime[0]用来记录当前素数个数
	for(int i=2; i<=N; ++i)
	{
		if (isPrime[i]) prime[++prime[0]]=i; //把素数保存到素数表prime中，并更新素数个数
		for (int j=1; j<=prime[0]&&i*prime[j]<=N; ++j)
		{
			isPrime[i*prime[j]]=false; //筛除i*prime[j]
			if (i%prime[j]==0) break;
			//当i中含有素因子prime[j]时中断循环,确保每个数只被它的最小素因子筛除
		}
	}
}

2. 最大公因数和最小公倍数

OI中求最大公因数的常用方法就是欧几里得算法（辗转相除法）

给个模版吧，时间复杂度为$O(log(a+b))$

1
int gcd(int a,int b) {return b==0?a:gcd(b,a%b);}

利用一些$gcd$的性质我们也可以很容易的证明出欧几里得算法。

这里就不做说明了。

关于最小公倍数，求法也很简单：$lcm(a,b)=a/gcd(a,b)∗b$

这里最好先除再乘，防止爆$long \space long$

3. 快速幂

顾名思义，快速幂就是快速算底数的$N$次幂。其时间复杂度为$O(log_2N)$， 与朴素的$O(N)$相比效率有了极大的提高。

而快速幂的核心思想就是对指数进行二进制分解。举个栗子或许更好理解

例如：由于$11$的二进制是$1011$，所以$11=2^0+2^1+2^3$。所以可以进行转化$a^{11}=a^{2^0+2^1+2^3}$

于是我们转化为求解$a^{11}=a^{2^0} \times a^{2^1} \times a^{2^3}$

效率就可以大大的提升，快速幂可以用位运算来实现

b & 1 //取b二进制的最低位，判断和1是否相同，相同返回1，否则返回0，可用于判断奇偶

b >> 1 //就是将b的二进制右移一位，去掉b的二进制最低位(即第0位)，相当于除2

1
2
3
4
5
6
7
8
9
10
int FastPower(int a,int b)
{
	int ret=1,base=a;
	while (b)
	{
		if(b&1) ret*=base;
		base*=base; b>>=1;
	}
	return ret;
}

4. 欧拉函数

4.1 欧拉函数定义

在数论，对正整数N，欧拉函数是小于或等于N的正整数中与N互质的数的数目$(\varphi(1)=1)$。此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、$\varphi$函数、欧拉商数等。 例如$\varphi(8)=4$，因为$1,3,5,7$均和$8$互质。

4.2 求解欧拉函数

求欧拉函数有一个通式：$\varphi(x)=x∗\prod^{N}_{i=1}(1−\frac{1}{pi})$

其中$p1,p2……pn$为$x$的所有质因数，$x$是不为0的整数。

怎么证明呢，其实有一种很好理解的证明方法。

用数学期望来证明的话，对于$x$的每个素因子$pi$，在$1 \sim N$的范围内，含质因子$pi$的概率为$\frac{1}{pi}$，所以不含质因子$pi$的概率为$1−\frac{1}{pi}$，然后把概率乘起来就是$\varphi(x)$的值了。

4.3 欧拉函数的性质

有一个很明显的定理，当$p$为质数时，$\varphi(p)=p−1$

欧拉定理：对于互质的正整数$a$和$n$，有$a^{\varphi(n)}≡1(mod \space n)$。

欧拉函数是积性函数——若$m,n$互质，$\varphi(mn)=\varphi(m)\varphi(n)$。

若$n$是质数$p$的$k$次幂，$\varphi(n)=p^k−p^{k−1}=(p−1)p^{k−1}$，因为除了$p$的倍数外，其他数都跟$n$互质。

特殊性质：当$n$为奇数时，$\varphi(2n)=\varphi(n)$

欧拉函数还有这样的性质：

设$a$为$N$的质因数

  • 若$N\%a=0 \space and \space (N/a)\%a=0$则有$\varphi(N)=\varphi(N/a) \times a$
  • 若$N\%a=0 \space and \space (N/a)\%a!=0$则有$\varphi(N)=\varphi(N/a) \times (a−1)$

4.4 线性求欧拉函数

关于欧拉函数的线性筛法，利用上面的两条性质可以实现，下面给出了代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Euler_sieve(int N)
{
	memset(isPrime,true,sizeof(isPrime));
	phi[1]=1; prime[0]=0; //记录当前素数个数，phi[i]为i对应的欧拉函数值
	for (int i=2; i<=N; ++i)
	{
		if (isPrime[i]) prime[++prime[0]]=i,phi[i]=i-1;
			//把素数保存到素数表prime中，并更新素数个数
		for (int j=1; j<=prime[0]&&i*prime[j]<=N; ++j)
		{
			isPrime[i*prime[j]]=false; //筛除i*prime[j]
			if (i%prime[j]==0) {phi[i*prime[j]]=phi[i]*prime[j];break;}
			//当i中含有素因子prime[j]时中断循环,确保每个数只被它的最小素因子筛除
			else phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}