基本算法

简单数学

快速幂

1. 基本原理

   a^n有两种情况，一种是n为偶数，一种是n为奇数。
   我们都知道：a^n * a*m = a^(m+n)。
   因此，n为偶数时a^n=a^(n/2)∗a^(n/2)。
   而n为奇数时只需要再乘一个a就可以了。

2. 基础代码

   int 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;
   }

3. 以位运算为基础的加速代码

   (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。

int quickPower(int a, int b)//是求a的b次方
{
    int ans = 1, base = a;//ans为答案，base为a^(2^n)
    while(b > 0)//b是一个变化的二进制数，如果还没有用完
    {
        if(b & 1)//&是位运算，b&1表示b在二进制下最后一位是不是1，如果是：
            ans *= base;//把ans乘上对应的a^(2^n)

        base *= base;//base自乘，由a^(2^n)变成a^(2^(n+1))
        b >>= 1;//位运算，b右移一位，如101变成10（把最右边的1移掉了），10010变成1001。现在b在二进制下最后一位是刚刚的倒数第二位。结合上面b & 1食用更佳
    }
    return ans;
}

素数

1. 基本形式
   • 素数必然满足6n-1或者是6n+1的形式。
           证明：我们可以将任意一个数字写成…… 6n -1 , 6n, 6n+1, 6n+2, 6n+3, 6n+4, 6(n+1) -1, 6(n+1), 6(n+1)+1……         从写出的数字可以看出6n+2， 6n+3， 6n+4 = 2(3n + 2), 6n这一些数字必然不是素数，即可证明，如果一个除2，3之外的数字满足素数条件，这个数字必然是6n-1或者是6n+1的形式。但是并非6n-1或是6n+1必是素数，即为充分不必要。
   • 孪生素数必然满足被12整除

                证明：孪生素数除3，5之外。令孪生素数满足6n-1和6n+1的形式，及6n+1+6n-1 = 12n，必然被12整除。

2. 快速筛法(欧拉筛)

组合数

    1. 基本原理

        由数学公式可知，C(n, m) = C(n-1, m) + C(n-1, m-1)，对其进行基本的递推即可。

    2. 代码

long long num[MAX][MAX] = {0};


long long C(int n, int m)
{
    if (n == 0 || m == 0 || m == n || n == 1) return 1;
    if (num[n][m]) return num[n][m];
    
    num[n - 1][m] = C(n-1, m);
    num[n - 1][m - 1] = C(n-1, m-1);
    
    return num[n - 1][m] + num[n - 1][m - 1];
}