GESP五级 数学

一、最大公约数（GCD）与最小公倍数（LCM）

1. 欧几里得算法（辗转相除法）

• 两个数的最大公约数等于其中较小数与两数相除余数的最大公约数。即假设a%b=r,则gcd(a,b)=gcd(b,r)。

  核心公式

  gcd(a, b) = gcd(b, a % b)，终止条件：b == 0 时返回 a

两种实现

// 递归实现
int gcd(int a, int b) {
    if(b == 0) return a;
    else return gcd(b, a % b);
}

// 迭代实现（无栈溢出风险）
int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

真题考点

• 调用序列：gcd(48,18) → gcd(18,12) → gcd(12,6) → gcd(6,0)
• 时间复杂度：O(log n)，优于暴力枚举法（O(n)）
• 特性：自动处理 a < b 的情况，假如传入20和30，则r=20%30=20，a=30，b=20，会自己完成交换。

2. 最小公倍数（LCM）

• 两个数的最小公倍数等于他俩乘积除以最大公约数。

  公式

  lcm(a, b) = a * b / gcd(a, b)
  ✅ 防溢出写法：lcm(a, b) = a / gcd(a, b) * b
  ❌ 不推荐写法：a * b / gcd(a, b)（大数相乘可能溢出）

3. 暴力枚举法（对比考察）

• 实现：循环从min(a,b)往下找第一个同时整除a和b的数
• 时间复杂度：O(n)，效率远低于欧几里得算法

二、质数与唯一分解定理

1. 质数定义

大于1的整数，除了1和自身外没有其他正因数

2. 质数判断优化

（1）基础优化

循环到 sqrt(n) 即可，因为若n有大于sqrt(n)的因数，则必有一个小于sqrt(n)的因数

bool is_prime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

（2）进阶优化：6k±1法

• 原理：大于3的质数都可以表示为 6k±1 的形式

• 代码：先排除2、3、5的倍数，再按步长4和2交替检查

  bool is_prime(int n) {
    if (n <= 1) return false;
    if (n == 2 || n == 3 || n == 5) return true;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0) return false;
    int i = 7, step = 4;
    while (i * i <= n) {
        if (n % i == 0) return false;
        i += step;
        step = 6 - step; // 步长交替4和2
    }
    return true;
  }

3. 唯一分解定理

• 定义：任何大于1的整数，都可以唯一分解为有限个质数的乘积（忽略顺序）
• 正确分解示例：24 = 2×2×2×3
• 错误分解示例：36=2×3×6（6不是质数）、48=2×2×3×4（4不是质数）

4. 推论

如果大于1的整数不能被任何不超过其平方根的质数整除，那么它必定是质数

三、完全数

1. 定义

一个正整数等于它所有真因子（小于自身的正因数）的和

• 例：28的真因子是1、2、4、7、14，和为28，故28是完全数

2. 真因子求和优化

循环到 i*i <= n，同时累加 i 和 n/i（注意去重，当i == n/i时只加一次）

bool isPerfectNumber(int n) {
    if (n <= 1) return false;
    int sum = 1; // 1是所有大于1的正整数的真因子
    for (int i = 2; i * i <= n; i++) { // 高频填空：i*i <= n
        if (n % i == 0) {
            sum += i;
            if (i != n / i) sum += n / i;
        }
    }
    return sum == n;
}

四、同余

1. 定义

若整数a和b除以m的余数相同，则称a和b对模m同余，记作 a ≡ b (mod m)

• 等价条件：m | (a - b)（m能整除a-b）

五、整除特性

• 能被9整除的数：各位数字之和能被9整除
• 能被3整除的数：各位数字之和能被3整除
• 能被2整除的数：末位是偶数
• 能被5整除的数：末位是0或5

六、递归与迭代对比（必考复杂度）

易错点

• 记忆化斐波那契的时间复杂度是O(n)，不是O(2ⁿ)
• 递归的空间复杂度主要来自递归调用栈

七、真题考察点

• 完全数真因子求和循环边界：i*i <= n
• 欧几里得算法迭代版返回值：a
• 同余问题：m必须是a-b的正因数
• 唯一分解定理：只能分解为质数的乘积
• 6k±1质数判断：大于3的质数都符合该形式
• 暴力GCD时间复杂度：O(n)，欧几里得：O(log n)

• 迭代阶乘空间复杂度：O(1)，递归阶乘：O(n)