歐幾里得算法也叫輾轉相除法，用于求最大公約數，屬于小學奧數常見內容。
有個基本性質：gcd(a，b)=gcd(b，a%b)。
而擴展歐幾里德算法，則用來已知a，b，求解方程ax+by=gcd(a，b)的解。
根據數論中的相關定理，解是一定存在的。
所以，這道題只要用上擴展歐幾里德算法，就能很輕松找到一組x0、y0，使得等式成立。
接下來，江寒根據算法，只花了五分鐘，就編寫出了對應的代碼。
其中的遞歸函數exgcd（），就是擴展歐幾里德算法的一種實現。
用上了這種方法之后，編程難度大大降低，一共只用了10來行代碼，就完成了解答。
然后一調試……
江寒就無語地發現，求解出來的x0，居然有時候會出現負值。
這就不符合題意了。
那么……為什么會產生這種情況呢？
江寒想了想，拿過一張草稿紙，簡單地推理了一下。
在數學上，ax=1(modb)等價于ax%b=1，又等價于ax+by=1。
當用擴展歐幾里德算法，求出它的一組解x0和y0時，可得ax0+by0=1。
那么只要在方程左邊加上一個kab，再減去一個kab，合并同類項可得：
a(x0+kb)+b(y0-ka)=1。
x=x0+kb，y=y0-ka就是方程的通解，k可以為負數、0、或正數。
這里我們只關心x的取值，于是接下來，只要求出等于x0+kb的最小正整數，就可以了。
為什么給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分鐘，還剩下兩個多小時。
那么，接下來就一鼓作氣，搞定最后一題。