“七八點鐘？沒問題，我們都不見得能玩到那麼晚呢。”熊磊率先表示贊同。

朱達昌也點了點頭：“玩得太晚了，兩位老師也會不放心。”

江寒笑問：“看你們下午都這麼有時間，意思是今天不往回走了唄？”

朱達昌回答：“高老師預定了火車臥鋪，夜裏10點的始發車。”

李山河也說：“要等8、9個小時的車，這麼長時間，不玩點什麼也太無聊了。”

熊磊的情況有所不同，他解釋說：“我爸爸的車實在不能湊合了，準備買臺全新的高爾夫6，明天就去4s店提車，所以只能晚一天回去。”

江寒瞭然一笑，熊爸爸那輛二手車，動不動就趴窩，的確早該換換了。

想了想，對李山河、朱達昌說：“我不一定能送你們上車，今晚我可能就得往回走了。”

“這麼急嗎？好不容易來一趟松江，不好好玩一玩？”李山河問。

江寒坦然點頭，說：“我是坐方便車來的，別人什麼時候往回走，我就什麼時候跟回去，總不能讓別人將就我吧？”

其實要什麼時候回去，還不是他一句話的事情？

但夏雨菲明天有課……

“誒？如果唱k的話，能不能讓夏雨菲同學也來呀？”朱達昌突發奇想。

“就是的，江寒，你和夏雨菲好像挺熟悉的，幫忙邀請一下唄。”李山河也力促。

江寒一陣無語。

別說，還真可以考慮一下。

小媳婦這次出來，光跟着自己跑前跑後了，也沒玩好……

也不知道她有沒有意願出來散散心？

江寒想了想，沒把話說死：“好吧，比完賽我打電話問一聲，能不能約出來，我可不敢保證哦。”

聽了江寒的話，其他人都十分期待，畢竟夏雨菲不光長得好看，在學校裏也是有名的唱歌好聽。

但其實，江寒已經決定，順便也叫苗清瀾和關浩一聲，願意來的話，就一起熱鬧熱鬧。

而且，出門在外的，指導教師們也不可能徹底放手，肯定都會跟着。

這樣的話，就不太好去一些環境太複雜的場所了……

時間將到8點，賽場封鎖就被解除，選手們再次魚貫入場。

其他流程和昨天大同小異。

8點30分，Day2比賽正式開始。

江寒拿到題之後，習慣性地全部瀏覽了一遍，然後從頭開始做。

今天的三道題，難度比Day1高多了。

但說實話，並沒有超過他的預計，都屬於那種稍微花點心思就能解決的類型。

第一題是同餘方程。

【問題描述】：求關於x的同餘方程ax≡1（mod b）的最小正整數解。

輸入數據是兩個正整數a和b，要求輸出方程的最小正整數解x0。

比如：輸入3和10，輸出就是7。

數據範圍：

對於40%的數據，2≤b≤1000；

對於60%的數據，2≤b≤50000000；

對於100%的數據，2≤a≤2000000000，2≤b≤2000000000；

輸入的數據保證一定有解。

江寒一打眼就看出來了，這是一道數論題。

只要明白同餘方程是怎麼回事，就很容易理清思路。

原式可理解爲ax mod b = 1，即ax的乘積除以b，餘數爲1。

所以，對於任意給定的a、b，可以用窮舉法暴力搜索，從x0=1開始，每次遞增1，很容易就能找出一個最小的x，使得方程成立。

但因爲a、b的取值範圍特別巨大，這樣做，會導致至少4個點TLE（Time Limit Exceeded，即時間超限）。

要想得到全部分數，必須想辦法縮減運算時間。

如果能找到這個算式中隱藏的規律，問題自然迎刃而解。

當然，這需要擁有一點數論功底，才能辦得到。

江寒先觀察了一下方程。

原式等價於 ax-kb=1，因爲k值可以爲負數，所以又可以看做ax+by=1。

顯而易見，a與b一定互質，所以原式可轉化爲 ax+by=gcd（a，b），這裏gcd表示兩個整數的最大公約數……

咦？

這不就是擴展歐幾里得的標準形式嗎？

這樣就簡單了啊！

歐幾里得算法也叫輾轉相除法，用於求最大公約數，屬於小學奧數常見內容。

有個基本性質：gcd（a，b）=gcd（b，a%b）。

而擴展歐幾里德算法，則用來已知a， b，求解方程ax+by = gcd（a， b）的解。

根據數論中的相關定理，解是一定存在的。

所以，這道題只要用上擴展歐幾里德算法，就能很輕鬆找到一組x0、y0，使得等式成立。

接下來，江寒根據算法，只花了五分鐘，就編寫出了對應的代碼。

其中的遞歸函數exgcd（），就是擴展歐幾里德算法的一種實現。

用上了這種方法之後，編程難度大大降低，一共只用了10來行代碼，就完成了解答。

然後一調試……

江寒就無語地發現，求解出來的x0，居然有時候會出現負值。

這就不符合題意了。

那麼……爲什麼會產生這種情況呢？

江寒想了想，拿過一張草稿紙，簡單地推理了一下。

在數學上，ax = 1 （mod b）等價於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%的校驗點，達到All Clear的境界，就必須使用二分答案法，再加上前綴和差分……

正打算換個思路來破題，江寒忽然想起了什麼，拿起草稿紙一陣推演。

五分鐘後，他長出了一口氣，然後開始畫流程、寫僞代碼。

他沒有改變算法，仍然使用了線段樹，只不過在標準的算法中，稍微做了一點小改進。

辦法很簡單，就是將線段樹的標記固定化了，在區間完全重合的時候，只是打上修改標記，而不去pushdown標記。

在查詢的時候，順便將每個位置標記上，要算的值都放在下一層遞歸裏，這樣就大大優化了線段樹的pushdown常數。

標記的刪除非常方便，要把一個區間改回去，只需要把最外層的幾個小區間標記置0就行。

這麼一改進，就能大大減少運算量，從而有很大的機會通過全部數據了。

江寒寫完增強線段樹算法，又編寫了一段測試代碼，用各種極限值去測試。

結果非常喜人，在100%的數據輸入區間，都能輕鬆在1秒內得到答案。

第二題就此搞定。

時間到此纔過去1個小時20分鐘，還剩下兩個多小時。

那麼，接下來就一鼓作氣，搞定最後一題。