📚 课堂笔记：数论基础 + 前缀和进阶

---

知识点一：素数筛法（埃氏筛）

核心思想

用一个布尔数组标记每个数是否为合数。从 2 开始，每找到一个素数就把它的所有倍数标记为合数。

初始：isP[0]=1, isP[1]=1 （0和1不是素数）
i=2 → 标记 4,6,8,10,... 为合数
i=3 → 标记 6,9,12,15,... 为合数
i=4 → 已被标记，跳过
...

模板代码

const int N = 2e5 + 10;
bool isP[N];  // 0=素数, 1=合数

void sieve() {
    isP[0] = isP[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (isP[i] == 0) {           // i 是素数
            for (int j = i * 2; j <= N; j += i) {
                isP[j] = 1;          // 标记 i 的倍数为合数
            }
        }
    }
}

⚠️ 易错点

1. 筛的范围：筛到 N（常量上限），不是筛到 n（输入）。否则后续查询大数时没筛到
2. 0 和 1：必须初始化 isP[0]=isP[1]=1，它们不是素数
3. 复杂度：O(N log log N)，接近线性，1e7 以内无压力

---

📝 例题1：P655 质因数分解（难度2）✅ AC

题意：给定正整数 n（n≥2），求 n 的最大质因数。
保证 n 最多只有两个质因子（即 n = p × q，p ≤ q，p、q 都是素数）。

思路：从小到大枚举，找到第一个能整除 n 的素数 p，则答案 = n / p。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
bool isP[N];

int main() {
    int n;
    cin >> n;
    
    // 筛法预处
    isP[0] = 1; isP[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (isP[i] == 0) {
            for (int j = i * 2; j <= N; j += i) {
                isP[j] = 1;
            }
        }
    }
    
    // 从小到大找第一个能整除 n 的素数
    for (int i = 2; i * i <= n; i++) {   // 只需枚举到 sqrt(n)
        if (isP[i] == 0 && n % i == 0) {
            cout << n / i;   // 较大的质因子 = n / 较小的质因子
            return 0;
        }
    }
    return 0;
}

关键点：

• 枚举到 i*i <= n 即可，因为如果 n = p×q 且 p ≤ q，那么 p ≤ √n
• 找到小因子 p 后，大因子直接 n/p 得到

---

📝 例题2：P4792 素数的个数（难度3）✅ AC

题意：给定 n 和 m，求区间 [n, m] 内素数的个数。

思路：筛到上限 1e7，然后遍历 [n, m] 统计素数个数。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e7 + 10;   // ⚠️ 上限要足够大
bool isP[N];

int main() {
    isP[0] = 1; isP[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (isP[i] == 0) {
            for (int j = i * 2; j <= N; j += i) {
                isP[j] = 1;
            }
        }
    }
    
    int n, m, cnt = 0;
    cin >> n >> m;
    for (int i = n; i <= m; i++) {
        if (isP[i] == 0) cnt++;
    }
    cout << cnt;
    return 0;
}

关键点：

• 数组大小 N = 1e7 + 10，要放在全局区（栈上放不下）
• 筛的循环也要到 N，不能只到 m（虽然实际上到 m 就够了）

---

知识点二：最大公约数 (GCD)

核心公式

• GCD(a, b)：a 和 b 的最大公约数
• LCM(a, b) = a × b / GCD(a, b)
• C++ 内置函数：__gcd(a, b)（需要 <bits/stdc++.h> 或 <algorithm>）

性质

1. GCD(a, b) = GCD(b, a % b) ← 辗转相除法
2. GCD(a, 0) = a
3. 如果 GCD(a, b) = 1，则 a 和 b 互质
4. a 和 b 的所有公约数都是 GCD(a, b) 的约数

---

📝 例题3：P910 最大公约数和最小公倍数问题（难度2）✅ AC

题意：给定 x0 和 y0，求满足以下条件的 (P, Q) 的对数：

• GCD(P, Q) = x0
• LCM(P, Q) = y0

思路：

