“七八點鐘？沒問題，我們都不見得能玩到那麼晚呢。”熊磊率先表示贊同。
朱達昌也點了點頭：“玩得太晚了，兩位老師也會不放心。”
江寒笑問：“看你們下午都這麼有時間，意思是今天不往回走了唄？”
朱達昌回答：“高老師預定了火車臥鋪，夜裡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分鐘，還剩下兩個多小時。
那麼，接下來就一鼓作氣，搞定最後一題。