此篇是数学篇,主要补充之前涉及得少但比较重要的与数学相关的技巧和算法,如位运算、计算GDC(最大公约数)、LCM(最小公倍数)、分解质因数等。

位运算

此部分主要参考教程:

由于计算机内部以二进制来存储数据,所以位运算是相当快的——使用位运算可以在一定程度上优化我们的程序。

c++(其他语言同样)中的位运算有按位与、按位或、按位异或、按位取反,它们的描述如下:

运算 运算符 解释
按位与 & 两位都是1时结果才为1
按位或 \ 两位都是0时结果才为0
按位异或 ^ 两位不同时结果为1——重点是”异”
按位取反 ~ 所有位颠倒

位运算的应用主要有两方面:

  1. 一是题目本身要求我们对一个数进行位运算,这时我们往往需要用到位操作
  2. 二是使用位运算可以帮助我们省时省力地完成某些操作——即位运算优化

位操作

我们可以把一个数看成一个位串,如果我们需要像数组一样对这个位串进行操作,比如获得某一位的值,或者只为其中某一位赋值,就要用到位操作。

获得某一位的值

如果我们需要知道一个数n的第i位(i从0开始取)是0还是1,这时我们的操作是:

1
(n >> i) & 1;
解释

n右移i位后,第i位变成了右边的第一位,然后再和000……1按位与,最终结果就是第i位的值。

将某一位置1

如果需要将n的第i位置为1,我们的操作是:

1
n | (1 >> i);
解释

要将n的第i位置为1,那么需要将该位和1进行或运算;因为同时要保证其他位的值不变,那么除了第i位为1外,其他位都为0,即1>>i

将某一位置0

如果需要将n的第i位置为0,我们的操作是:

1
n & ~(1 >> i);
解释

同上,将n11……101…11按位与即可。

将某一取反

如果需要将n的第i位取反,我们的操作是:

1
n ^ (1 >> i);
解释

根据异或的功能,我们很容易知道,一个数和0异或,结果是其本身;和1异或,结果是其取反。所以我们只需要将n11……101…11按位异或即可。

其他

通过以上四种操作,我们就可以像数组一样操作位串了。下面再补充一些除上面的之外还很常用的位操作。

  • 把从右到左的第一个1变成0且不影响前面:
1
n & (n - 1);
  • 只留下从右到左第一个1,其余位全部变为0:
1
n & (-n);

位运算优化

判奇偶

我们常用的判奇偶的方式为:

1
2
n%2==1//奇数
n%2==0//偶数

实际上,将奇数用二进制表示,其最后一位必定为1;偶数的最后一位必定为0,那么,我们只需要知道最后一位的值即可:

1
2
n&1==1//奇数
n&1==0//偶数

判断同号

判断两个数是否同号的一般操作是:

1
2
a*b>0;//同号
a*b<0;//异号

使用位运算同样可以实现:

1
2
a^b>0;//同号
a^b<0;//异号

判是否为$2^n$

若一个数(非负整数) 为$2^n$,那么这个数的二进制表达中一定有且只有一位为1,判断方法有两种:

1
2
n & (n - 1) == 0;//是2的幂
n & (n - 1) != 0;//不是2的幂
1
2
n & (-n) == n;//是2的幂
n & (-n) != n;//不是2的幂

n&(n-1)n&(-n)的含义见上文。

乘/除以$2^n$

使用移位运算即可,右移i位代表乘以$2^i$,左移i位代表除以$2^i$。

1
2
n << i;//乘
n >> i;//除

OI Wiki很推荐使用这个方法求2的幂,因为使用位运算计算$2^n$与使用pow相比可以降低时间复杂度;而一般的优化只体现在常数层面——所以这个优化是很值得的!

交换两个数

异或满足交换律和结合律,同时a^a=0,所以可以用异或实现交换两个数(不使用临时变量):

1
2
3
a=a^b;//a=a+b
b=a^b;//b=a-b;
a=a^b;//a=a-b;

位运算练习

位1的个数

题目

编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为1的个数(也被称为汉明重量)。

示例 1:输入:00000000000000000000000000001011 输出:3

分析:前面我们知道了使用n&(n-1)可以把从右到左的第一个1变成0且不影响前面的数字。那么可以一直循环直到n为0。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int hammingWeight(uint32_t n) {
int ans=0;
while(n!=0){
n&=(n-1);
ans++;
}
return ans;
}
};

颠倒二进制位

题目

颠倒给定的 32 位无符号整数的二进制位。

示例 1:

输入:n = 00000010100101000001111010011100
输出:964176192 (00111001011110000010100101000000)

分析:这道题很明显是考位操作。交换两个值的方法有很多,这里使用最朴素的方法:使用临时的变量——其实这样的效率已经很不错了。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
for(char i=0;i<=15;i++){
char temp=(n>>i)&1;
if(((n>>(31-i))&1)==0) n&=~(1<<i);
else n|=1<<i;
if(temp==0) n&=~(1<<(31-i));
else n|=(1<<(31-i));
}
return n;
}
};

