/** Shared code for solutions to Project Euler problems* By Nayuki Minase** http://nayuki.eigenstate.org/page/project-euler-solutions* https://github.com/nayuki/Project-Euler-solutions*/import java.math.BigInteger;final class Library {// Returns the reverse of the given string.public static String reverse(String s) {return new StringBuilder(s).reverse().toString();}// Tests whether the given string is a palindrome.public static boolean isPalindrome(String s) {return s.equals(reverse(s));}// Tests whether the given integer is a palindrome in decimal.public static boolean isPalindrome(int x) {return isPalindrome(Integer.toString(x));}// Returns floor(sqrt(x)).public static int sqrt(int x) {if (x < 0)throw new IllegalArgumentException("Square root of negative number");int y = 0;for (int i = 32768; i != 0; i >>>= 1) {y |= i;if (y > 46340 || y * y > x)y ^= i;}return y;}// Returns floor(sqrt(x)).public static long sqrt(long x) {if (x < 0)throw new IllegalArgumentException("Square root of negative number");long y = 0;for (long i = 1L << 31; i != 0; i >>>= 1) {y |= i;if (y > 3037000499L || y * y > x)y ^= i;}return y;}// Tests whether x is a perfect square.public static boolean isSquare(int x) {if (x < 0)return false;int sqrt = Library.sqrt(x);return sqrt * sqrt == x;}// Returns x to the power of y.public static int pow(int x, int y) {if (y < 0)throw new IllegalArgumentException("Negative exponent");int z = 1;for (int i = 0; i < y; i++) {if (Integer.MAX_VALUE / z < x)throw new ArithmeticException("Overflow");z *= x;}return z;}// Returns x^y mod m.public static int powMod(int x, int y, int m) {if (x < 0)throw new IllegalArgumentException("Negative base not handled");if (y < 0)throw new IllegalArgumentException("Reciprocal not handled");if (m <= 0)throw new IllegalArgumentException("Invalid modulus");// Exponentiation by squaringint z = 1;while (y != 0) {if ((y & 1) != 0)z = (int)((long)z * x % m);x = (int)((long)x * x % m);y >>>= 1;}return z;}// Returns x^-1 mod m. Note that x * x^-1 mod m = x^-1 * x mod m = 1.public static int reciprocalMod(int x, int m) {if (m < 0 || x < 0 || x >= m)throw new IllegalArgumentException();// Based on a simplification of the extended Euclidean algorithmint 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 + m) % m;elsethrow new IllegalArgumentException("Reciprocal does not exist");}// Returns n!.public static BigInteger factorial(int n) {if (n < 0)throw new IllegalArgumentException("Factorial of negative number");BigInteger prod = BigInteger.ONE;for (int i = 2; i <= n; i++)prod = prod.multiply(BigInteger.valueOf(i));return prod;}// Returns n choose k.public static BigInteger binomial(int n, int k) {return factorial(n).divide(factorial(n - k).multiply(factorial(k)));}// Returns the largest non-negative integer that divides both x and y.public static int gcd(int x, int y) {while (y != 0) {int z = x % y;x = y;y = z;}return x;}// Tests whether the given integer is prime.public static boolean isPrime(int x) {if (x < 0)throw new IllegalArgumentException("Negative number");if (x == 0 || x == 1)return false;else if (x == 2)return true;else {if (x % 2 == 0)return false;for (int i = 3, end = sqrt(x); i <= end; i += 2) {if (x % i == 0)return false;}return true;}}// Returns a Boolean array 'isPrime' where isPrime[i] indicates whether i is prime, for 0 <= i <= n.// For a large batch of queries, this is faster than calling isPrime() for each integer.// For example: listPrimality(100) = {false, false, true, true, false, true, false, true, false, false, ...}.public static boolean[] listPrimality(int n) {if (n < 0)throw new IllegalArgumentException("Negative size");boolean[] prime = new boolean[n + 1];if (n >= 2)prime[2] = true;for (int i = 3; i <= n; i += 2)prime[i] = true;// Sieve of Eratosthenesfor (int i = 3, end = sqrt(n); i <= end; i += 2) {if (prime[i]) {for (int j = i * i; j <= n; j += i << 1)prime[j] = false;}}return prime;}// Returns all the prime numbers less than or equal to n, in ascending order.// For example: listPrimes(100) = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., 83, 89, 97}.public static int[] listPrimes(int n) {if (n < 0)throw new IllegalArgumentException("Negative size");boolean[] isPrime = listPrimality(n);int count = 0;for (boolean b : isPrime) {if (b)count++;}int[] primes = new int[count];for (int i = 0, j = 0; i < isPrime.length; i++) {if (isPrime[i]) {primes[j] = i;j++;}}return primes;}// Returns the number of integers in the range [1, n] that are coprime with n.// For example, totient(12) = 4 because these integers are coprime with 12: 1, 5, 7, 11.public static int totient(int n) {if (n <= 0)throw new IllegalArgumentException("Totient of non-positive integer");int p = 1;for (int i = 2, end = Library.sqrt(n); i <= end; i++) { // Trial divisionif (n % i == 0) { // Found a factorp *= i - 1;n /= i;while (n % i == 0) {p *= i;n /= i;}end = Library.sqrt(n);}}if (n != 1)p *= n - 1;return p;}// Returns an array 'totients' where totients[i] == totient(i), for 0 <= i <= n.// For a large batch of queries, this is faster than calling totient() for each integer.public static int[] listTotients(int n) {if (n < 0)throw new IllegalArgumentException("Negative size");int[] totients = new int[n + 1];for (int i = 0; i <= n; i++)totients[i] = i;for (int i = 2; i <= n; i++) {if (totients[i] == i) { // i is primefor (int j = i; j <= n; j += i)totients[j] = totients[j] / i * (i - 1);}}return totients;}// Returns the same result as x.multiply(y), but is faster for large integers.public static BigInteger multiply(BigInteger x, BigInteger y) {final int CUTOFF = 1536;if (x.bitLength() <= CUTOFF || y.bitLength() <= CUTOFF) { // Base casereturn x.multiply(y);} else { // Karatsuba fast multiplicationint n = Math.max(x.bitLength(), y.bitLength());int half = (n + 32) / 64 * 32;BigInteger mask = BigInteger.ONE.shiftLeft(half).subtract(BigInteger.ONE);BigInteger xlow = x.and(mask);BigInteger ylow = y.and(mask);BigInteger xhigh = x.shiftRight(half);BigInteger yhigh = y.shiftRight(half);BigInteger a = multiply(xhigh, yhigh);BigInteger b = multiply(xlow.add(xhigh), ylow.add(yhigh));BigInteger c = multiply(xlow, ylow);BigInteger d = b.subtract(a).subtract(c);return a.shiftLeft(half).add(d).shiftLeft(half).add(c);}}// Advances the given sequence to the next permutation and returns whether a permutation was performed.// If no permutation was performed, then the input state was already the last possible permutation (a non-ascending sequence).// For example:// - nextPermutation({0,0,1}) changes the argument array to {0,1,0} and returns true.// - nextPermutation({1,0,0}) leaves the argument array unchanged and returns false.public static boolean nextPermutation(int[] a) {int i, n = a.length;for (i = n - 2; ; i--) {if (i < 0)return false;if (a[i] < a[i + 1])break;}for (int j = 1; i + j < n - j; j++) {int tp = a[i + j];a[i + j] = a[n - j];a[n - j] = tp;}int j;for (j = i + 1; a[j] <= a[i]; j++);int tp = a[i];a[i] = a[j];a[j] = tp;return true;}}// Immutable unlimited precision fractionfinal class Fraction {public final BigInteger numerator; // Always coprime with denominatorpublic final BigInteger denominator; // Always positivepublic Fraction(BigInteger numer, BigInteger denom) {if (denom.signum() == 0)throw new ArithmeticException("Division by zero");// Reduce to canonical formif (denom.signum() == -1) {numer = numer.negate();denom = denom.negate();}BigInteger gcd = numer.gcd(denom);if (!gcd.equals(BigInteger.ONE)) {numer = numer.divide(gcd);denom = denom.divide(gcd);}numerator = numer;denominator = denom;}public Fraction add(Fraction other) {return new Fraction(numerator.multiply(other.denominator).add(other.numerator.multiply(denominator)), denominator.multiply(other.denominator));}public Fraction subtract(Fraction other) {return new Fraction(numerator.multiply(other.denominator).subtract(other.numerator.multiply(denominator)), denominator.multiply(other.denominator));}public Fraction multiply(Fraction other) {return new Fraction(numerator.multiply(other.numerator), denominator.multiply(other.denominator));}public Fraction divide(Fraction other) {return new Fraction(numerator.multiply(other.denominator), denominator.multiply(other.numerator));}public boolean equals(Object obj) {if (obj instanceof Fraction) {Fraction other = (Fraction)obj;return numerator.equals(other.numerator) && denominator.equals(other.denominator);} elsereturn false;}public int hashCode() {return numerator.hashCode() + denominator.hashCode();}public String toString() {return numerator + "/" + denominator;}}
No comments:
Post a Comment