从一道ICPC杭州站A题，彻底搞懂exgcd和gcd在取模问题中的实战应用-编程阁

从ICPC杭州站A题解密exgcd与gcd在模运算中的实战技巧

数论算法在竞赛编程中往往扮演着"钥匙"的角色——看似晦涩难懂，却能四两拨千斤地解决那些让暴力解法束手无策的问题。2022年ICPC杭州站的A题《Modulo Ruins the Legend》正是这样一道典型例题，它将扩展欧几里得算法（exgcd）和最大公约数（gcd）的应用展现得淋漓尽致。本文将带您深入这道题的数学内核，掌握模运算场景下求表达式最小值的通用解法。

1. 问题背景与数学模型转化

题目给出一个长度为n的整数序列，要求找到两个整数s和d，使得表达式(s×n + d×n(n+1)/2 + sum) % m的值最小。其中sum是原序列所有元素之和。这看似简单的需求背后，隐藏着三个关键数学挑战：

模运算的非线性特性：模运算打破了常规代数运算的线性性质，使得直接求极值的方法失效
多变量耦合：s和d两个变量相互影响，需要同时考虑
整数解约束：所有解必须为整数，排除了连续优化的可能性

通过观察，我们可以将原问题转化为寻找满足特定条件的整数k，使得(k×d + sum) % m最小，其中d是n和n(n+1)/2的最大公约数。这一步转化至关重要，它将双变量问题简化为单变量问题。

关键推导步骤：

原式 = (s×n + d×n(n+1)/2 + sum) % m 令 d = gcd(n, n(n+1)/2) 则存在整数k使得 s×n + d×n(n+1)/2 = k×d 因此转化为求 (k×d + sum) % m 的最小值

2. gcd与模运算的深层联系

最大公约数在这个问题中扮演着桥梁的角色。通过gcd的性质，我们可以将问题进一步简化：

计算d = gcd(n, n(n+1)/2)，这代表了线性组合可能达到的最小步长
计算g = gcd(d, m)，这决定了在模m下能够达到的最小增量

重要性质表格：

数学概念	符号表示	实际意义
序列长度	n	决定问题规模的基础参数
三角数	n(n+1)/2	产生等差数列求和的关键项
组合gcd	d	连接s和d变量的纽带
模gcd	g	决定最终解精度的核心参数

当我们将问题转化为(k×d + sum) % m后，可以利用模运算的性质将其拆解：

(k×d + sum) % m = (k×d % m + sum % m) % m = (k×d + t×m + sum%m) % m （其中t为任意整数）

3. exgcd的实战应用解析

扩展欧几里得算法在这里的作用是求解关键系数。我们需要理解其每一步的数学含义：

基础exgcd求解：首先用exgcd求出满足s×n + dt×n(n+1)/2 = k×d的系数s和dt
模方程求解：再用exgcd求解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 tx = x; x = y, y = tx - y * (a / b); return d; }

这个递归实现有三个关键点：

基准情况：当b=0时，直接返回a作为gcd，x=1,y=0作为特解
递归过程：不断交换a和b的位置，同时更新系数
系数更新：通过y = tx - y * (a / b)维护贝祖等式成立

4. 最小值求解的完整推导

通过前述步骤，我们最终将问题转化为求(z×g + sum%m) % m的最小值，其中g=gcd(d,m)。这里需要分情况讨论：

当z×g + sum%m < m时，表达式值就是z×g + sum%m，最小可能值为g
当z×g + sum%m ≥ m时，表达式值为z×g + sum%m - m，可以取得更小的值

最优解求法：

z = ceil((m - sum%m) / g) 最小值 = z×g + sum%m - m

这个结果的直观解释是：我们寻找最小的z使得z×g刚好超过m - sum%m，这样取模后就能得到最接近0的负值（在模运算中等价于较大的正值）。

5. 完整解题代码与关键注释

结合所有推导，下面是完整的C++实现，包含关键步骤注释：

#include <bits/stdc++.h> using namespace std; typedef long long ll; 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; } int main() { ll n, m, sum = 0; cin >> n >> m; for (int i = 0; i < n; i++) { ll x; cin >> x; sum += x; } ll a = n, b = n * (n + 1) / 2; ll s, dt; ll d = exgcd(a, b, s, dt); // 求出初始系数 sum %= m; ll k, t; ll g = exgcd(d, m, k, t); // 解模方程 ll z = (m - sum + g - 1) / g; // 等价于ceil((m-sum)/g) k = (k % m * z % m + m) % m; // 调整k的范围 s = ((s % m) * (k % m)) % m; dt = ((dt % m) * (k % m)) % m; // 计算最终系数 cout << (z * g + sum - m) << endl; // 输出最小值 cout << s << " " << dt << endl; // 输出s和d的解 return 0; }

关键变量说明：