题目

描述

题目大意

给你平面直角坐标系上的$n$n个起点和$n$n个终点，$(x,y)$(x,y)每次只能走到$(x,y+x)(x+y,y)(x,y-x)(x-y,y)$(x,y+x)(x+y,y)(x,y−x)(x−y,y)这些点，每次花费的时间为$1$1。
在走的过程中必须一直在第一象限。
起点和终点没有对应，即可以从某个起点到达任意终点。
问花费的最小的时间和。
题目保证所有的起点都可以到达所有的终点。

---

思考历程

看到题目的时候很绝望啊……
数据范围这么大，你究竟想干嘛……
这些点走的方式很奇怪，于是我试着往那个方向思考一下，然后没有什么卵用……
于是我把希望寄托在部分分上，最多的步数是$500$500。
我突然发现，就算是求出了两点之间的距离，我还是不能快速地匹配，只会暴力全排列……
然后得分的范围继续缩小，我去考虑$n=1$n=1的情况。
然而我发现，如果暴力宽搜，$m=500$m=500的情况还是过不去。
似乎可以双向宽搜，但是实现复杂并且没有什么卵用（要打哈希表或者map）。
所以我只会$10$10分。
感觉分值太小，都不想打了，于是放弃。

---

正解

这题的正解真的很巧妙。
我们从它们走路的方式入手：看看$(x,y-x)(x-y,y)$(x,y−x)(x−y,y)，有没有想到$gcd$gcd相关的东西？
我比赛时想到了，但根本不知道有什么卵用。
再换一种方式思考一下。其实，假设终点会动，那么起点走到$(x,y+x)(x+y,y)$(x,y+x)(x+y,y)是不是相当于终点走到$(x,y-x)(x-y,y)$(x,y−x)(x−y,y)？
对于每个点$(x,y)$(x,y)，我们发现只能去到$(x,y-x)$(x,y−x)和$(x-y,y)$(x−y,y)其中的一个点，因为另一个点不在第一象限。
发现这个东西像是一棵二叉树，它到父亲走的是$(x,y-x)$(x,y−x)或$(x-y,y)$(x−y,y)，到儿子走的是$(x,y+x)$(x,y+x)或$(x+y,y)$(x+y,y)。
可以画张图理解一下，这里就不画了……
数据保证所有的起点都可以到达所有的终点，所以所有的点$(x,y)$(x,y)的$gcd(x,y)$gcd(x,y)都是一样的。
想一想如果不一样，那还有到达的可能吗？显然没有。

现在所有的起点和终点都在二叉树上面，想让时间和最小，那么在匹配起点和终点的时候，如果在同一棵子树中就尽量匹配，然后没有匹配完的就伸出去，这样显然最优。
数据范围比较小的时候，暴力将这棵二叉树建出来，在起点上打$1$1的标记，在终点上打$-1$−1的标记，对于每一条边，经过它的点数就是它下面的点中标记的和的绝对值。
这样子就可以过$70$70分了。可是数据并不友好，如果暴力建树，那么将会特别大。

我们发现这棵树上面有很多点是没有什么卵用的，不妨将它们缩在一起。
看看$(x,y)$(x,y)到$(x,y-x)$(x,y−x)或$(x-y,y)$(x−y,y)，其实很容易联想到$gcd$gcd。
求$gcd$gcd的过程就是$(x,y)$(x,y)变成$(x,y \mod x)$(x,ymodx)或$(x \mod y,y)$(xmody,y)。
其实$gcd$gcd就是缩减版的这样的操作。
$gcd$gcd的时间复杂度是$\lg$lg级别的，考虑用$gcd$gcd过程中的点建成一棵缩减版的二叉树。
对于一个点，求一遍$gcd$gcd，就可以形成一条链。很容易发现这条链上的每一个点都是转折点，如果一个点是父亲的右儿子，那么它的儿子就是左儿子，反之同理。
为什么？因为在求$gcd$gcd的过程中，它们的大小关系一定变化的。上一次$x&gt;y$x>y，下一次$x&lt;y$x<y。
对于每个点，我们都搞出了这样的一条链，然后我们将这些链合并起来，这棵二叉树就建好了，点数最多为$n \lg n$nlgn。