1. P × Q = GCD × LCM = x0 × y0（设乘积为 ch）
2. 枚举 ch 的所有因子对 (i, ch/i)
3. 检查 GCD(i, ch/i) 是否等于 x0，LCM 是否等于 y0
4. 如果 i = ch/i（即 i² = ch），只算 1 对，否则算 2 对（正反顺序）

#include<bits/stdc++.h>
#define int long long    // ⚠️ 防止乘法溢出
using namespace std;

signed main() {
    int x0, y0, cnt = 0;
    cin >> x0 >> y0;
    int ch = x0 * y0;    // P*Q = GCD*LCM
    
    for (int i = 1; i * i <= ch; i++) {   // 枚举到 sqrt(ch)
        if (ch % i == 0) {
            int x = i, y = ch / x;
            int da = __gcd(x, y);           // 最大公约数
            int xiao = x / __gcd(x, y) * y; // 最小公倍数 = x*y/gcd
            if (x0 == da && y0 == xiao) {
                if (da == xiao) {
                    cnt++;       // P=Q，只算一对
                } else {
                    cnt += 2;    // (P,Q) 和 (Q,P) 不同
                }
            }
        }
    }
    cout << cnt;
    return 0;
}

关键点：

• #define int long long 防止 x0 * y0 溢出
• 枚举因子只需到 sqrt(ch)，另一半是 ch / i
• LCM 计算要先除后乘：x / gcd(x,y) * y，避免中间结果溢出

---

📝 例题4：P6753 次大公约数（难度3）✅ AC

题意：给定 a 和 b，求 GCD(a, b) 的最大真因子（即除 GCD 本身外最大的约数）。

思路：

1. 先求 g = GCD(a, b)
2. 如果 g = 1，没有真因子，输出 -1
3. 否则找 g 的最小质因子 p（从 2 枚举到 sqrt(g)），答案 = g / p
4. 如果 g 本身是素数（没有找到因子），答案 = 1

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    int a, b;
    cin >> a >> b;
    int go = __gcd(a, b);
    
    if (go == 1) {        // 互质，无公约数
        cout << -1;
        return 0;
    }
    
    bool f = 0;
    for (int i = 2; i * i <= go; i++) {  // 找最小质因子
        if (go % i == 0) {
            cout << go / i;   // g / 最小质因子 = 最大真因子
            f = 1;
            break;
        }
    }
    if (f == 0) {
        cout << 1;   // g 本身是素数，最大真因子是 1
    }
    return 0;
}

关键点：

• 次大公约数 = GCD 的最大真因子 = GCD / GCD的最小质因子
• 因为 g 的因子中，最小的因子对应的最大因子就是 g/最小因子

---

📝 例题5：P6773 约数（南海区赛）✅ AC

题意：给定 a 和 b，设 g = GCD(a, b)。有 q 次查询，每次给 [l, r]，求 g 的所有约数中，在 [l, r] 范围内的最大约数。没有则输出 -1。

思路：

1. 求出 g 的所有约数，存入数组并排序
2. 每次查询从大到小遍历约数数组，找到第一个在 [l, r] 内的

#include<bits/stdc++.h>
#define int long long
using namespace std;
int isP[1001];   // 存储约数

signed main() {
    int a, b;
    cin >> a >> b;
    int go = __gcd(a, b);
    int q;
    cin >> q;
    
    int cnt = 0;
    for (int i = 1; i * i <= go; i++) {   // 枚举 g 的所有约数
        if (go % i == 0) {
            cnt++;
            isP[cnt] = i;           // 小因子
            cnt++;
            isP[cnt] = go / i;      // 大因子
        }
    }
    
    sort(isP + 1, isP + cnt + 1);   // 排序后从大到小找
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        int flag = 0;
        for (int i = cnt; i >= 1; i--) {  // 从大到小找
            if (isP[i] >= l && isP[i] <= r) {
                cout << isP[i] << endl;
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            cout << -1 << endl;
        }
    }
    return 0;
}

关键点：

• 枚举约数到 sqrt(g)，每次同时加入 i 和 g/i
• 约数可能有重复（当 i = g/i 时），但本题不影响答案
• 排序后从后往前找第一个在范围内的，保证最大

---

知识点三：前缀和进阶（课堂讲解）

基础回顾：前缀和求区间和

