Brian Warehouse

Some birds aren`t meant to be caged, their feathers are just too bright... ...
posts - 40, comments - 16, trackbacks - 0, articles - 1

SGU 112 a^b-b^a (Java Edition)

Posted on 2010-08-17 13:21 Brian 阅读(552) 评论(0)  编辑 收藏 引用 所属分类: SGU

You are given natural numbers a and b. Find ab-ba.

Input

Input contains numbers a and b (1≤a,b≤100).

Output

Write answer to output.

Sample Input

2 3

Sample Output

-1

一看到这种题目,就想到高精度算法,Java的大数。
此举确实流氓了一点,不过确实过了,鄙人的第一题SGU啊,不许打击。
过段时间看看能不能写出 (C++ Edition) ,啥也别说了,上代码。

SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouseimport java.math.*;
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse
import java.util.*;
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse
public class Solution
SGU 112 a^b-b^a (Java Edition) - Icho - Brian WarehouseSGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse{
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse   
public static void main(String[] args)
SGU 112 a^b-b^a (Java Edition) - Icho - Brian WarehouseSGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse   
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse{
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse      Scanner in 
= new Scanner(System.in);
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse      
int a = in.nextInt();
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse      
int b = in.nextInt();
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse      
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse      BigInteger A
=BigInteger.valueOf(a);
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse      BigInteger B
=BigInteger.valueOf(b); // A^B
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse
      BigInteger rA=BigInteger.valueOf(a);
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse      BigInteger rB
=BigInteger.valueOf(b); // store the result after computing
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse
      
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse      
for(int i=1; i<b; i++// just b-1 times
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse
          rA=rA.multiply(A);
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse      
for(int i=1; i<a; i++)    
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse          rB
=rB.multiply(B);
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse      System.out.println(rA.subtract(rB)); 
// sub
SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse
   }

SGU 112 a^b-b^a (Java Edition) - Icho - Brian Warehouse}

附《Core Java I》里关于 大数的简单介绍,讲的算比较清晰的了:
Big Numbers
If the precision of the basic integer and floating-point types is not sufficient, you can
turn to a couple of handy classes in the java.math package: BigInteger and BigDecimal. These
are classes for manipulating numbers with an arbitrarily long sequence of digits. The
BigInteger class implements arbitrary precision integer arithmetic, and BigDecimal does the
same for floating-point numbers.
Use the static valueOf method to turn an ordinary number into a big number:
BigInteger a = BigInteger.valueOf(100);
Unfortunately, you cannot use the familiar mathematical operators such as + and * to
combine big numbers. Instead, you must use methods such as add and multiply in the big
number classes.
BigInteger c = a.add(b); // c = a + b
BigInteger d = c.multiply(b.add(BigInteger.valueOf(2))); // d = c * (b + 2)
C++ NOTE: Unlike C++, Java has no programmable operator overloading. There was no way
for the programmer of the BigInteger class to redefine the + and * operators to give the add and
multiply operations of the BigInteger classes. The language designers did overload the + operator
to denote concatenation of strings. They chose not to overload other operators, and they
did not give Java programmers the opportunity to overload operators in their own classes.
Listing 3–6 shows a modification of the lottery odds program of Listing 3–5, updated to
work with big numbers. For example, if you are invited to participate in a lottery in
which you need to pick 60 numbers out of a possible 490 numbers, then this program
will tell you that your odds are 1 in 7163958434619955574151162225400929334117176
12789263493493351 013459481104668848. Good luck!
The program in Listing 3–5 computed the statement
lotteryOdds = lotteryOdds * (n - i + 1) / i;
When big numbers are used, the equivalent statement becomes
lotteryOdds = lotteryOdds.multiply(BigInteger.valueOf(n - i + 1)).divide(BigInteger.valueOf(i));
Listing 3–6 BigIntegerTest.java
1. import java.math.*;
2. import java.util.*;
3.
4. /**
5. * This program uses big numbers to compute the odds of winning the grand prize in a lottery.
6. * @version 1.20 2004-02-10
7. * @author Cay Horstmann
8. */
9. public class BigIntegerTest
10. {
11. public static void main(String[] args)
12. {
13. Scanner in = new Scanner(System.in);
14.
15. System.out.print("How many numbers do you need to draw? ");
16. int k = in.nextInt();
17.
18. System.out.print("What is the highest number you can draw? ");
19. int n = in.nextInt();
20.
21. /*
22. * compute binomial coefficient n*(n-1)*(n-2)*...*(n-k+1)/(1*2*3*...*k)
23. */
24.
25. BigInteger lotteryOdds = BigInteger.valueOf(1);
26.
27. for (int i = 1; i <= k; i++)
28. lotteryOdds = lotteryOdds.multiply(BigInteger.valueOf(n - i + 1)).divide(
29. BigInteger.valueOf(i));
30.
31. System.out.println("Your odds are 1 in " + lotteryOdds + ". Good luck!");
32. }
33. }

java.math.BigInteger

? BigInteger add(BigInteger other)
? BigInteger subtract(BigInteger other)
? BigInteger multiply(BigInteger other)
? BigInteger divide(BigInteger other)
? BigInteger mod(BigInteger other)
returns the sum, difference, product, quotient, and remainder of this big integer and
other.
? int compareTo(BigInteger other)
returns 0 if this big integer equals other, a negative result if this big integer is less
than other, and a positive result otherwise.
? static BigInteger valueOf(long x)
returns a big integer whose value equals x.
? BigDecimal add(BigDecimal other)
? BigDecimal subtract(BigDecimal other)
? BigDecimal multiply(BigDecimal other)
? BigDecimal divide(BigDecimal other, RoundingMode mode) 5.0
returns the sum, difference, product, or quotient of this big decimal and other.
To compute the quotient, you must supply a rounding mode. The mode
RoundingMode.HALF_UP is the rounding mode that you learned in school (i.e., round
down digits 0 . . . 4, round up digits 5 . . . 9). It is appropriate for routine
calculations. See the API documentation for other rounding modes.
? int compareTo(BigDecimal other)
returns 0 if this big decimal equals other, a negative result if this big decimal is less
than other, and a positive result otherwise.
? static BigDecimal valueOf(long x)
? static BigDecimal valueOf(long x, int scale)
returns a big decimal whose value equals x or x /10scale.


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理