企业官网建设流程全解析

1. 先把几何擦干净：面积等于 1 到底在说什么

1.1 叉积是这道题唯一需要的几何知识

拿到 ABC340 的 F 题，第一反应不该是写代码，而是把题目里那句"三角形面积为 1"翻译成自己能算的东西。题目给的是三个点：(0, 0)、(X, Y)、(A, B)，前两个点固定，第三个点要我们自己造。很多人在这里下意识去想海伦公式，一条边一条边地算长度，然后开根号——这条路在这道题上是死路，因为一旦出现根号，你就再也回不到整数域了，而题目要求的 A、B 必须是整数。

正确的入口是叉积。平面上三个点确定的三角形，有向面积的绝对值等于：

S = |X * B - Y * A| / 2

这个式子不需要开根号，不需要求边长，两个坐标叉乘相减就完事。我个人的习惯是：只要题目涉及到坐标、格点、面积，先写叉积，别犹豫。这道题更是如此，因为叉积公式里的X * B - Y * A正好是一个关于 A、B 的线性表达式，而线性表达式意味着我们可以用数论工具去解它——这才是这道题真正的题眼。

顺带说一句，格点三角形的面积一定是 0.5 的整数倍，这一点用 Pick 定理（S = I + B/2 - 1）可以直接看出来，边界点数 B 和内部点数 I 都是整数，所以面积只能是半整数。也就是说，"面积恰好为 1"这个条件在格点上并不罕见，它是可以达到的，出题人没有为难你。

1.2 为什么目标值一定是 ±2

把S = 1代进去，得到|X * B - Y * A| = 2。去掉绝对值，就是两条方程：

X * B - Y * A = 2 X * B - Y * A = -2

这两条本质上没有区别，因为如果把解 (A, B) 整体取反变成 (-A, -B)，等式左边正好变号。所以我后面统一按= 2处理，如果算出来的解是负的，取反一样合法。

这里有个细节值得强调：为什么不能是 ±1 或者 ±3。因为叉积算出来的是"两倍面积"，所以面积是 1 就意味着叉积是 2。如果把题目改成"面积为 2"，那方程右边就是 4；改成"面积为 0.5"，右边是 1。搞清楚这个换算关系，你以后遇到面积类题目就不会被"半格"这种字眼绕晕。

从整数角度看，X * B - Y * A = 2是一条带两个未知数的线性方程。两个未知数、一条方程，解要么一个都没有，要么有无穷多个。判断"有没有"，靠的是最大公约数；找到"某一个"，靠的是扩展欧几里得。这道题的整个技术栈就这么两件事，没有第三个知识点。

1.3 题目真正问的是"你能不能凑出 2"

我见过不少人卡在这题，卡点不在算法，而在心理上——他们觉得"要求输出一个具体的点，这怎么做"，然后开始尝试各种特判、各种构造。其实换个说法就通了：

已知两个整数 X、Y，问能不能找到整数 B、A，使得X * B - Y * A = 2。

这就是一道最标准的二元一次不定方程题。你甚至不需要知道几何，只要会解这个方程，答案自然就有了。我第一次做的时候，是先把它当纯代数题解出来，最后才回头验证几何意义，这样思路反而更干净。

再补一句数据范围的解读：题目给出的 |X|、|Y| 上限是 10 的 9 次方，这个量级说明两件事。第一，暴力枚举 A、B 是不可能过的，必须用对数级别的算法；第二，中间结果会在 10 的 9 次方到 10 的 18 次方之间，用 64 位整数足够，不需要高精度。很多人看到 10 的 9 次方就紧张，其实这恰好是"long long 完全放得下"的舒服区间。

2. 贝祖定理：存在性由 gcd 一个人说了算

2.1 用硬币凑钱来理解 gcd 的支配地位

