背景

在 $6月28日$ 考五级的上午， D 老师给我们讲了五级的一些知识点。以下是五级大纲：

---

初等数论

就是数学。就像上次的题目：原根判断 。

高精度

模拟竖式运算就好了。

链表

这个不会啊……但考试的时候它就考了一大堆链表。

后来学了：链表

辗转相除法

这是求两个数的最大公约数的方法。具体如下：

这比小学学的短除法快多了。很快可以发现，这可以用递归来实现。核心代码：

int gcd(int n, int m)
{
	if (m == 0)return n;
	return gcd(m, n % m);
}

素数表的埃氏筛法和线性筛法

这个……还好这个没有编程题。详细讲解

唯一分解定理

就是任意一个数（不知道有什么条件）都可以分解为质数的乘积。还好也没有编程题。参考代码：

void fj(int n)
{
	alen = 1;
	for (int i = 2; i * i <= n; i++)
    {
        if (n % i != 0)continue;
        while (n % i == 0)
        {
            n /= i;
            a[alen++] = i;
        }
    }
    if (n >= 2)a[alen++] = n;
    alen--;
    for (int i = 1; i < alen; i++)
    {
        printf("%lld*", a[i]);
    }
    int i = alen;
    printf("%lld", a[i]);
}

二分查找/二分答案

参考 二分 、 关于二分搜索（答案）三种写法的分析 。

贪心算法

这个嘛，多练。实际上一道贪心的编程题我只有 $17.5$ 分。

分治算法

这一块就很多东西了。

分治-快速幂

我们都知道， $a^{b+c}=a^b×a^c$ ，即 $a^{2b}=a^b×a^b$ ，而 $a^{2b+1}=a^b×a^b×a^1$ 。因此可以推导出快速幂的思路：

但是两边都是 $a^3$ ，所以可以剪枝。核心代码：

int fpow(int a, int b)
{
	if (b == 0)return 1;//0次方是1 
	if (b == 1)return a;
	int h = fpow(a, b / 2);
	if (b & 1)//b是奇数
		return h * h * a;
	else //偶数
		return h * h; 
}

分治-归并排序

归并排序是一种排序。时间复杂度： $o(n \log{n})$ 。思路：不停地中分数组（只是分成两份而已，没有特殊含义），直到数组只剩下一个数。然后在回溯时顺便排序。

这个顺便真的有点 tang 。本来就是用来排序的东西。

具体的排序方法：定义一个 i 和 j ，分别指向两个被中分的数组（实际上还是一个数组）。不停地比较 i 和 j 。如果 i 更小就把 i 放到一个新数组里，否则就把 j 放进数组里。这里的 i 和 j 代表它们指向的内容。具体方法（经过一段回溯之后，大数组的两个中分的小数组都已经排好序了）：

最后数组就排序好了。分治的时间： $\log{n}$ ， 排序的时间： $n$ 。总时间： $n \log{n}$ 。核心代码：

void msort(int l, int r)
{
    if (l == r)return ;

    int mid = l + (r - l) / 2;
    int i = l, p = l, j = mid + 1;

    msort(l, mid);
    msort(mid + 1, r);

    while (i <= mid && j <= r)
    {
        if (a[j] < a[i])
        {
            t[p] = a[j];
            p++;
            j++;
        }
        else
        {
            t[p] = a[i];
            p++;
            i++;
        }
    }
    while (i <= mid)
    {
        t[p] = a[i];
        p++;
        i++;
    }
    while (j <= r)
    {
        t[p] = a[j];
        p++;
        j++;
    }
    for (int i = l; i <= r; i++)
        a[i] = t[i];
}

分治-快速排序

概念：选择一个基准数，比它大的放右边，小的放左边。

递归

递归 ，就是函数调用自身。辗转相除法、快速幂、归并排序、求斐波那契数列（可以用）等都是递归。

算法复杂度的估算（含多项式、指数、对数复杂度）

简单粗暴

时间复杂度

数循环

空间复杂度

数数组