前排拜谢 gza 大蛇

· · 题解

听闻存在 2log 做法震撼人心，中间忘了，后面忘了

这篇题解大致是对 gza 题解的补充说明和优化。

先简单梳理一下 gza 题解，首先是在 stern-brocot tree 上二分，观察到二分的过程相当于不断的向左跳和向右跳，跳长链的过程可以用倍增优化，每次跳完之后再 check，check 的过程可以用数论分块和类欧。

问题 1：为什么 gza 的做法的复杂度是 2log 的

观察到可以将向左跳和向右跳合并在一次看，如果本来的分数是 \frac{b}{a},\frac{d}{c}，那么假设向左跳了 2^u+p 次，向右跳了 2^v+q 次，那么 a,c 中有一个至少增加了 2^{\max(u,v)} 倍，而询问次数最多不超过 4\max(u,v)，则总询问次数不超过 8\log n。

问题 2：为什么 gza 的代码跑得这么慢

第一点是因为他质数筛的部分写的是 1e7，但是其他的部分实现也不好，比如说在 stern-brocot tree 的长链上跳 n 次的部分就可以不使用矩阵而是简单的数学推导。

问题 3：这个做法还可以优化吗？

当然可以！

观察到在 stern-brocot tree 上二分的过程已经很难优化，考虑优化 check。

优化 check 也不难，将数论分块换成狄利克雷求和，平衡复杂度做到半只 log。

总复杂度 O(n^{\frac{2}{3}}+\sqrt n \log^{1.5} n)。

最优解榜二，无卡常到手！