数学

最大公约数

最大公约数（greatest common divisor，gcd），又称最大公因数（highest common factor，hcf），指能够整除多个整数的最大正整数。而多个整数不能都为零。

例如 8 和 12 的最大公约数为 4。

素数

素数（Prime number），又称质数，指在大于 1 的自然数中，除了 1 和该数自身外，无法被其他自然数整除的数（也可定义为只有 1 与该数本身两个正因数的数）。

如 3、5、7、11、13、17、19、23 等。

更具体来说，素数又可分为两类：

• 4k + 3：3、7、11、19、23 等
• 非 4k + 3：5、13、17 等

斐波那契数列

阶乘

正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，计为 \(n!\)。例如：

\(5!=5\times 4\times 3\times 3\times 2\times 1=120\)

特别的，\(1\) 的阶乘 \(1!\) 为 \(1\)、\(0\) 的阶乘 \(0!\) 亦为 \(1\)，其中，\(0\) 的阶乘表示一个空积。

排列组合

从 \(n\) 个元素中取出 \(k\) 个元素，\(k\) 个元素的排列数量为：

\(P_k^n=\frac{n!}{(n-k)!}\)

从 \(n\) 个元素中取出 \(k\) 个元素，\(k\) 个元素的组合数量为：

\(C_k^n=\frac{n!}{k!(n-k)!}\)

级数与时间复杂度

• 算数级数：与末项平方同阶
• 幂方级数：比幂次高出一阶
• 几何级数（a>1）：与末项同阶
• 收敛级数：\(O(1)\)
• 调和级数：\(\Theta(logn)\)
• 对数级数：\(\Theta(nlogn)\)

// 算数级数，O(n^2)
for(int i = 0; i < n; i++)
{
    for(int j = 0; j < n; j++)
    {
        O1Operation(i, j);
    }
}

// 算数级数，O(n^2)
for(int i = 0; i < n; i++)
{
    for(int j = 0; j < i; j++)
    {
        O1Operation(i, j);
    }
}

// 算数级数，O(n^2)
for(int i = 0; i < n; i++)
{
    for(int j = 0; j < i; j += 2013)
    {
        O1Operation(i, j);
    }
}

// 几何级数，O(n)
for(int i = 1; i < n; i <<= 1)
{
    for(int j = 0; j < i; j++)
    {
        O1Operation(i, j);
    }
}

// 几何级数，O(logn*2^logn)
for(int i = 0; i <= n; i++)
{
    for(int j = 1; j < i; j += j)
    {
        O1Operation(i, j);
    }
}