s[i] = s[i-1] + a[i]     // s[i] = 前 i 个数的和
区间 [L, R] 的和 = s[R] - s[L-1]

🌟 进阶：前缀和不止能求和，还能统计区间信息

课堂示例：统计区间内有多少个偶数

// s[i] 表示前 i 个数中有多少个偶数
// s[i] = s[i-1] + (a[i] % 2 == 0)
// 区间 [L, R] 中偶数的个数 = s[R] - s[L-1]

为什么有效：把「是否为偶数」转化为 0/1 值，前缀和就变成了计数前缀和。

📝 例题6：P4760 偶数个数（难度2）✅ AC

题意：给定 n 个数，q 次查询，每次查询 [l, r] 区间内偶数的个数。

完美对应课堂讲解的前缀和进阶用法！

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int n, q, l, r, x, s[N];   // s[] 是前缀和数组

signed main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        s[i] = s[i-1] + (x % 2 == 0);   // 核心一行：前缀和统计偶数
    }
    while (q--) {
        cin >> l >> r;
        cout << s[r] - s[l-1] << endl;   // 区间偶数个数
    }
    return 0;
}

关键点：

• s[i] = s[i-1] + (x % 2 == 0)：表达式 x % 2 == 0 结果为 1 或 0，直接累加
• 查询 O(1)，总复杂度 O(n + q)

前缀和计数的一般化

统计目标	转化方式	s[i] 定义
区间和	直接累加	s[i] = s[i-1] + a[i]
区间偶数个数	a[i]%2==0 → 1/0	s[i] = s[i-1] + (a[i]%2==0)
区间奇数个数	a[i]%2==1 → 1/0	s[i] = s[i-1] + (a[i]%2==1)
区间满足条件个数	条件为真 → 1/0	s[i] = s[i-1] + (条件(a[i]))
区间内某值出现次数	a[i]==k → 1/0	s[i] = s[i-1] + (a[i]==k)

💡 记忆口诀：前缀和就是「打标记 + 累加 + 做差」

---

知识点四：定长区间枚举（课堂讲解）

核心思想

当需要枚举长度固定的区间 [l, r] 时，有两种写法：

写法一：用 len 计算 r

int n, len;
for (int l = 1; l + len - 1 <= n; l++) {
    int r = l + len - 1;    // 右端点 = 左端点 + 长度 - 1
    cout << l << " " << r << endl;
}

写法二：双指针同步移动（推荐 ✅）

int n, len;
for (int l = 1, r = len; r <= n; l++, r++) {
    cout << l << " " << r << endl;
}

写法二更简洁：l 和 r 同时移动，只需保证 r ≤ n。

应用场景

• 定长滑动窗口：固定窗口大小的最大值/最小值/计数
• 定长区间统计：固定长度区间的某种属性
• 与前缀和配合：枚举区间 + 前缀和 O(1) 查询

---

📊 今日错题分析

1. P655：第一次 TLE（时间超限），第二次 AC

   • 原因：筛的范围不够或循环效率问题
   • 教训：筛法上限要设够大，查询循环到 sqrt(n) 就行

2. P910：第一次 80 分，第二次 100 分

   • 可能遗漏了 P=Q 的情况（只算一次不算两次）

---

🔑 核心模板速记

1. 素数筛法

bool isP[N]; // 0=素数, 1=合数
isP[0] = isP[1] = 1;
for (int i = 2; i <= N; i++)
    if (!isP[i])
        for (int j = i*2; j <= N; j += i)
            isP[j] = 1;

2. GCD 相关

int g = __gcd(a, b);         // 最大公约数
int l = a / __gcd(a,b) * b;  // 最小公倍数（先除后乘！）

3. 枚举因子（到 sqrt）

for (int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
        // i 是因子
        // n / i 也是因子
    }
}

4. 前缀和计数

// s[i] = s[i-1] + (满足条件 ? 1 : 0)
// 区间 [l,r] 满足条件的个数 = s[r] - s[l-1]
s[i] = s[i-1] + (a[i] % 2 == 0);

5. 定长区间枚举

for (int l = 1, r = len; r <= n; l++, r++) {
    // [l, r] 是长度为 len 的区间
}