Java大数

java.math包中的BigInteger类和BigDecimal类分别提供任意精度的整数和小数运算。

1、BigInteger类

①导入：import java.math.BigInteger;

②常用方法：

BigInteger valueOf(long val) 【转换】
int compareTo(BigInteger val) 【返回值1、0、-1分别表示大于、等于、小于】
BigInteger add(BigInteger augend) 【加法】
BigInteger subtract(BigInteger subtrahend) 【减法】
BigInteger multiply(BigInteger multiplicand) 【乘法】
BigInteger divide(BigInteger divisor) 【除法】
BigInteger mod(BigInteger divisor) 【取模，返回值非负】
BigInteger pow(int n) 【幂】
String toString() 【返回此BigInteger的十进制字符串表示形式】
String toString(int radix) 【返回此BigInteger的radix进制字符串表示形式】

2、BigDecimal类

①导入：import java.math.BigDecimal;

②常用方法：

BigDecimal valueOf(double val) 【转换】
BigDecimal stripTrailingZeros() 【移除尾部的0】
int compareTo(BigDecimal val) 【返回值1、0、-1分别表示大于、等于、小于】
BigDecimal add(BigDecimal augend) 【加法】
BigDecimal subtract(BigDecimal subtrahend) 【减法】
BigDecimal multiply(BigDecimal multiplicand) 【乘法】
BigDecimal divide(BigDecimal divisor) 【除法】
BigDecimal pow(int n) 【幂】
String toPlainString() 【返回不带指数的字符串表示】
String toString() 【返回字符串表示形式，如果需要指数，则使用科学记数法】

hdoj 1002 A + B Problem II （大数加法）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1002

 1 import java.util.Scanner;
 2 import java.math.BigInteger;
 3 
 4 public class Main{
 5     public static void main(String args[]){
 6         Scanner cin=new Scanner(System.in);
 7         int t=cin.nextInt();
 8         for(int i=1;i<=t;i++){
 9             BigInteger a=cin.nextBigInteger();
10             BigInteger b=cin.nextBigInteger();
11             BigInteger sum=a.add(b);
12             if(i!=1) System.out.println();
13             System.out.println("Case " + i + ":");
14             System.out.println(a + " + " + b + " = " +sum);
15         }
16     }
17 }

View Code

hdoj 1042 N! （大数乘法）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1042

 1 import java.util.Scanner;
 2 import java.math.BigInteger;
 3 
 4 public class Main{
 5     public static void main(String args[]){
 6         Scanner cin=new Scanner(System.in);
 7         while(cin.hasNextInt()){
 8             int n=cin.nextInt();
 9             BigInteger ans=BigInteger.ONE;
10             for(int i=1;i<=n;i++){
11                 BigInteger a=BigInteger.valueOf(i);
12                 ans=ans.multiply(a);
13             }
14             System.out.println(ans);
15         }
16     }
17 }

View Code

hdoj 1063 Exponentiation （大数的幂）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1063

 1 import java.util.Scanner;
 2 import java.math.BigDecimal;
 3 
 4 public class Main{
 5     public static void main(String args[]){
 6         Scanner cin=new Scanner(System.in);
 7         while(cin.hasNext()){
 8             BigDecimal a=cin.nextBigDecimal();
 9             int n=cin.nextInt();
10             a=a.pow(n);
11             a=a.stripTrailingZeros();
12             String ans=a.toPlainString();
13             if(ans.charAt(0)=='0') ans=ans.substring(1);
14             System.out.println(ans);
15         }
16     }
17 }

View Code

hdoj 1715 大菲波数 （大数加法）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1715

 1 import java.util.Scanner;
 2 import java.math.BigInteger;
 3 
 4 public class Main {
 5     public static void main(String args[]){
 6         BigInteger[] f=new BigInteger[1001];
 7         f[1]=f[2]=BigInteger.ONE;
 8         for(int i=3;i<=1000;i++) f[i]=f[i-1].add(f[i-2]);
 9         Scanner cin=new Scanner(System.in);
10         int n=cin.nextInt();
11         for(int j=1;j<=n;j++){
12             int m=cin.nextInt();
13             System.out.println(f[m]);
14         }
15     }
16 }

View Code

poj 1131 Octal Fractions （大数加法 + 乘法 + 除法）