但是，有的时候两条链相交的最低点（也就是两点的$LCA$LCA）不在建出来的这棵缩减版的二叉树上，也就如同下图：

黑色的边表示实际二叉树上面的链，红色的边表示利用$gcd$gcd求出的链上的边。
在用$gcd$gcd求链之后，因为链上的父亲可能是儿子的好多代祖先，所以在不同的链合并之后，就可能出现一个父亲有很多个儿子的情况，但实际上，这些儿子都是在二叉树中的同一条链上的。
如果它们不在同一条链上，那就是这样：

然而在前面的时候我们已经说过了，在转角的地方应该出现一个点，使得这个点在求$gcd$gcd的链上。所以说，这样的情况是不存在的。
当我们见到那样的情况的时候该怎么做？
可以将每个点挂在它链上的父亲处，然后建树的时候在父亲那里对于这些点排序，然后依次相连。

建完缩减版二叉树之后就类似之前的做法来做就好了。
时间复杂度$O(n \lg n*60)$O(nlgn∗60)，可以过。

---

具体实现

这题的正解理解起来其实还是比较容易的，重点是实现复杂。
YMQ大佬打了6k的代码……
这题的细节特别多。

首先，先把所有$gcd$gcd路径上的点存起来，并且给予它们一个编号，丢在一个数组里面。
边做$gcd$gcd边建树会很复杂，所以我们先不要考虑。
其次对它们排个序，然后去重。去重的时候用指针来指向第一个和它一样的点，再将它删去（因为在后面要给它们打标记，所以不能仅仅将其删去）。

接着就是建树：
上面说将点挂在父亲那里，然后排序，依次相连。这样的方法比较复杂，并且要用动态数组或者是链表，感觉上实现很不方便。
我们左右儿子分别处理，由这棵二叉树的性质可得左儿子的$x$x坐标和自己相等，右儿子的$y$y坐标和自己相等。
现在我们只考虑处理左儿子（右儿子同理）：
首先我们按照$x$x坐标为第一关键字排序，按照$y$y坐标为第二关键字排序。
我们发现$x$x相同的所有点是连在一起的，前面的$x&gt;y$x>y，后面的$x \leq y$x≤y。
思考一下这个二叉树的性质：
如果当前的这个点作为左儿子，那么$x\leq y$x≤y。
如果当前的这个点作为右儿子，那么$x&gt;y$x>y。
我们只考虑左儿子，所以只有$x \leq y$x≤y的时候才有必要将其挂在链上父亲上，然后排序，连边。
但是，$x$x相等的连在一起，并且$y$y是递增的，不妨考虑另一种想法：
实际上，$y$y已经被排序好了，现在就是要接在父亲那里。
显然这个点的$y\mod x$ymodx是父亲的$y$y。
链上父亲的编号怎么找？哈希？不（我对哈希总是抱有一种排斥的心理，因为我总觉得它会挂。）。
在$x$x相等的这一段中，前面的那一段$x&gt;y$x>y，链上父亲必定在前面那一段之内。
所以二分就可以了！
对于每个链上父亲，也就是$x&gt;y$x>y的点，可以记录一个接口，表示如果有左儿子挂在他上面，就应当从接口向这个儿子连一条边。这个接口的初值就是自己。
所以找到父亲之后连到接口上，并且将接口更新为自己。

做完这些操作之后树就建好了。
剩下的直接暴力递归去搞……

有一个特别重要的细节：求完$gcd$gcd之后，最后一个点是在坐标轴上的。
但是按照二叉树本来的样子，根节点就应该是$(gcd,gcd)$(gcd,gcd)。
我在打程序的时候一直在思考着这个东西该怎么处理，需要特殊处理吗？
后来我决定将这个在坐标轴上的点保留下来，并且在点的数组当中加入$(gcd,gcd)$(gcd,gcd)。
在建树的时候，由于$(gcd,gcd)$(gcd,gcd)一定是最小的，其它不相同的点本来认$(gcd,0)$(gcd,0)或$(0,gcd)$(0,gcd)为父亲，但由于$(gcd,gcd)$(gcd,gcd)的存在，它们都会认$(gcd,gcd)$(gcd,gcd)为父亲。
于是递归的时候就可以愉快地从$(gcd,gcd)$(gcd,gcd)开始了！