@Test public void testReciprocalMod() { int[][] goodCases = { {1, 2, 1}, {1, 3, 1}, {2, 3, 2}, {1, 4, 1}, {3, 4, 3}, {1, 5, 1}, {2, 5, 3}, {3, 5, 2}, {4, 5, 4}, {2, 7, 4}, {3, 7, 5}, {4, 7, 2}, {5, 7, 3}, {6, 7, 6}, {18585, 26128, 5705}, {4352341, 7559949, 3054661}, {290514683, 936234758, 903930729}, {735803087, 1384775511, 1321131185}, {1, 2147483647, 1}, {2, 2147483647, 1073741824}, {188080773, 2147483647, 1201032874}, {527995520, 2147483647, 1215591224}, {1154582780, 2147483647, 193267031}, {1321286464, 2147483647, 95844396}, {2147483645, 2147483647, 1073741823}, {2147483646, 2147483647, 2147483646}, }; for (int[] cs : goodCases) assertEquals(cs[2], Library.reciprocalMod(cs[0], cs[1])); int[][] badCases = { {Integer.MIN_VALUE, Integer.MIN_VALUE}, {-1, -1}, {0, -1}, {-1, 0}, {0, 0}, {1, 1}, {3, 2}, {Integer.MAX_VALUE, 1}, {2, 4}, {2, 6}, {3, 6}, {44100, 48000}, {77, 2147483646}, {30783, 2147483646}, }; for (int[] cs : badCases) { try { Library.reciprocalMod(cs[0], cs[1]); Assert.fail(); } catch (IllegalArgumentException e) {} } }
public static int reciprocalMod(int x, int m) { if (!(0 <= x && x < m)) throw new IllegalArgumentException(); int y = x; x = m; int a = 0; int b = 1; while (y != 0) { int z = x % y; int c = a - x / y * b; x = y; y = z; a = b; b = c; } if (x == 1) return a >= 0 ? a : a + m; else throw new IllegalArgumentException("Reciprocal does not exist"); }
Library { public static int reciprocalMod(int x, int m) { if (!(0 <= x && x < m)) throw new IllegalArgumentException(); int y = x; x = m; int a = 0; int b = 1; while (y != 0) { int z = x % y; int c = a - x / y * b; x = y; y = z; a = b; b = c; } if (x == 1) return a >= 0 ? a : a + m; else throw new IllegalArgumentException("Reciprocal does not exist"); } }
Library { public static int reciprocalMod(int x, int m) { if (!(0 <= x && x < m)) throw new IllegalArgumentException(); int y = x; x = m; int a = 0; int b = 1; while (y != 0) { int z = x % y; int c = a - x / y * b; x = y; y = z; a = b; b = c; } if (x == 1) return a >= 0 ? a : a + m; else throw new IllegalArgumentException("Reciprocal does not exist"); }  }
Library { public static int reciprocalMod(int x, int m) { if (!(0 <= x && x < m)) throw new IllegalArgumentException(); int y = x; x = m; int a = 0; int b = 1; while (y != 0) { int z = x % y; int c = a - x / y * b; x = y; y = z; a = b; b = c; } if (x == 1) return a >= 0 ? a : a + m; else throw new IllegalArgumentException("Reciprocal does not exist"); }  static String reverse(String s); static boolean isPalindrome(String s); static boolean isPalindrome(int x); static int sqrt(int x); static long sqrt(long x); static BigInteger sqrt(BigInteger x); static boolean isSquare(int x); static int pow(int x, int y); static int powMod(int x, int y, int m); static int reciprocalMod(int x, int m); static BigInteger factorial(int n); static BigInteger binomial(int n, int k); static int gcd(int x, int y); static boolean isPrime(int x); static boolean[] listPrimality(int n); static int[] listPrimes(int n); static int[] listSmallestPrimeFactors(int n); static int totient(int n); static int[] listTotients(int n); static boolean nextPermutation(int[] arr); }
Library { public static int reciprocalMod(int x, int m) { if (!(0 <= x && x < m)) throw new IllegalArgumentException(); int y = x; x = m; int a = 0; int b = 1; while (y != 0) { int z = x % y; int c = a - x / y * b; x = y; y = z; a = b; b = c; } if (x == 1) return a >= 0 ? a : a + m; else throw new IllegalArgumentException("Reciprocal does not exist"); }  static String reverse(String s); static boolean isPalindrome(String s); static boolean isPalindrome(int x); static int sqrt(int x); static long sqrt(long x); static BigInteger sqrt(BigInteger x); static boolean isSquare(int x); static int pow(int x, int y); static int powMod(int x, int y, int m); static int reciprocalMod(int x, int m); static BigInteger factorial(int n); static BigInteger binomial(int n, int k); static int gcd(int x, int y); static boolean isPrime(int x); static boolean[] listPrimality(int n); static int[] listPrimes(int n); static int[] listSmallestPrimeFactors(int n); static int totient(int n); static int[] listTotients(int n); static boolean nextPermutation(int[] arr);  }