简单数学
快速幂
基本原理
a^n有两种情况,一种是n为偶数,一种是n为奇数。
我们都知道:a^n * a*m = a^(m+n)。
因此,n为偶数时a^n=a^(n/2)∗a^(n/2)。
而n为奇数时只需要再乘一个a就可以了。基础代码
1
2
3
4
5
6
7
8int Pow(int a,int n)
{
if (n==0) return 1;
if (n==1) return a;
int c=Pow(a,n/2);
if (n%2==0) return c*c;
return c*c*a;
}以位运算为基础的加速代码
(1)如果将 a 自乘一次,就会变成 a^2。再把 a^2 自乘一次就会变成 a^4 。然后是 a^8…… 自乘 n 次的结果是 a^(2^n) 。
(2)将底数转化为二进制看一下:
比如 b=(11)10 =(1011)2。从左到右,这些1分别代表十进制的 8,2,1。可以说 a^11=a^8×a^2×a^1。
1 | int quickPower(int a, int b)//是求a的b次方 |
素数
- 基本形式
- 素数必然满足6n-1或者是6n+1的形式。
- 孪生素数必然满足被12整除
证明:孪生素数除3,5之外。令孪生素数满足6n-1和6n+1的形式,及6n+1+6n-1 = 12n,必然被12整除。
- 快速筛法(欧拉筛)
组合数
1. 基本原理
由数学公式可知,C(n, m) = C(n-1, m) + C(n-1, m-1),对其进行基本的递推即可。
2. 代码
1 | long long num[MAX][MAX] = {0}; |