In competitive programming contests, many of the contestants use C++.
C++ STL(Standard Template Library) provides lots of of algorithms and containers.
But STL doesn't have the following very important features :
1.Library functions for Big numbers (Integers & real numbers)
2.Library functions for geometric shapes(lines,polygons,rectangles etc)
Contestants use prewritten templates to solve the problems related to big numbers and Geometry.
But, this can be time consuming and may cause typing errors requiring extra time for debugging.
This article is about JAVA library functions, built-in functions are not a must but can help quick coding and simplified debugging :
java.math.BigInteger :
Initialization (with constructors):
=====================
BigInteger bignum=new BigInteger("46767346456456464563464");
/* Initialize a big integer 'bignum' with 46767346456456464563464 */
BigInteger bignum=new BigInteger("1011100101",2);
/* Initialize a binary big integer 'bignum' with 1011100101 */
BigInteger bignum=new BigInteger("30456723456",8);
/* Initialize an octal big integer 'bignum' with 30456723456 */
BigInteger bignum=new BigInteger("16AFGH2",16);
/* Initialize an hexadecimal big integer 'bignum' with 16AFGH2 */
/*bases are from 2 to 36 A-Z is used for 10 to 36*/
byte[] bytes={1,0,1,1};
BigInteger bignum=new BigInteger(bytes);
/* Initialize a big integer 'bignum' with a byte array 'bytes' whereas
*/
Constants :
========
BigInteger.ONE //Represents 1 e.g. bignum = BigInteger.ONE;
BigInteger.ZERO //Represents 0 e.g. bignum = BigInteger.ZERO;
BigInteger.TEN //Represents 10 e.g. bignum = BigInteger.TEN;
Member Functions :
==============
BigInteger abs()
/* Returns a BigInteger whose value is the absolute value of this BigInteger.
e. g. bignum=bignum2.abs();
*/
BigInteger add(BigInteger val)
/* Returns a BigInteger whose value is (this + val).
e. g. bignum = bignum1.add(bignum2);
*/
BigInteger and(BigInteger val)
/* Returns a BigInteger whose value is (this & val).
e. g. bignum = bignum1.and(bignum2);
*/
BigInteger andNot(BigInteger val)
/* Returns a BigInteger whose value is (this & ~val).
e. g. bignum = bignum1.andNot(bignum2);
*/
int bitCount()
/* Returns the no. of bits in the 2's complement representation of this BigInteger that differ from its sign bit.
e. g. int a = bignum.bitCount(); */
int bitLength()
/* Returns the number of bits in the minimal two's-complement representation of this BigInteger, excluding a sign bit.
BigInteger b=new BigInteger("367544565567");
int a =b.bitLength();
*/
BigInteger clearBit(int n)
/* Returns a BigInteger whose value is equivalent to this BigInteger with the designated bit cleared.
Returns a big integer by clearing the nth bit counting from te right , starting from 0 e.g.
BigInteger b=new BigInteger("12");
System.out.println(b);
b=b.clearBit(3);
System.out.println(b);
*/
int compareTo(BigInteger val)
/* Compares this BigInteger with the specified BigInteger.
e. g. int a=bignum.compareTo(bignum2)
a= -1 if , bignum<bignum2
a= 0 if , bignum=bignum2
a= 1 if , bignum>bignum2 */
BigInteger divide(BigInteger val)
/* Returns a BigInteger whose value is (this / val).
BigInteger b1=new BigInteger("12");
BigInteger b2=new BigInteger("5");
BigInteger[] c=b1.divide(b2);
System.out.println("Result :" + c);
*/
BigInteger[] divideAndRemainder(BigInteger val)
/* Returns an array of two BigIntegers containing //(this / val) followed by (this % val). e. g.
BigInteger b1=new BigInteger("12");
BigInteger b2=new BigInteger("5");
BigInteger[] c=b1.divideAndRemainder(b2);
System.out.println("Result :" + c[0]);
System.out.println("Remainder :" + c[1]);
*/
double doubleValue()
/* Converts this BigInteger to a double.
e. g. double d = b.doubleValue();
*/
BigInteger flipBit(int n)
/* Returns a BigInteger whose value is equivalent to this BigInteger with the designated bit (the nth bit counting from te right , starting from 0 ) flipped.
BigInteger gcd(BigInteger val)
/* Returns a BigInteger whose value is the greatest common divisor of abs(this) and abs(val)
e. g. BigInteger r = bignum1.gcd(bignum2);
*/
int getLowestSetBit()
/* Returns the index of the rightmost (lowest-order) one bit in this BigInteger (the number of zero bits to the right of the rightmost one bit). e. g.
BigInteger b=new BigInteger("4500");
System.out.println("Decimal : "+b.toString(10));
System.out.println("Binary : "+b.toString(2));
System.out.println("Lowest Set Bit : "+b.getLowestSetBit());
O/P:
Decimal : 4500
Binary : 1000110010100
Lowest Set Bit : 2
*/
int intValue()
/* Converts this BigInteger to an int. e. g.
int a = bignum.intValue();
*/
boolean isProbablePrime(int certainty)
/* Returns true if this BigInteger is probably prime, false if it's definitely composite.
The certainty is a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that this
BigInteger is prime exceeds (1 - 1/(2^certainty)).
The execution time of this method is proportional to the value of this parameter. e. g.
BigInteger bignum = new BigInteger("1000000000000");
boolean res = bignum.isProbablePrime(7);
*/
long longValue()
/* Converts this BigInteger to a long. e. g.
long a = bignum.longValue();
*/
BigInteger max(BigInteger val)
/* Returns the maximum of this BigInteger and val.
e. g. BigInteger mx = bignum.max(bignum2);
*/
BigInteger min(BigInteger val)
/* Returns the minimum of this BigInteger and val.
e. g. BigInteger mn = bignum.min(bignum2);
*/
BigInteger mod(BigInteger m)
/* Returns a BigInteger whose value is (this mod m). */
BigInteger modInverse(BigInteger m)
/* Returns a BigInteger whose value is (this-1 mod m). */
BigInteger modPow(BigInteger exponent, BigInteger m)
/* Returns a BigInteger whose value is (this exponent mod m). */
BigInteger multiply(BigInteger val)
/* Returns a BigInteger whose value is (this * val). */
BigInteger negate()
/* Returns a BigInteger whose value is (-this). */
BigInteger nextProbablePrime()
/* Returns the first integer greater than this BigInteger that is probably prime. */
BigInteger not() // Returns a /*BigInteger whose value is (~this).*/
BigInteger or(BigInteger val)
/* Returns a BigInteger whose value is (this | val).
BigInteger pow(int exponent)
/* Returns a BigInteger whose value is (thisexponent).*/
# BigInteger probablePrime(int bitLength, Random rnd)
/* Returns a positive BigInteger that is probably prime, with the specified bitLength.*/
BigInteger remainder(BigInteger val)
/* Returns a BigInteger whose value is (this % val).*/
BigInteger setBit(int n)
/* Returns a BigInteger whose value is equivalent to this BigInteger with the designated bit set.*/
BigInteger shiftLeft(int n)
/* Returns a BigInteger whose value is (this << n).*/
BigInteger shiftRight(int n)
/* Returns a BigInteger whose value is (this >> n).*/
int signum()
/* Returns the signum function of this BigInteger.*/
BigInteger subtract(BigInteger val)
/* Returns a BigInteger whose value is (this - val).*/
boolean testBit(int n)
/* Returns true if and only if the designated bit is set.*/
byte[] toByteArray()
/* Returns a byte array containing the two's-complement representation of this BigInteger.*/
String toString()
/* Returns the decimal String representation of this BigInteger.*/
String toString(int radix)
/* Returns the String representation of this BigInteger in the given radix.*/
#BigInteger valueOf(long val)
/* Returns a BigInteger whose value is equal to that of the specified long.*/
BigInteger xor(BigInteger val)
/* Returns a BigInteger whose value is (this^val) */
---------------------------------------------------------------------------------------------------------------
# :-> static Members
UVa Problems , solved using these functions :-
495 Fibonacci Freeze
568 Just The Facts
623 500!
10220 I Love Big Numbers!
10334 Ray Through Glasses
11161 Help My Brother!
10023 Square Root
No comments:
Post a Comment