[線代] 測試一個多元一次多項式是否有給定解

[snobbery (egoist)]

我遇到的問題如下:

給定 p1x1 + p2x2 + ... pnxn = y, 其中 p1, p2, ... pn, y 都已知,
想知道是否有 x1, x2, ... xn 來讓 p1x1 + p2x2 + ... pnxn = y 成立.

給個實際例子如下:

給定 3x1 + 5x2 + 17x3 = 61, 其中 p1 = 3, p2 = 5, p3 = 17, y = 61,
想知道是否有 x1, x2, ... xn 來讓 3x1 + 5x2 + 17x3 = 61 成立.

如果沒有這種 x1, x2, ... xn 的話, 當然輸出就是 reject 就好,
如果有這種 x1, x2, ... xn 的話, 可以不用"找到"那組 x1, x2, ... xn,
只要知道有這組 x1, x2, ... xn 即可.

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.138.34.36
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1436522962.A.508.html
推 LPH66       : 你需要整數解嗎? 沒要整數解的話隨便都有
→ LPH66       : 要整數解的話則是有某個 GCD(pi,pj)|y <=> 有整數解
→ LPH66       : 要正整數解的話就要討論一下了
推 LPH66       : 回你的水球, 就只是簡單的 extended Euclid algo.
→ LPH66       : 對那一組 pi pj 求 xi xj 其他都設 0 就是了