第256章 扩展欧几里得算法，以及增强线段树 (第2/2页)

，用于求最大公约数，属于小学奥数常见内容。

    有个基本性质：gcd=gcd。

    而扩展欧几里德算法，则用来已知a，b，求解方程的解。

    根据数论中的相关定理，解是一定存在的。

    所以，这道题只要用上扩展欧几里德算法，就能很轻松找到一组，使得等式成立。

    接下来，江寒根据算法，只花了五分钟，就编写出了对应的代码。

    其中的递归函数exgcd，就是扩展欧几里德算法的一种实现。

    用上了这种方法之后，编程难度大大降低，一共只用了10来行代码，就完成了解答。

    然后一调试……

    江寒就无语地发现，求解出来的x0，居然有时候会出现负值。

    这就不符合题意了。

    那么……为什么会产生这种情况呢？

    江寒想了想，拿过一张草稿纸，简单地推理了一下。

    在数学上，等价于ax%，又等价于ax 。

    当用扩展欧几里德算法，求出它的一组解时，可得ax0 。

    那么只要在方程左边加上一个kab，再减去一个kab，合并同类项可得：

    ) b=1。

    就是方程的通解，k可以为负数、0、或正数。

    这里我们只关心x的取值，于是接下来，只要求出等于的最小正整数，就可以了。

    为什么给x0加上一个kb，而不是某个比b小的数与k的乘积？

    很简单，如果那么做，就找不到能使等式成立的y了……

    因为x0有可能为负数，所以要分两种情况讨论。

    当x0大于0时，显而易见，x0%b也大于0，所以最小的正整数x就是x0%b本身。

    而当x0≤0时，x0%b也必然≤0，因为|x0%b|必定小于b，所以只需要在x0%b的结果上，再加上一个b，就可以得到最小的正整数解了。

    推演到这里，结论就很明确了。

    江寒马上将代码稍加修改，再次一调试，这次就顺利通过了。

    啧，出题的人挺阴险的嘛。

    如果生搬硬套扩展欧氏算法，没准一不小心就会掉进坑里去……

    虽然这么一个小坑，应该也困不住太多人就是了。

    第一题搞定之后，江寒就开始思考下一道题。

    第二题：借教室。

    ：……

    这道题和Day1的第三题差不多，都是那种表述啰嗦得要死，但只要看明白题意，就会觉得异常简单的题型。

    江寒直觉可以用线段树来弄。

    事实上，应该也是行得通的。

    但一般说来，线段树中的pushdown常数都特别巨大，很容易溢出。

    所以，如果没什么特别的优化手段，最多通过70%的数据校验点，也就差不多达到极限了。

    要想过掉100%的校验点，达到AllClear的境界，就必须使用二分答案法，再加上前缀和差分……

    正打算换个思路来破题，江寒忽然想起了什么，拿起草稿纸一阵推演。

    五分钟后，他长出了一口气，然后开始画流程、写伪代码。

    他没有改变算法，仍然使用了线段树，只不过在标准的算法中，稍微做了一点小改进。

    办法很简单，就是将线段树的标记固定化了，在区间完全重合的时候，只是打上修改标记，而不去pushdown标记。

    在查询的时候，顺便将每个位置标记上，要算的值都放在下一层递归里，这样就大大优化了线段树的pushdown常数。

    标记的删除非常方便，要把一个区间改回去，只需要把最外层的几个小区间标记置0就行。

    这么一改进，就能大大减少运算量，从而有很大的机会通过全部数据了。

    江寒写完增强线段树算法，又编写了一段测试代码，用各种极限值去测试。

    结果非常喜人，在100%的数据输入区间，都能轻松在1秒内得到答案。

    第二题就此搞定。

    时间到此才过去1个小时20分钟，还剩下两个多小时。

    那么，接下来就一鼓作气，搞定最后一题。