假设你手里只有面值 6 元和 9 元的硬币（这里只是打比方，现实里当然没有这种面值，重点在数学结构），你能凑出的金额有哪些？6、9、12、15、18……你会发现凑出来的永远是 3 的倍数。这个 3 就是 gcd(6, 9)。反过来，3 本身能不能凑出来？能，9 - 6 = 3。

这就是贝祖定理（Bézout's identity）的全部内容：对于不全为零的整数 a、b，所有形如a * x + b * y的整数构成的集合，恰好等于 gcd(a, b) 的所有倍数。换句话说：

• 如果 d = gcd(a, b)，那么方程a * x + b * y = c有整数解，当且仅当 d 整除 c；
• 有解的时候，解的个数是无穷多，因为你可以对 x 加上 b/d、对 y 减去 a/d，等式恒成立。

套到这道题上：方程是X * B - Y * A = 2，把 -Y 看成第二个系数，那么 g = gcd(X, Y)（取绝对值）。2 能被 g 整除才有解。g 只可能是 1 或者 2 才有戏；如果 g ≥ 3，直接输出 -1，一行代码结束。

这个判断条件很多人写成了2 % g != 0就完事了，但要注意 g 可能是负数，取模的行为在不同语言里不一样，这个坑我在第 4 节会专门拆开讲。

2.2 扩展欧几里得到底多返回了什么

普通欧几里得算法只告诉你 gcd 是多少，扩展版多返回两个数。它的目标是：给定 a、b，求出 (x, y) 使得

a * x + b * y = gcd(a, b)

递归的推法其实很好记。当 b = 0 的时候，gcd(a, 0) = a，而a * 1 + 0 * 0 = a，所以直接返回 x = 1、y = 0。

当 b ≠ 0 的时候，设已经递归求出：

b * x' + (a mod b) * y' = g

把a mod b换成a - (a / b) * b（这里的除法是整除），代入整理：

b * x' + (a - (a / b) * b) * y' = g a * y' + b * (x' - (a / b) * y') = g

对照a * x + b * y = g，就得到：

x = y' y = x' - (a / b) * y'

这就是那句著名的回溯公式。写代码的时候，模板长这样：

long long extgcd(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } long long g = extgcd(b, a % b, y, x); // 注意这里 x、y 是交换着传的 y -= (a / b) * x; return g; }

extgcd(b, a % b, y, x)这一行是很多人的第一个坎——为什么传参的时候把 x 和 y 换了个位置？因为递归回来后，新一层的 x' 对应的是上一层的 y，直接在传参时就交换，省掉一次临时变量赋值。这个技巧我第一次见的时候也愣了两秒，后来自己手推一遍递归树就彻底明白了。

2.3 把 g 放大成 2 才是最后一步

假设 g = gcd(X, Y) 能整除 2，那么令k = 2 / g。exgcd 给出来的 (u, v) 满足：

X * u + (-Y) * v = g

两边同乘 k：

X * (u * k) + (-Y) * (v * k) = k * g = 2

对照X * B - Y * A = 2，直接读出来：

B = u * k A = v * k

到这里就结束了，一行输出两个数。这一步一定要自己代回去验算，我在第 3 节会给出具体的验算方法。因为 A、B 的对应关系特别容易搞反——有人写成A = u * k, B = v * k，交上去 WA 一片，还以为是算法错了，其实就是一个下标的疏忽。

顺便说一个很实用的观察：k 只能是 1 或 2（因为 g 只能是 1 或 2），所以缩放这一步连乘法溢出都不用担心。哪怕 u、v 顶到 10 的 9 次方，乘个 2 也就 2×10 的 9 次方，long long 的容量是 9×10 的 18 次方，安全得很。

3. 从模板到 AC：两版实现和上线前的自检

3.1 C++ 版本：把符号问题一次性处理干净

#include <bits/stdc++.h> using namespace std; long long extgcd(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } long long g = extgcd(b, a % b, y, x); y -= (a / b) * x; return g; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long X, Y; cin >> X >> Y; long long P = X, Q = -Y; long long u, v; long long g = extgcd(P, Q, u, v); // 把 gcd 统一成正数，同步翻转解，等式依然成立 if (g < 0) { g = -g; u = -u; v = -v; } if (2 % g != 0) { cout << -1 << "\n"; return 0; } long long k = 2 / g; cout << v * k << " " << u * k << "\n"; return 0; }

