競賽程式答案常在定理與輸入條件的交界出錯。模除法需要可能不存在的逆元;叉積為零時須另檢查重疊。兩個題目共享一個好習慣:先把判斷化成精確不變量,再明確處理例外。
除法前先解同餘
定義 17.1.1
(線性同餘)
對整數 和正整數 , 表示某整數 滿足 。記 。
定理 17.1.2
(線性同餘的可解性)
設 為整數, 為正整數,。同餘式 有解,當且僅當 。此時它的解恰好構成模 的一個剩餘類,相當於模 的恰好 個不同剩餘類。
證明
(以最大公因數化簡)
若有解, 同時整除 和 ,所以 。反之,設 ,把 除以 :化簡後的同餘式 ,其係數與模數互質,所以 Bézout 恆等式給出 的模 逆元 ,以及解 。原同餘式的每個解經此除法都滿足化簡後的同餘式,而化簡後同餘式的每個解乘以 即滿足原同餘式。所以解恰好是模 的一個剩餘類,而這個類分成模 的 個剩餘類。
證明透視
為甚麼可以約去最大公因數,卻不能約去係數
證明除以的是 ,而不是 。除了之後,係數 與模數 互質,這正是 Bézout 恆等式產生逆元所需的條件。除法同時也把模數除以 :同餘式只能連同模數一起除以 。所以解集是模 的一個類,而不是模 的類,並且模 出現 個剩餘類。當 時,論證就是普通的逆元。必要性只用到 同時整除 和 ,完全不需要逆元。
這不等於在模 時隨意約去 。 的模 逆元存在當且僅當 。例如 2 沒有模 6 逆元:任何剩餘類乘 2 都得偶剩餘類。同餘式仍可能有解,例如 。Fermat 公式 要求 是質數且 ;模數為合數或 是 倍數時,該理由失效。
反例模式
約去公因數時模數也要改變
聲稱: 推出 。取 、。則 、,假設成立,但 不能被 整除。修正方法是把 連同模數一起約去:,即 ,而 確實成立。同理, 的解為 ,即模 的兩個剩餘類 與 ;驗算 。
常見錯誤
(對合數模數使用 Fermat 逆元公式)
取 、,公式 給出 ,但 。 模 的逆元是 ,因為 。指數 只在模數 為質數且 時才有根據。
例題:係數不可逆
例題 17.1.3
(係數不可逆的同餘式)
解 。 且 ,故有解。除以 2 得 。Euclid 給出 ,故 ,。因此 ;模 100 的兩個剩餘類為 和 。直接核對 、。若右邊是 31,最大公因數不整除它,便無解。
擴展 Euclid 不只求最大公因數,也構造係數。一般算法不斷把 換成 ,直至餘數為零;回代維持整數線性組合。正模數下應把負逆元正規化為所需的非負代表。程式語言的餘數慣例不同,不要假設 -7 % 50 必定是 43,須明確處理。
概念視角結構
解集是子群的一個陪集
在加法群 中,滿足 的剩餘類 構成子群 。由於 恰當 整除 時成立,故 ,階為 。若 是 的一個解,則全部解集是陪集 。例如 :,,解為 與 。映射 的像是 的倍數所成子群,所以 必須屬於其中。
定向使用正負號而非斜率
定義 17.1.4
(三點的定向)
對平面點定義
正值表示由有向 轉向 是左轉,負值是右轉,零表示共線;不用除以水平或垂直座標差。對兩條非退化閉線段 、,若 C、D 相對 AB 的定向值嚴格異號,且 A、B 相對 CD 的定向值也嚴格異號,便是內部真正相交。若某個定向值為零,須檢查該點是否在另一線段的座標包圍盒內。單靠共線不能判斷線段是否重疊。
例題:交叉與重疊
例題 17.1.5
(相交、重疊與分離的線段)
取 、、、。C、D 相對 AB 的定向值為 、;A、B 相對 CD 的為 、。兩對均嚴格異號,故線段真正相交。參數式 與 給出 ,唯一交點是 。
保留 A、B,但改用 、。四個定向值皆為零,因各點在 上; 區間 與 重疊於 ,所以閉線段共有從 到 的整段,而非僅一個點。若第二線段改為從 到 ,仍共線,但包圍盒不相交,故線段不相交。
兩端點相同的點線段應作點在線段上的測試,不能只依賴「真正交叉」論證。座標為整數時,要用足夠寬的整數類型計算兩個乘積及其差。即使單一乘積能放下,相減仍可能溢位;須由座標限制及表示方式推導界,不能用浮點斜率代替溢位證明。算術溢位後,原本正確的符號測試也不再正確。
常見錯誤
(零定向值不表示重疊)
叉積為零只說明三點共線。對 、、、,四個定向值都是零,但 與 不相交,因為它們的 區間 與 沒有公共部分。定向值為零之後,必須檢查包圍盒。
檢查整個化約
同餘證明有必要性及充分性;只報 而不構造縮減後的逆元,便缺了一半論證。線段測試也有兩層:嚴格異號處理真正交叉;出現零值時須檢查端點和重疊。先測普通實例,再刻意測共用端點、平行重疊和分離的共線線段。這些情況往往能暴露隨機外觀輸入未觸及的假設。
合併同餘時不要假設互質
熟悉的中國剩餘定理在模數 互質時,給出模 的一個剩餘類。若它們有公因數,須先檢查相容性。
定理 17.1.6
(兩個同餘式的相容性)
設 為正整數,。方程組 、 有解,當且僅當 。此時所有解恰好構成模 的一個剩餘類,不一定是模 。
證明
(必要性靠相減,充分性靠解同餘式)
若 ,則 可被 整除。反之,設 。同餘式 的右邊被 整除,由上面的可解性定理它有解 ;於是 同時滿足兩個同餘式。若 與 是兩個解, 同時被 與 整除,所以被 整除;而在解上加最小公倍數的倍數,兩個同餘式仍然成立。所以解構成模最小公倍數的一個類。
例題:相容與不相容的餘數
例題 17.1.7
(相容與不相容的餘數)
解 、。最大公因數是 2,整除差 ,故相容。寫 ,第二條變為 ,等價於 。由 ,得 ,故 ;19 的餘數確為 1 和 3。相反,、 無解,因差 1 不被 2 整除。把不相容同餘當作互質情況合併,可能得到看似合理但無法通過原式核對的整數。
實作須一致處理模數 1:它不對整數施加限制。擴展 Euclid 和 CRT 的中間乘積可能超過原輸入,即使最終剩餘值能放下亦然。安全類型取決於算法及輸入界;溢位後才取模不能撤銷溢位。Euclid 迭代次數對輸入位元長度是線性的,並不表示任意大整數的每次算術操作都有常數位元成本。
把幾何測試寫成完整程序
對非退化線段 ,定義 onSegment(A,B,P) 要求定向值為零,且 分別位於 A、B 對應座標的閉區間內。對一對線段,先測四個嚴格定向值是否構成真正交叉;若任何定向值為零,對相應端點執行 onSegment,便涵蓋共用端點及共線重疊。一條線段退化成點時,對另一線段執行點在線段上的測試;兩條均是點時比較兩點。這些慣例很重要:從閉線段改為開線段,端點接觸是否算相交便會改變。
定向值是有符號三角形面積的兩倍,其大小卻不是歐氏距離(Euclidean distance)。正負號只判定左、右或共線;計算距離需要不同的正規化。分類多邊形時,即使局部轉向一致,也需頂點次序及簡單多邊形等適當假設。自相交頂點序列的有符號面積需要不同解讀,不能默默當作一般簡單多邊形。應區分數學輸入契約與實作它的計算檢查。
二進位快速冪:保持乘積不變量
對非負整數指數 及整數模數 ,平方乘法把每個乘積模 化簡。初始 result=1 mod m、base=a mod m、e=E,其中 e 是尚未處理的指數。若 e 為奇數,先把 result 乘 base;無論奇偶,都把 base 平方並把 e 換為其整數一半。指數零返回模 的乘法單位元; 時其標準代表為 0。負指數需要逆元,不屬此簡單程序範圍。
定理 17.1.8
(平方乘法的不變量)
在每一輪開始時,result * base^e 模 同餘於 。特別地,當 e=0 時,result 的值就是 。
證明
(不變量在每一輪中保持成立)
初始時 result * base^e 等於 。設不變量在某一輪開始時成立,寫 ,。這一輪把新結果設為 result * base^r,新底數設為 base^2,新指數設為 ,一律模 。於是新結果乘以(新底數)的 次方,同餘於 result * base^r * base^(2q) result * base^e,而它同餘於 。當 時指數嚴格減小為 ,所以最終達到 ,此時不變量化為 result 。
例題 17.1.9
(計算 )
例如求 。初始結果 1、底數 3、指數 13;最低位為 1,結果變 3,平方得 9,指數減半為 6。指數 6 的最低位為 0,保留結果 3,9 平方模 17 得 13,指數減半為 3。最低位為 1,結果變 ,13 平方得 16,指數減半為 1。最後一位為 1,結果變 ,指數變 0,故答案是 12。實作可以省略最後一次沒有用到的平方,但仍須避免中間乘積溢位。
每輪把剩餘指數減半,故重複平方法需要對數數目的算術操作。這個計數不同於任意大整數乘法的位元複雜度,也不同於避免固定寬度溢位的模乘例程成本。若 、 有公因數,正整數冪的計算仍然有效;只有使用逆元的推理需要互質。區分算法不變量與用來縮減指數的定理,能避免在假設不成立時誤用 Fermat 定理。
幾何程式也須類似地檢查叉積符號的邊界。在寬類型中先做座標相減再相乘;若先溢位才轉型,已經太遲。在明確分析誤差容許度下,雙精度近似可能合理;但整數座標題使用足夠寬的精確表示,便可直接測試是否等於零。輸入界必須涵蓋相減、乘積及最後的差,而不只涵蓋每個座標。
模算例的最後核對應代回原系統,而不只代回縮減式。上述 19 除以 6 餘 1、除以 8 餘 3;加上最小公倍數 24 後兩個餘數仍保持。這既核對了所列代表,也解釋如何表示整個剩餘類。
相容條件變成兩個理想之和的陳述。
通往推廣的路徑
從整數到理想
相容條件變成兩個理想之和的陳述。
在 中, 生成理想 ,所以條件 即 。在任何交換環中,對理想 ,方程組 、 有解恰當 ,而解構成模 的一個剩餘類。在 中, 與 的交是 。
練習
快速檢查
(判斷 是否有解;若有,列出模 的所有解。)
先計算最大公因數。
解答 · 答案
這裏 而 ,所以有解。除以 得 。因為 , 的逆元為 ,所以 。模 的剩餘類為 ,恰好 個。驗算:、、。
快速檢查
(解 與 。)
檢查 是否整除 。
解答 · 答案
整除 ,所以方程組相容。寫 。第二個條件為 ,即 ,所以 。取 得 ;由於 ,解為 。驗算:,。
快速檢查
(從 到 的閉線段與從 到 的閉線段是否相交?)
四個點都在同一條直線上。
解答 · 答案
所有點都在 上,所以四個定向值都是零,嚴格正負號測試不適用。 的包圍區間 與 ( 同理)共有值 ,而點 在兩條閉線段上。所以它們恰好相交於一點,即共同端點 。
快速檢查
(追蹤平方乘法計算 。)
從 result 為 1、base 為 2、指數為 10 開始。
解答 · 答案
指數 10 為偶數:result 仍為 1,base 變為 ,指數 5。指數 5 為奇數:result 變為 ,base 變為 ,指數 2。指數 2 為偶數:base 變為 ,指數 1。指數 1 為奇數:result 變為 ,base 變為 ,指數 0。答案為 ,與 一致。