编程竞赛高频数学算法：GCD、斐波那契与素数优化

1. 项目概述

在计算机编程竞赛和机试中，数学相关算法题占据了相当大的比重，其中最大公约数(GCD)、斐波那契数列和素数相关问题是三个最常出现的考点。这三个数学概念看似基础，但在实际应用中却有着丰富的变体和优化空间。

我参加过多次编程竞赛和担任过机试考官，发现很多考生在面对这些"基础"题目时反而容易翻车。要么是算法效率不够导致超时，要么是边界条件处理不当造成错误。本文将结合我的实战经验，深入解析这三个高频考点，提供可直接用于机试的优化代码模板，并分享那些只有踩过坑才知道的注意事项。

2. 最大公约数(GCD)深度解析

2.1 欧几里得算法原理与实现

欧几里得算法（辗转相除法）是计算两个数最大公约数的经典方法。其基本原理基于以下数学定理：gcd(a,b) = gcd(b, a mod b)。这个看似简单的定理，在实际编码中却有几个关键点需要注意。

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

// 迭代实现
int gcd_iter(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

注意：在实际机试中，建议使用迭代实现。虽然递归写法更简洁，但面对极大数时可能引发栈溢出。

2.2 边界条件与特殊处理

在实际编码中，有几个边界条件需要特别注意：

1. 当输入包含0时：gcd(a,0)=a
2. 负数处理：可以先取绝对值再计算
3. 大数运算：当数字超过int范围时，需要使用long long类型

c复制#include <stdlib.h> // for abs()

int gcd_safe(int a, int b) {
    a = abs(a);
    b = abs(b);
    if (a < b) return gcd_safe(b, a);
    return b == 0 ? a : gcd_safe(b, a % b);
}

2.3 实际应用场景

GCD不仅仅用于求最大