核心概述
欧几里得算法与扩展欧几里得（gcd / exgcd）：用于计算两整数的最大公约数及系数 x,y 使 ax + by = gcd(a,b)；可据此求解线性丢番图方程与模逆。复杂度 O(log min(|a|,|b|))。
原文引述
Description: Computes gcd via Euclid; extended version returns (g,x,y) with ax+by=g. Supports solving ax≡b (mod m) and modular inverse when gcd(a,m)=1. Time: O(log min(|a|,|b|))
展开阐述
-
函数/接口（据实现）
- ll gcd(ll a, ll b)：返回 gcd(a,b)，可用迭代取模实现；规范为非负。
- ll exgcd(ll a, ll b, ll& x, ll& y)：返回 g=gcd(a,b)，并给出 x,y 使 ax+by=g。
- 可选：ll lcm(ll a, ll b) = a / gcd(a,b) * b（注意溢出，见 090-数论-长整型模乘）。
-
典型用法
- 线性方程 ax+by=c：
- 设 g = gcd(a,b)。若 c%g≠0 无解；否则由 exgcd 得到一组解 (x0,y0)，再缩放 c/g，并用通解 x = x0 + k·(b/g)，y = y0 − k·(a/g)。
- 模逆 inv(a, m)：
- 若 gcd(a,m)=1，则 exgcd(a,m) 得 x，使 ax+my=1，取 inv ≡ x mod m（规范到 [0,m)）。
- 若 gcd(a,m)≠1 则 a 在模 m 下无逆（但可在因子环上讨论）。
- 同余 ax ≡ b (mod m)：
- 设 g=gcd(a,m)。若 b%g≠0 无解；否则化为 (a/g)x ≡ (b/g) (mod m/g)，用上式求逆解出。
- 线性方程 ax+by=c：
-
实现要点
- gcd 迭代：while (b) { auto t=a%b; a=b; b=t; } 返回 |a|。
- exgcd 递归：exgcd(b, a%b, x1, y1)，回代 x=y1，y=x1−(a/b)*y1。
- 规范化：根据需要将 gcd 取非负；模逆结果统一到 [0,m)。
- 溢出注意：在 lcm 与中间乘法中使用 __int128 或见 090-数论-长整型模乘。
-
输出语义
- gcd(a,b)：非负最大公约数。
- exgcd(a,b)：返回 g，同时输出一组 (x,y) 使 ax+by=g。
- lcm(a,b)：最小公倍数（若 a=b=0 按需定义为 0）。
-
复杂度
- O(log min(|a|,|b|)) 步取模；exgcd 同量级。
-
使用与注意
- 对负数参数，算法同样有效；可先取绝对值并在最后按需要恢复符号。
- 在浮点环境中避免混用；所有运算用整数进行。
- 与 081-数论-中国剩余定理、088-数论-模逆、091-数论-模幂 等常配合使用。