2022-7-13 summary

The time for this summary is 2022-7-12~2022-7-13.

Summarize the learning algorithm ：

1. I have deeply studied the game , In especial SG function . I know several key points ：

（1）SG Expression of function ：sg(x) = mex{1,2, 3...} = 0, Defined as the smallest integer that does not appear .

（2）SG Function table template and understanding ： take SG Understand the relationship between function and binary , We define all 0 In a state of inevitable failure

00000000（ Suppose eight digits ） So for a state 00000001 It can be removed 1 Let him become all 0 It is a winning state

We can use the value that needs to be removed ^ To get . For any state, he has any way to turn it into a state of failure

Then it is in a winning state .

Main transformation ：（ The problem of taking stones ）

A and B Just as much ,A ^ B = 0 If you start, you'll lose

A - B - , A ^ B = 1 The first step is to win

A - B Defeat or A - B Defeat , A ^ B = 1 The first step is to win

A Defeat B Defeat A^B = 0 If you start, you'll lose

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

How to solve the problem , If you can't see it, type the watch first and then find the rule

2. Big prime judgement

Generally speaking, judge a number n Is it a prime number , You can use a root sign n The algorithm of . But when n Sometimes, for example ：100000000000000000, It's impossible at this time , Need to adopt a new property to judge , Fermat's small Theorem .

The condition of Fermat's theorem is P Prime number , On the contrary, if Fermat's small theorem holds, then P Prime number . But this judgment will be a little mistaken , Therefore, we need to make a second depth judgment （ I don't understand it very well here. I have to look at it ）.

Summarize the question brushing part ：

Two garbage CF+ Supplementary questions ：

Last year's winter vacation Niuke made up the question ：

 

 
  Game problem

Reading summary

Read the algorithm competition advanced graph theory 20 page （ Equivalent to review ）, Look at the integer solution of the binary first-order equation （20 page ）. There is an available corollary ：

ax + by = n There is an integer solution ====> gcd(a,b) Divisibility n.