Posted on 2007-05-25 23:35
oyjpart 閱讀(2693)
評論(6) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
擴展歐幾里德的基本用法如下
方程 ax + by = C
要求x，y~~的解或者通解
若a,b,c存在大于1公約數 可以把這三個系數同時除掉公約數
此時如GCD(a, b)不整除C 則無解 因為兩邊同時除以GCD(a, b) 左邊是整數 右邊是小數 矛盾~
若整除 則除以GCD(a, b)得到新的 ax + by = k
若k 等于 1; 則用 extend_Eulid求解x，y
若k不等于1； 求解ax + by = 1 用extend-Eclude求出來之后乘以k即可
POJ上面的2個練習題：
PKU1061 青蛙的約會：擴展歐幾里德
跳蚤：最大公約數為1一定能導致同余1方程有解 再用m的因式分解判斷前面的數是否都含有這個因式