我在代码里多做了一个动作：把 P、Q 的构造和 A、B 的读取分开写。也就是先令P = X、Q = -Y，让方程变成标准的P * u + Q * v = g形式，最后再从 v 读出 A、从 u 读出 B。多写两行变量，换来的是符号上不容易出错，我觉得很值。

关于g < 0的处理，这里解释一下为什么需要。C++ 的递归版 exgcd 在 b = 0 时直接返回 a，如果 a 本身是负数（比如 X = 0、Y = -6 时 Q = 6、P = 0，或者反过来），返回的 g 就是负的。虽然从代数上讲负数 gcd 也能用（等式照样成立），但后面那句2 % g != 0读起来就很不直观，而且k = 2 / g会变成负数，输出结果看着别扭。统一翻正，是为了让后面所有判断都在非负数域里做，脑子清爽。翻转的依据很简单：P * u + Q * v = g两边同乘 -1，就变成P * (-u) + Q * (-v) = -g，等式依然成立。

还有个小防御值得加：题目保证 (X, Y) ≠ (0, 0)，所以 P、Q 不可能同时为 0，g 一定不是 0，2 % g不会炸。但如果你是在刷题平台上把它当模板题练手，最好自己心里有这个前提，别把2 % g用在 g 可能为 0 的地方。

3.2 Python 版本：迭代写法避开递归的符号坑

import sys def extgcd(a, b): old_r, r = a, b old_s, s = 1, 0 old_t, t = 0, 1 while r != 0: q = old_r // r old_r, r = r, old_r - q * r old_s, s = s, old_s - q * s old_t, t = t, old_t - q * t return old_r, old_s, old_t def main(): X, Y = map(int, sys.stdin.read().split()) P, Q = X, -Y g, u, v = extgcd(P, Q) if g < 0: g, u, v = -g, -u, -v if 2 % g != 0: print(-1) return k = 2 // g print(v * k, u * k) main()

这里用迭代版而不是递归版，理由有两个。一是 Python 的递归默认上限是 1000，虽然 exgcd 的深度只有 O(log) 级别，理论上够用，但迭代版完全没有这个心理负担。二是迭代版把"商、余数、系数"三组量放在一起更新，形式对称，读完其实就是欧几里得算法的矩阵形式，比递归更接近本质。

语言差异带来的一个坑必须提：Python 的//是向下取整，C++ 的/是向零取整。对4 // 6这种正数场景没区别，但遇到-4 // 6，Python 给 -1，C++ 给 0。这个差异在 exgcd 里会不会出问题？不会，因为迭代版维持的不变式old_s * a + old_t * b = old_r对任意取整方式都成立，只要商和余数自洽。但如果你把 C++ 的递归模板直接翻译成 Python 却不改这一段细节，就容易出现系数对不上、等式差一个 a 或 b 的情况。我在这里踩过一次，排查了二十多分钟才发现是除法语义的问题。

3.3 提交前必须跑的本地验算

算法对了不代表结果对，因为 A、B 的对应关系、符号翻转这些地方全靠人工把握。我给自己定了个规矩：这类"构造一组解"的题，写完必须跑一遍验证脚本。

def verify(X, Y, A, B): if A == B == -1: return True # 输出 -1 时单独检查 return abs(X * B - Y * A) == 2

除了验证代码本身的输出，我还会在 |X|、|Y| ≤ 30 的范围内做一次存在性对拍：对于每一对 (X, Y)，用暴力枚举 A、B（比如 -200 到 200）判断是否有解，再和程序的输出对照。如果暴力说有解而程序输出 -1，或者暴力说无解而程序给了个点，那就肯定是判定条件写错了。

