[問題] 多元一次方程式求正整數解

看板C_and_CPP作者 (allstar)時間15年前 (2010/04/25 01:22), 編輯推噓5(5推 0噓 6→)
留言11則, 7人參與, 最新討論串1/1
遇到的問題： (題意請描述清楚) 多元一次方程式求正整數解，但只有兩條聯立方程式，求其正整數解 　　四元一次方程式的題目可能像這樣 1234A + 2345B + 3457C + 4568D = 5678901 A + B + C + D = 1234 則 A, B, C, D 皆為正整數之解為？ 五元一次方程式的題目可能像這樣 1234A + 2345B + 3456C + 4567D + 5678E = 6789012 A + B + C + D + E = 1234 則 A, B, C, D, E 皆為正整數之解為？ 　　上面兩個數值都是隨便掰的，搞不好沒有正整數解也說不一定 補充說明： 　　一開始直覺就是暴力解，三元一次方程式沒問題 　　但到五元一次方程式，只要數值大一點，算幾天都算不完 　　目前只想到最基本的方法，就是把兩條式子相消，可以少一元 　　像上面四元一次方程式的題目，可以化簡為 1234A + 2345B + 3457C + 4568D = 5678901 - 1234A + 1234B + 1234C + 1234D = 1522756 ------------------------------------------- 　 1111B + 2223C + 3334D = 4156145 暴力解快 1234 倍，不過還是算不完 ... 　　請問有沒有更快速的解法？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.46.115.196
→
04/25 01:26, , 1F
多元只有兩個方程式怎麼可能有確定解
04/25 01:26, 1F
推
04/25 01:29, , 2F
應該是把符合條件的「都」找出來吧
04/25 01:29, 2F
推
04/25 01:34, , 3F
這樣解出應該是個三次元的圖形吧...
04/25 01:34, 3F
→
04/25 01:45, , 4F
沒錯，是「都」要找出來，抱歉沒說清楚
04/25 01:45, 4F
推
04/25 01:54, , 5F
其中一變數移到右邊,所有可能值去左邊binary search?XD
04/25 01:54, 5F
→
04/25 01:54, , 6F
以上是類似某題ACM解法-.-
04/25 01:54, 6F
→
04/25 01:55, , 7F
當然右移的是domain最大的那個
04/25 01:55, 7F
推
04/25 08:19, , 8F
很像我的作業...我的做法是做高斯消去後找leading one
04/25 08:19, 8F
→
04/25 08:20, , 9F
哦 應該是做Gauss-Jordan消去..然後剩下右邊非零係數為其
04/25 08:20, 9F
→
04/25 08:21, , 10F
解及free variable
04/25 08:21, 10F
推
04/25 14:20, , 11F
好像是離散數學的題目？
04/25 14:20, 11F
‣ 更多 os653 的文章
文章代碼(AID): #1BqoZA-t (C_and_CPP)