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