素数

• 素数：a > 1 且只能被平凡约数整除的数

• 合数：a > 1 且不是素数的数称为合数

• 平凡约数：a 的平凡约数就是1 和a 本身

• 因子：a 的非平凡约数为 称为a 的因子， 如20 的因子有，2， 4， 5， 10

• 也就是 20 = 2 * 10， 20 = 4 * 5

埃氏筛法

• 从小到大枚举每个数，如果当前数厄密划掉，必是素数，记录该质数，枚举当前质数的倍数，必是合数，划掉合数

• 代码：

typedef long long ll;

const int N = 100000010;
bool st[N];  //状态

void eratos(int n){

    for (ll i = 2; i <= n; i ++) st[i] = true;

    for (ll i = 2; i <= n/2; i ++){
        if (st[i]){
            for (ll j = i * i; j <= n; j += i){
                st[j] = false;
            }
        }
    }
}

二分

• 二分思想：

• 1. 确定一个区间，使得目标值一定在区间中
• 2. 找一个性质，满足两点：
• • a. 性质具有二段性：前面连续的一段是满足的，后面连续的一段是不满足的，中间是无缝隙衔接的，这样就具有二段性
• • b. 答案是二段性的分界点

整数二分

• 两大类：一类是二分值处理下面ans，一类是处理上面ans

• 第一类：目标值(ans)是红色区间的右端点

• 将[L, R] 分为 [L, M - 1] 和 [M, R]
  

if (M 是红色的){
    //说明答案(ans) 仍然在 [M, R]
}
else {
    //说明答案(ans) 必然在 [L, M - 1]
}

• 代码

while(L < R){
    M = (L + R + 1) / 2;

    if (M 为红色) L = M;
    else R = M - 1;
}

• 如果 M = (L + R + 1) / 2; 不补上1, M =(L + R) / 2

L = R - 1;

M = (L + R) / 2 = L;

if (M 为红色) L = M = L;

//这样就会一直死循环

• 第二类：目标值(ans)是绿色区间的左端点

• 将 [L, R] 分为 [L, M] 和 [M + 1, R]
  

if (M 是绿色){
    说明ans 在[L, M];
}
else{
    ans 必然是在[M + 1, R];
}

• 代码

while(L < R){
    
    M = (L + R) / 2;

    if (M 是绿) R = M;
    else L = M + 1;
}

• 第二类不用写M = (L + R + 1) / 2;

• L = R - 1;

• M = (L + R) / 2 = L;

• if 成立R = M = L, 跳出循环

• else L = M + 1 = L + 1 = R;

• 整数二分步骤：

• 1. 找一个区间[L, R], 使得答案一定在该区间中
• 2. 找一个判断性条件，使得该判断条件具有二段性，并且答案一定是该二段性的分界点
• 3. 分析终点M 在该判断条件下是否成立，如果成立，考虑答案在哪个区间；如果不成立，考虑答案在哪个区间
• 4. 如果更新方式写的是R = Mid，则不用做任何处理；如果更新方式写的是L = Mid，则需要在计算Mid 时加上1