模块一：结构体与排序

1. 结构体基础

• 概念：自定义数据类型，可存储多种不同类型的数据
• 定义示例：

struct stu {
    int id;    // 学号
    int fs;    // 分数
    int wz;    // 原始位置
    int mc;    // 名次
};

2. 结构体排序（cmp函数）

• 规则：函数返回 true 时，第一个参数排在前面
• 示例1：按分数降序，分数相同按学号升序

bool cmp2(stu s1, stu s2) {
    if (s1.fs != s2.fs) {
        return s1.fs > s2.fs;  // 分数高的排前面
    } else {
        return s1.id < s2.id;  // 分数相同，学号小的排前面
    }
}

• 示例2：按原始位置升序（恢复输入顺序）

bool cmp3(stu s1, stu s2) {
    return s1.wz < s2.wz;
}

3. 经典例题

例题1：学生名次计算

• 需求：输入学生信息，按分数排名次（分数相同名次相同），最后按原始顺序输出名次
• 核心步骤：
  1. 记录原始位置 wz
  2. 按分数+学号排序（cmp2）
  3. 计算名次：分数相同则名次相同，否则名次+1
  4. 按原始位置排序恢复顺序（cmp3）
  5. 输出名次
• 关键代码：

// 计算名次
s[1].mc = 1;
for (int i = 2; i <= n; i++) {
    if (s[i].fs == s[i - 1].fs) 
        s[i].mc = s[i - 1].mc;
    else 
        s[i].mc = s[i - 1].mc + 1;
}

例题2：战斗爽！（士兵师徒关系）

• 需求：计算每个士兵能当多少人的老师（战斗力更高且无矛盾）
• 核心步骤：
  1. 记录原始位置 wz
  2. 按战斗力升序排序
  3. 计算初始可当老师数量：战斗力更高则数量为 i-1，否则与前一个相同
  4. 按原始位置恢复顺序
  5. 处理矛盾关系：每对矛盾中，战斗力高的士兵可当老师数量-1
• 关键代码：

// 计算初始可当老师数量
s[1].r = 0;
for (int i = 2; i <= n; i++) {
    if (s[i].zdl > s[i - 1].zdl) {
        s[i].r = i - 1;
    } else {
        s[i].r = s[i - 1].r;
    }
}

模块二：质数相关算法

1. 质数定义

• 质数（素数）：因数只有1和它本身的数
• 注意：1既不是质数也不是合数

2. 试除法判断质数（开根号优化）

• 原理：若 a = b * c 且 b <= c，则必有 b <= sqrt(a)，c >= sqrt(a)
• 时间复杂度：O(√a)
• 代码：

bool isPrime(int a) {
    if (a <= 1) return 0;  // 1及以下不是质数
    int tem = sqrt(a);
    for (int i = 2; i <= tem; i++) {
        if (a % i == 0) return 0;  // 能被整除，不是质数
    }
    return 1;  // 是质数
}

3. 试除法求因数总和

• 原理：遍历到 sqrt(a)，若 i 是因数，则 a/i 也是因数（注意避免重复加 i == a/i 的情况）
• 代码：

int factorSum(int a) {
    if (a <= 1) return a;
    int tem = sqrt(a), sum = 0;
    for (int i = 1; i <= tem; i++) {
        if (a % i == 0) {
            sum += i;
            if (i != a / i) sum += a / i;  // 避免重复
        }
    }
    return sum;
}

4. 埃氏筛法（快速筛质数）

• 原理：若一个数是合数，它一定可以写成若干个质因数相乘；从2开始，把每个质数的倍数标记为合数
• 适用场景：筛选1e7以内的质数
• 代码：

const int MAX = 1e7 + 10;
bool isNotPrime[MAX];  // isNotPrime[i]=0表示i是质数，1表示合数

void eratosthenes() {
    isNotPrime[1] = 1;  // 1不是质数
    for (int i = 2; i <= 1e7; i++) {
        if (isNotPrime[i] == 0) {  // 如果i是质数
            for (int j = 2; i * j <= 1e7; j++) {
                isNotPrime[i * j] = 1;  // 标记i的倍数为合数
            }
        }
    }
}

• 算法选择建议：
  • 筛选1e7以内质数 → 埃氏筛
  • 判断少量大数（1e9~1e10）是否为质数 → 试除法（开根号优化）