Anonymous user
Chinese remainder theorem: Difference between revisions
→{{header|Java}}: added Java
(→{{header|Java}}: added Java) |
|||
Line 562:
1000</lang>
'''Notes''': This is a brute force approach and does not meet the requirement for explicit notification of an an unsolvable set of equations (it just spins forever). A much more thorough and educational approach can be found on the [[j:Essays/Chinese%20Remainder%20Theorem|J wiki's Essay on the Chinese Remainder Thereom]].
=={{header|Java}}==
Translation of [[Chinese_remainder_theorem#Python|Python]] via [[Chinese_remainder_theorem#D|D]]
{{works with|Java|8}}
<lang java>import static java.util.Arrays.stream;
public class ChineseRemainderTheorem {
public static int chineseRemainder(int[] n, int[] a) {
int prod = stream(n).reduce(1, (i, j) -> i * j);
int p, sm = 0;
for (int i = 0; i < n.length; i++) {
p = prod / n[i];
sm += a[i] * mulInv(p, n[i]) * p;
}
return sm % prod;
}
private static int mulInv(int a, int b) {
int b0 = b;
int x0 = 0;
int x1 = 1;
if (b == 1)
return 1;
while (a > 1) {
int q = a / b;
int amb = a % b;
a = b;
b = amb;
int xqx = x1 - q * x0;
x1 = x0;
x0 = xqx;
}
if (x1 < 0)
x1 += b0;
return x1;
}
public static void main(String[] args) {
int[] n = {3, 5, 7};
int[] a = {2, 3, 2};
System.out.println(chineseRemainder(n, a));
}
}</lang>
<pre>23</pre>
=={{header|jq}}==
| |||