作者os653 (allstar)
看板C_and_CPP
標題[問題] 多元一次方程式求正整數解
時間Sun Apr 25 01:22:16 2010
遇到的問題： (題意請描述清楚)
多元一次方程式求正整數解，但只有兩條聯立方程式，求其正整數解
四元一次方程式的題目可能像這樣
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
→ netsphere:多元只有兩個方程式怎麼可能有確定解 04/25 01:26
推 loveme00835:應該是把符合條件的「都」找出來吧 04/25 01:29
推 Yshuan:這樣解出應該是個三次元的圖形吧... 04/25 01:34
→ os653:沒錯，是「都」要找出來，抱歉沒說清楚 04/25 01:45
推 walker2009:其中一變數移到右邊,所有可能值去左邊binary search?XD 04/25 01:54
→ walker2009:以上是類似某題ACM解法-.- 04/25 01:54
→ walker2009:當然右移的是domain最大的那個 04/25 01:55
推 hilorrk:很像我的作業...我的做法是做高斯消去後找leading one 04/25 08:19
→ hilorrk:哦 應該是做Gauss-Jordan消去..然後剩下右邊非零係數為其 04/25 08:20
→ hilorrk:解及free variable 04/25 08:21
推 costbook:好像是離散數學的題目？ 04/25 14:20