只出现一次的数字

题目

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:输入: [2,2,1] 输出: 1

这道题一开始的思路就是统计出现次数,但很明显需要借助额外的空间,所以不行。那么豁出去了,以时间换空间吧——先排序,再遍历;如果出现了两次就跳过。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int singleNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
if(i<nums.size()-1&&nums[i]==nums[i+1]) i++;
else return nums[i];
}
return 0;
}
};

果不其然,效率很低。那么有没有其他更好的方法呢?

分析:因为异或满足结合律,所以有a^a==0这种骚操作。所以可以遍历数组,对其中每个元素异或——最终的结果就是那个只出现一次的数字。

1
2
3
4
5
6
7
8
9
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans=0;
for(auto num:nums)
ans^=num;
return ans;
}
};

值得注意的是,C++中的vector<bool>bitset<> 会自动执行位级压缩,即其中每一个元素只占一位而不是字节!这样做的优点是可以成倍地节省空间,缺点是会降低效率,属于以时间换空间。

快速幂算法

此部分主要参考教程:

基本原理

快速幂又叫做二进制取幂,是使用二进制优化的在$O(logn)$的时间复杂度内快速计算出$a^n$的一种技巧。

如果要计算出$a^n$,我们一般的做法是将n个a相乘:

1
2
int ans=1;
for(int i=0;i<n;i++) ans*=a;

这个做法的时间复杂度为$O(n)$,效率是比较低的。

注意到n可用二进制表示:

$n=(n_t\ldots n_2n_1n_0)_2=n_t·2^t+ \ldots + n_1·2^1+ n_0·2^0$,其中$n_i$为二进制位。

那么最后$a^n$就可以写为:

$a^n=a^{n_t·2^t+ \ldots + n_1·2^1+ n_0·2^0}=a^{n_t·2^t}\times \ldots \times a^{n_1·2^1}\times a^{n_0·2^0}$

由于使用二进制本来就能将n用$\lfloor logn \rfloor+1$个二进制位表示,而要计算出$a^{n_0·2^0}$到$a^{n_t·2^t}$只需要不断平方,所以最终的时间复杂度为$O(logn)$。

结合位操作 可以很好的写出下面的代码:

1
2
3
4
5
6
7
8
long long bin_pow(int a,int n){
long long ans=1;
while(n>0){
if(n&1) ans*=a;
a*=a;
n>>=1;
}return ans;
}

应用:斐波拉契数列

将斐波拉契数列的通项公式用矩阵来表示:

要计算F(n),最终就归结到计算这个矩阵的n-1次方。所以,我们需要先后实现以下函数:

  1. 计算矩阵乘法的函数
  2. 快速幂计算矩阵的n次方
  3. 得到斐波拉契数列第n项值的函数

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//矩阵乘法
vector<vector<long long>> mat_mul(vector<vector<long long>>& a,vector<vector<long long>>& b){
int a_row=a.size(),a_column=a[0].size(),b_column=b.size();
vector<vector<long long>> ans(a_row,vector<long long>(b_column,0));
for(int i=0;i<a_row;i++)
for(int j=0;j<b_column;j++)
for(int k=0;k<a_column;k++)
ans[i][j]+=a[i][k]*b[k][j];
return ans;
}
//快速幂计算矩阵的n次方
vector<vector<long long>> bin_mul(vector<vector<long long>>& mat,int n){
int row=mat.size(),column=mat[0].size();
vector<vector<long long>> ans(row,vector<long long>(column,1 ));
while(n>0){
if(n&1) ans=mat_mul(mat,ans);
mat=mat_mul(mat,mat);
n>>=1;
}
return ans;
}
//得到F(n)
long long Fabric(int n){
if(n==0||n==1) return n;
vector<vector<long long>> mat={{1,1},{1,0}};
mat=bin_mul(mat,n-2);
return mat[0][0];
}

这样可以将计算斐波拉契数列的时间复杂度降到$O(logn)$。

但是斐波拉契数列到后面的值都很大,n仅仅上千时long long都会溢出,所以n一般不会计算到上百万的情况——$O(logn)$的时间复杂度其实是没有发挥出威力的。

gcd与lcm

本部分主要参考教程:

gcd即最大公约数,lcm即最小公倍数,二者之间有着千丝万缕的联系。该部分将从gcd的计算入手,然后再给出由gcd转换到lcm的方法,最后再推广到求多个数的gcd和lcm。

两个数的gcd

最大公约数的计算方法主要有三种:辗转相除法更相减损术,以及结合位运算和前者优点的Stein算法

辗转相除法

辗转相除法的理论依据是$gcd(a,b)=gcd(a,a\mod b)$,证明略。下面演示如何使用:

21和12的最大公约数=12和9的最大公约数=9和3的最大公约数=3和0的最大公约数。

所以根据表达式,我们很容易写出递归程序,递归的出口就是其中一个操作数为0:

1
2
3
4
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}

程序中只用判断b是否为0。因为若a<b,第一次操作会交换a、b,所以能保证a始终大于b。

