2022-7-13总结

本次总结的时间是2022-7-12~2022-7-13。

总结学习算法部分：

1.深入学习了博弈这一块，尤其是SG函数。知道了几个关键点：

（1）SG函数的表达式：sg(x) = mex{1，2， 3...} = 0，定义为最小没有出现的整数。

（2）SG函数打表模板及理解：将SG函数和二进制联系理解，我们定义全0为必败状态

00000000（假设八位数）那么对一个状态00000001能够拿掉1让他变成全0则为必胜状态

而需要拿掉的值我们可以使用 ^ 来求得。对于任意一个状态他有任意一种办法转化成必败状态

则本身为必胜状态。

主要转化：（取石头问题）

A和B一样多，A ^ B = 0 先手必败

A胜B胜， A ^ B = 1 先手必胜

A胜B败或A胜B败， A ^ B = 1 先手必胜

A败B败 A^B = 0 先手必败

void get_sg() {
    for (int i = 1; i < N; i++) {
        if (i & 1 && !sg[i - 1]) {
            sg[i] = 1;
            continue;
        }
        for (int j = 1; j <= 10; j++) {
            if (i >> j & 1) {
                for (int k = 0; k < j; k++) {
                    if (!sg[i ^ (1 << j) ^ (1 << k)]) sg[i] = 1;
                }
            }
        }
    }
}

解决问题思路， 看不出来就先打表然后找规律

2.大素判断

一般而言判断一个数n是不是素数，可以用根号n的算法。但是当n很大时比如：100000000000000000，此时是不行的，需要采用一个新的性质进行判断，费马小定理。

费马小定理的条件是 P是质数，反过来如果费马小定理成立那么P是质数。但是这个判断会有点误区，因此需要我们二次深度判断（这里没有搞太明白还要在看看）。

总结刷题部分：

两场垃圾CF+补题：

去年的寒假牛客补题：

 
 博弈题目

看书总结

看了算法竞赛进阶图论20页（相当于复习），看了二元一次方程整数求解（20页）。有一个可用的推论：

ax + by = n 有整数解 ====> gcd(a,b) 可以整除 n.