这个对拍做一遍只要十几秒，但能拦住 90% 的低级错误。具体操作是这样：先跑暴力生成期望答案表，再跑自己的程序生成实际答案表，逐行 diff。我一般会顺手检查两件事：一是面积为 1 的那些点到底长什么样，二是当 X、Y 之一是 0 的时候程序表现如何（这个边界我在下面会单独说）。

再给几个手算样例，方便你贴上去自测：

表格里"任意合法值"的意思是解有无穷多组，程序输出的哪一组都算对，只要代入验算成立即可。这一点是这道题比较友好的地方，不用去纠结最小解、字典序最小这类额外条件。

4. 踩坑实录：这道题最容易翻车的六个地方

4.1 符号错位：A 和 B 谁配 v，谁配 u

这是最高频的错误，没有之一。方程的左边是X * B - Y * A，B 配 X、A 配 Y，而且中间是减号。你在构造P * u + Q * v的时候，如果令P = X、Q = Y，那对应的就是B = u、A = -v；如果令P = X、Q = -Y，那就是B = u、A = v。两种写法都行，但千万别混着用。

我自己的做法是固定一种：永远把第二个系数取反，让方程变成纯加法形式，这样读系数的时候不用在脑子里做减法。写完之后立刻代回去做一次符号检查，X * B - Y * A算出来必须等于 2 或 -2，等于别的数就说明配错了。

4.2 负数 gcd 与取模判断

前面提过，递归版 exgcd 返回的 g 符号不一定是正的。C++ 里2 % (-1)结果是 0，2 % (-2)也是 0，所以2 % g != 0这个判断其实对负 g 也阴差阳错地成立。但这属于"碰巧对"，不是"设计对"，换个数就不行了。比如你以后要解X * B - Y * A = 3，3 % (-2)在 C++ 里是 1（因为余数符号跟随被除数），判断结果一样；但在 Python 里3 % -2是 -1，也是非零，结果碰巧也一致。可如果目标值是 6，6 % (-4)在 C++ 里是 2，非零，判断"无解"是对的，因为 4 确实不整除 6。你看，到处都是碰巧，早晚翻车。

稳妥做法：算法一拿到 g，立刻翻正，后面的所有判断都在正数域里做。这三行代码是保险，不是多余。

4.3 溢出：long long 到底够不够

先说结论：够，而且有相当大的余量。理由是这样：exgcd 返回的解 (u, v) 有一个已知的上界，|u| ≤ |Q| / (2g)、|v| ≤ |P| / (2g)（当 a、b 都非零时）。P、Q 最大是 10 的 9 次方，g 至少是 1，所以 |u|、|v| 最多到 5×10 的 8 次方，乘上 k（最大 2）之后是 10 的 9 次方量级。整个过程中最坏情况大概在 2×10 的 9 次方上下，离 long long 的上限还有九个数量级的距离。

真正需要小心的不是最终答案，而是中间那一句y -= (a / b) * x。当 a 很大、b 很小的时候，a / b可能是 10 的 9 次方这个量级，而 x 也可能是 10 的 9 次方，乘起来是 10 的 18 次方——刚好在 long long 边界附近晃。这一项如果写成 int，直接爆掉；写成 long long，勉强安全。所以模板里所有参数、返回值、中间变量，清一色 long long，不要图省事用 int。

4.4 特判写多了反而引入新 bug

有人一看 X 或 Y 等于 0，立刻加一堆特判：X = 0 时怎么怎么样，Y = 0 时怎么怎么样。其实 exgcd 本身对 0 是完全兼容的，extgcd(0, b)会正常返回 g = |b| 和一组系数，根本不需要额外处理。

我实测过 X = 0、Y = 2 的情况：P = 0、Q = -2，exgcd 返回 g = -2、u = 0、v = 1，翻正后 g = 2、u = 0、v = -1，k = 1，输出 A = -1、B = 0。代回去：0 * 0 - 2 * (-1) = 2，面积正好 1，完全正确。如果 X = 0、Y = 6，g = 6，2 不被 6 整除，输出 -1，也符合"|6A| = 2 无整数解"的推理。