更相减损术

更相减损术的做法就是不断让a、b作差,当a=b时即为最大公倍数。流程图及示例如下:

据此也很容易写出递归算法:

1
2
3
4
int gcd(int a,int b){
if(a==b) return a;
return a>b?gcd(a-b,b):gcd(a,b-a);
}

Stein算法

Stein算法的基本思路是:
  1. a、b均为偶数:$gcd(a,b)=gcd(a>>1,b>>1)<<1$
  2. a为偶数,b为奇数:$gcd(a,b)=gcd(a>>1,b)$
  3. a为奇数,b为偶数:$gcd(a,b)=gcd(a,b>>1)$
  4. a、b均为奇数:$gcd(a,b)=gcd(a-b,b)$(调用更相减损术)
  5. 当a=b时,即为最大公倍数

故代码如下:

1
2
3
4
5
6
7
int gcd(int a,int b){
if(a==b) return a;
if(!(a&1)&&!(b&1)) return gcd(a>>1,b>>1)<<1;
else if(!(a&1)&&(b&1)) return gcd(a>>1,b);
else if((a&b)&&!(b&1)) return gcd(a,b>>1);
else return a>b?gcd(a-b,b):gcd(a,b-a);
}

两个数的lcm

gcd和lcm之间的关系为:$gcd(a,b)\times lcm(a,b)=a \times b$。求出了gcd,我们很容易就能计算lcm!

1
2
3
4
int lcm(int a,int b){
//调用前面三种的一个即可
return a*b/gcd(a,b);
}

一组数的gcd与lcm

方法大同小异:

  1. 一组数的gcd的求法 :先求出前两个数的gcd,再用这个gcd与下个数求gcd,一直循环到最后一个数。
  2. 一组数的lcm的求法 :先求出前两个数的lcm,再用这个lcm与下个数求lcm,一直循环到最后一个数。
1
2
3
4
5
6
int gcds(vector<int> nums){
int ans=nums[0];
for(int i=1;i<nums.size();i++)
ans=gcd(ans,nums[i]);
return ans;
}
1
2
3
4
5
6
int lcms(vector<int> nums){
int ans=nums[0];
for(int i=1;i<nums.size();i++)
ans=lcm(ans,nums[i]);
return ans;
}

质数相关

对于质数我们主要研究两个问题,一是怎么判断一个数是否为质数,二是如何将一个合数分解质因数

质数的判定

暴力试除

要检测一个数是否为素数,就看除了1和它本身以外,是否还有其他因数——所以遍历2~n即可。

1
2
3
for(int i=2;i<n;i++){
if(n%i==0) return false;
}return true;

但是,判断一个数是否为素数就要$O(n)$的时间复杂度,效率是很低的。

注意到若a为n的因数,那么$\frac{n}{a}$也是n的因数,即因数都是成对出现的,——那么0~n都判断显然是有重复的。考虑极限情况$\frac{n}{a}=a\Rightarrow a=\sqrt{n}$,所以我们只需要从2判到$\sqrt{n}$即可。

1
2
3
for(int i=2;i<=sqrt(n);i++){
if(n%i==0) return false;
}return true;

这样时间复杂度就降到了$O(\sqrt{n})$。

筛法批量判定

筛法可以在很接近$O(n)$的时间复杂度下批量判定2~n范围内的质数。先观察下面的过程:

遍历完这数组后,最终标识为1的就是素数。很显然,我们还需要一个额外的数组来储存标志,所以空间复杂度为$O(n)$。

1
2
3
4
5
6
7
8
9
vector<bool> flag(n-1,1);
vector<int> ans;
for(int i=2;i<n;i++)
if(flag[i-2]==1)
for(int j=1;i*j<=n;j++)
flag[i*j-2]=0;
for(int i=2;i<=n;i++)
if(flag[i-2]==1)
ans.emplace_back(i);

在此基础上,还有如下的优化思路:

  1. 第一个循环只用从2判到$\sqrt{n}$。(读者可以思考为什么)
  2. 可以忽略除2以外的偶数——一开始就根本不用考虑。

上面的方法都是能准确判断出质数的方法。除此之外还有概率测试的方法,效率高但小概率判断失误,属于以概率换时间。这个方法本篇暂时不展开讨论。

分解质因数

算数基本定理

任何一个大于1的自然数N,且N为合数,那么N可以唯一分解为有限个质数的乘积。

由该定理可知,分解质因数一定是可行且唯一的!

分解质因数的方法也是试除法 ,也称为短除法。

如对12分解质因数,可以先分解出2,商为6;再对6分解质因数,分解出2,商为3;再对3分解质因数,分解出3,商为1。那么分解结果为:$12=2\times 2\times 3$。

可以使用递归,代码如下:

1
2
3
4
5
6
7
8
9
10
11
vector<int> primes;
void DPF(int n){
if(n==1) return;
for(int i=2;i<n;i++){
if(n%i==0){
primes.emplace_back(i);
DPF(n/i);
break;
}
}return;
}