1. 整数求和问题（导引）

问题描述

计算1到n的和，n ≤ 15万。

解决方案

方法一：循环累加

int sum = 0;
for (int i = 1; i <= n; i++) {
    sum += i;
}

时间复杂度：O(n)

方法二：高斯公式

// 直接计算：可能溢出
long long sum = n * (n + 1) / 2;

// 安全版本：防止溢出
long long sum;
if (n % 2 == 0) {
    sum = (n / 2) * (n + 1);
} else {
    sum = ((n + 1) / 2) * n;
}

关键点

• 注意数据范围，防止整数溢出
• 掌握先除后乘的技巧

2. 最小公倍数（LCM）

问题描述

求两个正整数的最小公倍数。

数学原理

LCM(a, b) = a × b / GCD(a, b)

辗转相除法求最大公约数

// 循环实现
int gcd(int a, int b) {
    while (b != 0) {
        int temp = a % b;
        a = b;
        b = temp;
    }
    return a;
}

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

防止溢出的LCM计算

int lcm(int a, int b) {
    return a / gcd(a, b) * b;  // 先除后乘
}

3. n的n次方个位数

问题描述

求n^n的个位数，n ≤ 1000。

解决方案

方法一：改进的暴力法

int result = 1;
for (int i = 0; i < n; i++) {
    result = (result * n) % 10;  // 每次只保留个位
}

方法二：找规律法

• 个位数存在循环节（周期为4）
• 利用抽屉原理证明循环的存在性

4. 非波那契数列变种

问题描述

判断f(n) = f(n-1) + f(n-2)，f(0)=7, f(1)=11能否被3整除。

解决方案

// 利用模运算性质
int a = 7 % 3, b = 11 % 3;
for (int i = 2; i <= n; i++) {
    int temp = (a + b) % 3;
    a = b;
    b = temp;
}
// 检查b是否为0

关键点

• 利用模运算避免大数计算
• 发现循环节（周期为8）

5. 快速幂运算

问题描述

求a^b的最后三位数（模1000）。

递归实现

long long quick_pow(long long a, long long b, long long mod) {
    if (b == 0) return 1;
    long long half = quick_pow(a, b/2, mod);
    long long result = half * half % mod;
    if (b % 2 == 1) result = result * a % mod;
    return result;
}

迭代实现

long long quick_pow(long long a, long long b, long long mod) {
    long long result = 1;
    while (b > 0) {
        if (b & 1) result = result * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return result;
}

6. 二分查找

循环实现

int binary_search(int arr[], int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == x) return mid;
        else if (arr[mid] < x) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

递归实现

int binary_search(int arr[], int left, int right, int x) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (arr[mid] == x) return mid;
    else if (arr[mid] < x) 
        return binary_search(arr, mid + 1, right, x);
    else 
        return binary_search(arr, left, mid - 1, x);
}

7. 二分法求解方程

问题描述

求8x^4 + 7x^3 + 2x^2 + 3x + 6 = y在[0,100]内的根。

解决方案

double f(double x) {
    return 8*pow(x,4) + 7*pow(x,3) + 2*pow(x,2) + 3*x + 6;
}

double solve(double y) {
    double left = 0, right = 100;
    while (right - left > 1e-6) {
        double mid = (left + right) / 2;
        if (f(mid) < y) left = mid;
        else right = mid;
    }
    return (left + right) / 2;
}

8. 三分法求函数极值

适用场景

单峰函数（凸函数）的极值问题。

算法框架

double ternary_search(double left, double right) {
    while (right - left > 1e-6) {
        double left_third = left + (right - left) / 3;
        double right_third = right - (right - left) / 3;
        
        if (f(left_third) < f(right_third)) {
            left = left_third;
        } else {
            right = right_third;
        }
    }
    return (left + right) / 2;
}

关键知识点总结

1. 数据范围敏感：时刻注意整数溢出问题
2. 数学公式转化：将复杂问题转化为数学公式
3. 模运算性质：利用模运算避免大数计算
4. 循环节思想：利用抽屉原理证明循环存在性
5. 分治思想：快速幂、二分查找、三分查找
6. 精度控制：实数运算时的终止条件

学习建议

1. 多动手实现基础算法
2. 注意边界条件和特殊情况的处理
3. 培养对时间复杂度的敏感度
4. 学会分析问题背后的数学原理
5. 多做练习，积累编程经验

这些基础算法和数学思想是后续学习更复杂算法的基石，需要扎实掌握。