我需要計算一個看起來像: 的運算式，(A - B * C) / D它們的型別是：signed long long int A, B, C, D;每個數字都可以非常大（不會溢位它的型別）。雖然 B * C 可能導致溢位，但同時運算式(A - B * C) / D會適合。我怎樣才能正確計算它？
例如：在等式(Ax By = C)中，假設 A * x 溢位，但y = (C - A * x) / B可以放入。不需要使用 BigInteger 或 double 資料型別。
uj5u.com熱心網友回復：
我認為您可以更改操作的順序，使其看起來像： A/D - (B/D)*C 結果應該保持不變。
uj5u.com熱心網友回復：
您可以轉換等式以先進行除法，同時考慮余數：
假設 / 是整數除法，一切都是無限精度：
x == x / y * y x % y
(A - B * C) / D
((A/D * D (A%D)) - (B/D * D (B%D)) * (C/D * D (C%D))) / D
(A/D * D - B/D * D * C/D * D - (B/D * D * (C%D) (B%D) * C/D * D) (A%D) - (B%D) * (C%D)) / D
(A/D * D - B/D * D * C/D * D) / D - (B/D * D * (C%D) (B%D) * C/D * D) / D ((A%D) - (B%D) * (C%D)) / D
(A/D - B/D * C/D * D) - (B/D * (C%D) (B%D) * C/D) ((A%D) - (B%D) * (C%D)) / D
A/D - B/D * C - B/D * (C%D) - (B%D) * C/D) ((A%D) - (B%D) * (C%D)) / D
假設 D 不是太小也不是太大x / D并且x % D很小，我們可以這樣做：
using T = signed long long int;
T compute(T a, T b, T c, T d) {
T a1 = a / d, a2 = a % d;
T b1 = b / d, b2 = b % d;
T c1 = c / d, c2 = c % d;
T m1 = b1 * c, m2 = b1 * c2, m3 = b2 * c1, m4 = b2 * c2;
T s1 = a1 - m1 - m2 - m3, s2 = a2 - m4;
return s1 s2 / d;
}
關鍵部分是 m1 到 m4 的乘法。我相信，在結果應該合適的情況下溢位的數字 b 和 c 的范圍相當小。
uj5u.com熱心網友回復：
既然你提到gcd了讓我們試試這個作為替代答案：
using T = signed long long int;
T gcd(T a, T b);
T compute(T a, T b, T c, T d) {
// use gcd for (b * c) / d
T db = gcd(b, d);
T dc = gcd(c, d / db);
T dm = db * dc;
// use gcd on a for (a - b*c) / dm
T da = gcd(a, dm);
// split da for use on (b * c) / da
db = gcd(b, da);
dc = da / db;
T dr = d / da;
return ((a / da) - (b / db) * (c / dc)) / dr;
}
僅當 d 與 a、b 和 c 有足夠的共同因子時才有效。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/443098.html
上一篇：C 程式在數字太大時列印0