题目链接：http://poj.org/problem?id=1131

 1 import java.util.Scanner;
 2 import java.math.BigDecimal;
 3 
 4 public class Main {
 5     public static void main(String[] args){
 6         BigDecimal eight=BigDecimal.valueOf(8);
 7         Scanner cin=new Scanner(System.in);
 8         while(cin.hasNext()){
 9             String s=cin.next();
10             BigDecimal b=BigDecimal.ZERO;
11             BigDecimal t=BigDecimal.ONE;
12             for(int i=2;i<s.length();i++){
13                 t=t.divide(eight);
14                 BigDecimal temp=BigDecimal.valueOf(s.charAt(i)-'0').multiply(t);
15                 b=b.add(temp);
16             }
17             String ss=b.stripTrailingZeros().toPlainString();
18             System.out.println(s+" [8] = "+ss+" [10]");
19         }
20     }
21 }

View Code

hdoj 1297 Children’s Queue （递推 + 大数加法）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1297

解题思路：

设 a_n 为 n 个人的合法队列数，以下按最后一个人的性别进行分析：
1、若 n 个人的合法队列的最后一个人是男，则对前 n-1 个人的队列没有任何限制，所以这种情况有 a_n-1 种。
2、若 n 个人的合法队列的最后一个人是女，则队列的第 n-1 个人必为女，即队列最后两人为女：
①若队列的前 n-2 个人是合法队列，则队列一定是合法的，这种情况有 a_n-2 种。
②若队列的前 n-2 个人是不合法队列，则不合法的地方必是尾巴，即其形式必为“前 n-4 个人+男+女”，这种情况有 a_n-4 种。
综上所述，可得递推公式为：a_n = a_n-1 + a_n-2 + a_n-4 (n>4).

 1 import java.util.Scanner;
 2 import java.math.BigInteger;
 3 
 4 public class Main {
 5     public static void main(String[] args){
 6         BigInteger[] a=new BigInteger[1001];
 7         a[1]=BigInteger.ONE;
 8         a[2]=BigInteger.valueOf(2);
 9         a[3]=BigInteger.valueOf(4);
10         a[4]=BigInteger.valueOf(7);
11         for(int i=5;i<=1000;i++) a[i]=a[i-1].add(a[i-2]).add(a[i-4]);
12         Scanner cin=new Scanner(System.in);
13         while(cin.hasNextInt()){
14             int n=cin.nextInt();
15             System.out.println(a[n]);
16         }
17     }
18 }

View Code

zoj 1962 How Many Fibs? （大数加法 + 比较）

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=962

 1 import java.util.Scanner;
 2 import java.math.BigInteger;
 3 
 4 public class Main {
 5     public static void main(String[] args){
 6         BigInteger zero=BigInteger.ZERO;
 7         BigInteger[] f=new BigInteger[501];
 8         f[1]=BigInteger.ONE;
 9         f[2]=BigInteger.valueOf(2);
10         for(int i=3;i<=500;i++) f[i]=f[i-1].add(f[i-2]);
11         Scanner cin=new Scanner(System.in);
12         while(cin.hasNextBigInteger()){
13             BigInteger a=cin.nextBigInteger();
14             BigInteger b=cin.nextBigInteger();
15             if(a.compareTo(zero)==0 && b.compareTo(zero)==0) break;
16             int count=0,j=1;
17             while(f[j].compareTo(a)==-1) j++;
18             while(f[j].compareTo(b)!=1){
19                 j++;
20                 count++;
21             }
22             System.out.println(count);
23         }
24     }
25 }

View Code

poj 1503 Integer Inquiry （大数加法 + 比较）

题目链接：http://poj.org/problem?id=1503

 1 import java.util.Scanner;
 2 import java.math.BigInteger;
 3 
 4 public class Main {
 5     public static void main(String[] args){
 6         Scanner cin=new Scanner(System.in);
 7         BigInteger zero=BigInteger.ZERO;
 8         BigInteger sum=zero;
 9         while(cin.hasNextBigInteger()){
10             BigInteger a=cin.nextBigInteger();
11             if(a.compareTo(zero)==0) break;
12             sum=sum.add(a);
13         }
14         System.out.println(sum);
15     }
16 }

View Code