平面上有一个棋子在 (0,0),每次操作可以将其从 (x,y) 移动到 (x′,y′) 当且仅当满足以下条件之一:
- ∣x−x′∣=A 且 ∣y−y′∣=B。
- ∣x−x′∣=B 且 ∣y−y′∣=A。
给定 A,B,X,Y,问能否将其移动到 (X,Y),若能则求最小操作次数,多组测试数据。
数据范围:1≤T≤2×105,1≤A,B≤106,0≤X,Y≤106。
扩展欧几里得算法
首先,我们取 g=gcd(A,B),若 g>1,我们将 A,B,X,Y 同时除以 g,显然结果不变,所以下面仅讨论 A,B 互质的情况。 我们将总次数分为 k1+k2,分别表示操作 1 和操作 2 的执行次数,显然全部取完以后横纵坐标变化量可以用 A⋅p1,B⋅p2,B⋅q1,A⋅q2 表示,即:
{A⋅p1+B⋅p2=XB⋅q1+A⋅q2=Y
还有什么条件呢?注意到每次操作系数仅能是 ±1,所以 p1≡q1≡k1(mod2),p2≡q2≡k2(mod2)。
也就是说,我们要在上面的条件下求 min(k1+k2)。
还有一个小问题,假如已经有了 p1,q1,那么最少需要操作多少次?显然,由于同奇偶,下界次数为 max(∣p1∣,∣q1∣) 并且这个下界可以取到(多余用正负抵消)。
所以 k1=max(∣p1∣,∣q1∣),k2=max(∣p2∣,∣q2∣),则总次数为:
max(∣p1∣,∣q1∣)+max(∣p2∣,∣q2∣)
现在我们开始考虑如何求 p1,p2,q1,q2,发现由于 p1≡q1≡k1(mod2),又因为 k1=max(∣p1∣,∣q1∣),产生了循环依赖,考虑进行固定奇偶性。
Trick:固定奇偶性
考虑直接枚举 k1,k2 的奇偶性,具体的,令 c1=k1mod2∈{0,1},c2=k2mod2∈{0,1},对于 (c1,c2),我们将 p,q 写为:
p1=2x1+c1,q1=2y1+c1p2=2x2+c2,q2=2y2+c2
其中 x,y∈Z,重新带入坐标方程:
{A(2x1+c1)+B(2x2+c2)=XB(2y1+c1)+A(2y2+c2)=Y
现在的答案为:
max(∣2x1+c1∣,∣2y1+c1∣)+max(∣2x2+c2∣,∣2y2+c2∣)
我们要在坐标方程的约束下最小化答案,由于 gcd(A,B)=1,所以坐标方程可以使用扩展欧几里得算法求出一组特殊解,然后将其扩展到全部解,形象化的:设通解为 x10,x20,y10,y20,则通解为:
⎩⎨⎧x1=x10+B⋅tx2=x20−A⋅ty1=y10+A⋅sy2=y20−B⋅st,s∈Z
有了这个,将其带入答案方程:
max(∣2Bt+α1∣,∣2As+β1∣)+max(∣−2At+α2∣,∣−2Bs+β2∣)
其中 α1=2x10+c1,β1=2y10+c1,α2=2x20+c2,β2=2y20+c2。
由于后面的负数下标不好看,考虑 n=−t,m=−s 给换掉:
max(∣2B(−n)+α1∣,∣2A(−m)+β1∣)=max(∣2Bn−α1∣,∣2Am−β1∣)max(∣−2A(−n)+α2∣,∣−2B(−m)+β2∣)=max(∣2An+α2∣,∣2Bm+β2∣)
好看多了,让我们替换常数:
e1e2e3e4=−α1=−(2x10+c1)=−β1=−(2y10+c1)=α2=2x20+c2=β2=2y20+c2
定义函数 f(n,m):
f(n,m)=max(∣2Bn+e1∣,∣2Am+e2∣)+max(∣2An+e3∣,∣2Bm+e4∣)
现在的问题转换为:给定四个常数 e,求 minf(n,m)。
由于我们需要整数最小值,考虑将 f 定义域扩展到实数,并定义:
f1(x,y)=max(∣2Bx+e1∣,∣2Ay+e2∣)f2(x,y)=max(∣2Ax+e3∣,∣2By+e4∣)
显然有 f(x,y)=f1(x,y)+f2(x,y),并且 f1,f2 都是凸函数(绝对值函数的最大值)。
此时有一个核心结论:
f(x,y) 有最小值的充要条件是 ∣2Bn+e1∣=∣2Am+e2∣ 且 ∣2An+e3∣=∣2Bm+e4∣。
具体证明官方使用了次梯度,这里我口胡一个简单一点的证明:
假如你站在二维平面坐标系上,每个点的高度就是 f(x,y),如果我们想找到最低点,那么它一定是一些棱交出来或一个平面,如果是平面的话最边上一定存在棱(保证 f 不是平面即可),所以说一定至少有一个是棱的最低端的最小值。
假设此时有一个最小值点满足 ∣2Bn+e1∣=∣2Am+e2∣ 且 ∣2An+e3∣=∣2Bm+e4∣,我们一定可以通过向四周移动这个点使其达到更小值(上下左右对应两个绝对值拆出的四条直线),所以假设不成立。
因此,我们只要找到 ∣2Bn+e1∣=∣2Am+e2∣ 且 ∣2An+e3∣=∣2Bm+e4∣ 就能得到最小值。