扩展欧几里得算法实战：从ICPC竞赛题看模运算与等差数列的优雅结合
当一道ICPC竞赛题将等差数列求和与模运算结合时，许多选手会陷入公式推导的迷雾。2022年杭州站A题《Modulo Ruins the Legend》正是这样一个典型案例——它要求我们在模运算环境下，找到等差数列叠加后表达式的最小可能值。这道题的精妙之处在于，它完美展示了扩展欧几里得算法（exgcd）如何成为解决复杂数论问题的瑞士军刀。
1. 问题本质与数学模型转化
原题给出一个长度为n的数列，要求找到两个参数s和d，使得新构造的等差数列s, s+d, s+2d,..., s+(n-1)d与原数列对应项相加后，总和在模m下的值最小。这看似是简单的数学问题，实则暗藏三个关键难点：
- 模运算的非线性特性：模运算破坏了常规代数运算的线性性质，使得直接套用公式变得困难
- 双变量优化：需要同时优化s和d两个参数，增加了问题复杂度
- 整数解约束：所有解必须为整数，排除了连续优化的可能性
通过数学推导，我们可以将问题转化为求表达式的最小值：
(s·n + d·n(n+1)/2 + sum) mod m其中sum是原数列总和。这个转化将原问题抽象为标准的数论问题，为后续应用exgcd铺平了道路。
提示：在竞赛数学中，将具体问题抽象为已知数学模型的能力，往往比解题技巧本身更重要
2. 扩展欧几里得算法的核心作用
扩展欧几里得算法不仅是求最大公约数（gcd）的工具，更是解线性同余方程的利器。在本问题中，它分三个阶段发挥作用：
2.1 最大公约数的桥梁作用
首先观察到表达式中的系数n和n(n+1)/2存在固有联系。计算它们的gcd：
def gcd(a, b): while b: a, b = b, a % b return a d = gcd(n, n*(n+1)//2)这个d将成为连接两个变量的纽带，让我们能将双变量问题简化为单变量问题。
2.2 同余方程的构造与求解
通过变量替换，原表达式可转化为(k·d + sum) mod m的形式。此时需要解关于k的方程：
k·d ≡ target (mod m)这正是exgcd的典型应用场景。算法不仅能判断方程是否有解，还能给出特解：
ll exgcd(ll a, ll b, ll &x, ll &y) { if(!b) { x=1, y=0; return a; } ll d = exgcd(b, a%b, x, y); ll t = x; x = y; y = t - y*(a/b); return d; }2.3 最小非负解的确定
exgcd给出的解通常不是最小非负解，需要通过模运算调整：
k = (k % (m/g) + (m/g)) % (m/g);这个步骤确保了我们在无穷多解中找到符合题目要求的最优解。
3. 算法实现的关键步骤拆解
让我们用具体代码展示如何将数学推导转化为实际解决方案。以下是核心实现流程：
- 输入处理与初始计算
ll n, mod; cin >> n >> mod; ll sum = 0; for(int i=1; i<=n; i++) { ll t; cin >> t; sum += t; } sum %= mod; // 预先取模简化计算- 系数准备与gcd计算
ll a = n, b = n*(n+1)/2; ll s, dt; ll d = exgcd(a, b, s, dt); // 同时得到gcd和系数关系- 解同余方程
ll k, t; ll g = exgcd(d, mod, k, t); // 解k·d ≡ target mod m ll z = (mod - sum + g - 1) / g; // 计算最优z值 k = (k * z) % mod;- 回代求原始参数
s = ((s%mod * k)%mod + mod)%mod; dt = ((dt%mod * k)%mod + mod)%mod;- 结果输出
cout << (z*g + sum - mod) << endl; // 最小值 cout << s << " " << dt << endl; // 对应参数4. 数学证明与边界情况分析
为确保解的正确性，我们需要严谨的数学证明。关键点在于理解为什么最小值可以表示为(z·g + sum - mod)。
定理：对于表达式(k·d + sum) mod m，当k·d ≡ (m - sum) mod g时取得最小值，其中g = gcd(d,m)。
证明过程可分为两步：
表达式变形：
(k·d + sum) mod m = (k·d mod m + sum mod m) mod m = (k·d + t·m + sum mod m) mod m最小值条件： 令g = gcd(d,m)，根据裴蜀定理，k·d + t·m可以表示任意g的倍数。因此当：
k·d + t·m = z·g ≥ (m - sum mod m)时，表达式取得最小值(z·g + sum mod m - m)
边界情况需要特别注意：
- 当g不整除(m - sum mod m)时，向上取整确保不等式成立
- 当sum ≡ 0 mod m时，最小值直接为0
- 当n=1时，问题退化为简单模运算
5. 竞赛实战技巧与优化策略
在实际比赛中，除了算法正确性，实现细节也至关重要。以下是经过多个ICPC区域赛验证的优化建议：
预处理技巧：
- 预先计算n(n+1)/2，避免重复计算
- 尽早对sum取模，减少后续计算量
- 使用快速输入输出（如ios::sync_with_stdio优化）
常见错误防范：
# 错误示例：忽略负数解的处理 s = (s * k) % mod # 可能得到负数 # 正确做法：确保结果非负 s = ((s % mod * k % mod) + mod) % mod复杂度分析：
- exgcd的时间复杂度为O(log min(a,b))
- 整体算法复杂度为O(n + log n)，完全满足竞赛要求
- 空间复杂度为O(1)，仅需常数额外空间
6. 扩展应用与思维训练
掌握这道题的解法后，可以解决一系列类似问题。例如：
模线性方程组求解：
# 解方程组 x ≡ a1 mod m1, x ≡ a2 mod m2 def solve_crt(a1, m1, a2, m2): g, p, q = exgcd(m1, m2) if (a2 - a1) % g != 0: return None lcm = m1 // g * m2 x = (a1 + (a2 - a1)//g * p % (m2//g) * m1) % lcm return x离散对数问题： Baby-step Giant-step算法中也需要exgcd来求模逆元
组合数学问题： 大数组合数取模时，需要用exgcd计算分母的模逆元
在实际训练中，建议尝试以下变种题目巩固理解：
- 将等差数列改为等比数列
- 修改模数为合数或质数
- 增加多个变量和约束条件
理解这类问题的核心在于识别数学模型背后的数论结构——当看到模运算与线性表达式的组合时，exgcd往往就是那把关键的解题钥匙。