所以我的建议是：能不特判就不特判。每多一个分支，就多一个出错的地方，而 exgcd 的通用性足以覆盖这些边界。真正需要特判的只有一处：题目保证 (X, Y) ≠ (0, 0)，如果你的代码里没有这个保证，才需要防一下 g = 0。

4.5 输出格式与"多解"的心态

题目的输出要求是两个整数，用空格隔开。看着简单，但两个细节容易丢分：一是 spj（特判评测）的题目，输出的解只要合法就给分，不要纠结"我算出来的是不是标准答案"；二是输出 -1 的时候只输出一个数，别手滑多打了空格或者换行之外的东西。

还有一点心态问题。构造类题目的答案不唯一，很多人做完了心里不踏实，总觉得"是不是该输出更小的解"。这道题没有这个要求，你就大大方方输出 exgcd 给的原始解，代回去验证成立就行。

4.6 速查表：症状与病因对照

5. 顺带学一招：Ax + By = C 的通用套路

5.1 通解结构与最小正整数解

A * x + B * y = C这类方程，只要 gcd(A, B) 整除 C，就一定有解，而且解的全体可以写成：

x = x0 + (B / g) * t y = y0 - (A / g) * t

其中 (x0, y0) 是一组特解（exgcd 缩放得到），t 是任意整数。这个结构很重要，因为它告诉你：解在一条"斜率为 -A/B"的直线上等距分布。你要找最小正整数解，就是解一个模方程x0 + (B/g) * t > 0，直接算出 t 的取值区间，取最小的那个就行。

我在别的题目里遇到过要求"x 和 y 都是正整数且 x + y 最小"的版本，做法就是把 t 的可行区间求出来，代入线性函数取端点。这套流程是通用的，和这道题的差别只在于目标值从 2 变成了 C。

5.2 这套模板还能用在哪

扩展欧几里得的应用面比很多人想的宽。除了这种几何构造题，它还在这些场景反复出现：

• 求解同余方程：a * x ≡ c (mod m)等价于a * x - m * y = c，两边一模一样的处理流程；当 gcd(a, m) = 1 时，x 就是 c 乘上 a 的逆元，这也是求乘法逆元的标准做法之一。
• 求逆元：模数是素数时可以直接用快速幂（费马小定理），但模数不保证是素数时，exgcd 是唯一稳妥的路子。
• 中国剩余定理的合并步骤：两个同余式合并时，本质就是解一次二元不定方程。
• 一次函数图像上的格点计数：给定线段两端点，数中间有多少个格点，答案和 gcd 直接相关。

所以这道题虽然定位是 F 题，但它的技术内核非常基础，属于"必须形成肌肉记忆"的那一类。我的建议是把它当作模板题来练——不是练这道题的思路，而是练"看到线性方程条件反射地想到 exgcd"这个反射弧。

5.3 什么时候不该硬上 exgcd

最后说个反向经验。虽然 exgcd 很万能，但不是所有"两个未知数"的题都适合它。比如：

• 如果数据范围很小（比如 X、Y ≤ 1000），枚举可能更省事，也更容易写对；
• 如果方程里出现了乘积项（比如X * A + Y * B + A * B = K），那就不线性了，得换因式分解或者枚举约数；
• 如果题目还附加了最优化目标（比如让 |A| + |B| 最小），光有特解不够，还得做一轮区间分析。

判断标准很简单：看方程对未知数是不是一次的。是，就丢给 exgcd；不是，赶紧换思路，别在一条路上耗到比赛结束。

我个人做这类题的习惯是，先把几何翻译成代数，再用 gcd 判断存在性，最后用 exgcd 求特解，三步走完通常不到十分钟。真正的耗时往往在最后一步的符号核对上——所以别省那一次代入验算，它比任何调试手段都便宜。