Java在ACM中简单应用（主要是大数）

Love The Way You Lie 2023-10-12 07:58 25阅读 0赞

#  Java在ACM中简单应用 #

--------------------

## 一、Java大数应用 ##

--------------------

大一就听学长们说Java在大数上可以说很凶猛了，于是乘着这学期学Java于是试着先了解了解Java在ACM中的简单操作

通过hdu1000[（题目链接）][Link 1]这个水题，发现了几个需要注意的地方：

1、Java中的多组输入同样是调用Java中的util包中的Scanner方法  
具体见下面代码

2、提交时不能出现包名，

3、类名(Class）只能是Main

于是代码为：

import java.util.Scanner;
    public class Main {
        
    	public static void main(String args[]) {
        
    		long a,b;
    		Scanner scan=new Scanner(System.in);
    		while(scan.hasNext()) {
        
    			a=scan.nextLong();
    			b=scan.nextLong();
    			System.out.println(a+b);
    		}
    	}
    }

接下来就是重头戏了，Java大数应用

为了解决大数（即：爆long long的数）的问题，Java中提供了两个操作类

BigInteger：大数整数操作  
BigDecimal：大数小数操作

当然这些大数都会以**字符串**的形式传入

下面的借鉴的这位大佬的博客：[https://blog.csdn.net/zhongkelee/article/details/52289163][https_blog.csdn.net_zhongkelee_article_details_52289163]

--------------------

## BigInteger： ##

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]

import java.util.Scanner;
    import java.math.*;
    public class Test {
        
    	public static void main(String args[]) {
        
    		BigInteger num1=new BigInteger("123456789");
    		
    		BigInteger num2=new BigInteger("9876543321");
    		
    		System.out.println("加法："+num2.add(num1));
    		System.out.println("减法："+num2.subtract(num1));
    		System.out.println("乘法："+num2.multiply(num1));
    		System.out.println("除法："+num2.divide(num1));
    		System.out.println("最大数："+num2.max(num1));
    		System.out.println("最小数："+num1.min(num1));
    		
    		BigInteger result[]=num2.divideAndRemainder(num1);
    		
    		System.out.println("商是："+result[0]+"，余数是："+result[1]);
    	}
    	public static void main(String args[]) {
        
    		
    	}
    }

--------------------

## BigDecimal： ##

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70 1]

package ustc.lichunchun.bigdataapi;
     
    import java.math.BigDecimal;
     
    public class BigDecimalDemo01 {
        
     
    	public static void main(String[] args) {
        
    		System.out.println("加法运算：" + MyMath.round(MyMath.add(10.345,3.333),1)) ;
    		System.out.println("减法运算：" + MyMath.round(MyMath.sub(10.345,3.333),3)) ;
    		System.out.println("乘法运算：" + MyMath.round(MyMath.mul(10.345,3.333),4)) ;
    		System.out.println("除法运算：" + MyMath.div(10.345,3.333,3)) ;
    	}
    }
    class MyMath{
        
    	public static double add(double d1,double d2){
        		// 进行加法计算
    		BigDecimal b1 = new BigDecimal(d1) ;
    		BigDecimal b2 = new BigDecimal(d2) ;
    		return b1.add(b2).doubleValue() ;
    	}
    	public static double sub(double d1,double d2){
        		// 进行减法计算
    		BigDecimal b1 = new BigDecimal(d1) ;
    		BigDecimal b2 = new BigDecimal(d2) ;
    		return b1.subtract(b2).doubleValue() ;
    	}
    	public static double mul(double d1,double d2){
        		// 进行乘法计算
    		BigDecimal b1 = new BigDecimal(d1) ;
    		BigDecimal b2 = new BigDecimal(d2) ;
    		return b1.multiply(b2).doubleValue() ;
    	}
    	public static double div(double d1,double d2,int len){
        		// 进行除法计算
    		BigDecimal b1 = new BigDecimal(d1) ;
    		BigDecimal b2 = new BigDecimal(d2) ;
    		return b1.divide(b2,len,BigDecimal.ROUND_HALF_UP).doubleValue() ;
    	}
    	public static double round(double d,int len){
        	// 进行四舍五入
    		BigDecimal b1 = new BigDecimal(d) ;
    		BigDecimal b2 = new BigDecimal(1) ; // 技巧
    		return b1.divide(b2,len,BigDecimal.ROUND_HALF_UP).doubleValue() ;
    	}
    };

来道开胃菜：  
**BigInteger应用：**  
[一、hdu 1002：A + B Problem II][hdu 1002_A _ B Problem II]

import java.util.Scanner;
    import java.math.*;
    public class Main {
        
    	public static void main(String args[]) {
        
    		Scanner scan=new Scanner(System.in);
    		int n=scan.nextInt();
    		for(int i=1;i<=n;i++) {
        
    			BigInteger a=scan.nextBigInteger();
    			BigInteger b=scan.nextBigInteger();
    			System.out.println("Case "+i+":");
    			System.out.println(a+" + "+b+" = "+a.add(b));
    			if(i!=n)
    				System.out.println();
    		}
    	}
    }

[二、HDU 1316：How Many Fibs?][HDU 1316_How Many Fibs]  
**题意：**  
给定一个区间【l，r】，求该区间内有多少个斐波拉契数

**题解：**  
由于数值很大，即：大整数。于是用Java的BigInteger类即可  
需要注意的是：  
Java大数比较大小，需要用到.compareTo()方法，具体见代码。

import java.math.BigDecimal;
    import java.math.BigInteger;
    import java.util.*;
    public class Main {
        
        public static void main(String args[]) {
        
            Scanner scan=new Scanner(System.in);
            BigInteger[] a=new BigInteger[100010];
            a[1]=BigInteger.valueOf(1);
            a[2]=BigInteger.valueOf(2);
            for(int i=3;i<=100000;i++) {
        
                a[i]=a[i-1].add(a[i-2]);
                int flag=a[i].compareTo(BigInteger.valueOf(10).pow(100));
                /**
                 * .compareTo()函数返回一个int类型的值
                 * 其中：-1表示前者小于后者；0表示相等；1表示前者大于后者
                 */
                if(flag==1) {
        
                    break;
                }
            }
            while(scan.hasNext()) {
        
                BigInteger l=scan.nextBigInteger();
                BigInteger r=scan.nextBigInteger();
                if(l.compareTo(BigInteger.valueOf(0))==0&&r.compareTo(BigInteger.valueOf(0))==0)
                    break;
                int cnt=0;
                for(int i=1;i<=100000;i++) {
        
                    if(a[i].compareTo(l)==-1)
                        continue;
                    else if(a[i].compareTo(r)==1)
                        break;
                    else {
        
                        cnt++;
                    }
                }
                System.out.println(cnt);
            }
            
        }
        
    }

**BigDecimal应用：**

[一、HDU 1063：Exponentiation][HDU 1063_Exponentiation]  
**题意：**  
题意比较简单，就是求高精度小数的幂

**题解：**  
直接用Java的BigDecimal即可，需要注意的是要**去掉前缀0和尾部的0**

import java.math.BigDecimal;
    import java.math.BigInteger;
    import java.util.*;
    public class Main {
        
        public static void main(String args[]) {
        
            Scanner scan=new Scanner(System.in);
            while(scan.hasNext()) {
        
                BigDecimal r=scan.nextBigDecimal();
                int n=scan.nextInt();
                String s=r.pow(n).stripTrailingZeros().toPlainString();   //去掉尾部的0，并转化为字符串
                if(s.charAt(0)=='0')
                    s=s.substring(1);   //去掉前缀0
                System.out.println(s);
            }
            
        }
        
    }

[二、HDU 1753：大明A+B][HDU 1753_A_B]  
**题意：**  
就是两个正小数的高精度加法

**题解：**  
直接利用BigDecimal类，需要注意的是：防止出现4.0,1e5这样的情况，具体见代码

import java.math.BigDecimal;
    import java.math.BigInteger;
    import java.util.*;
    public class Main {
        
        public static void main(String args[]) {
        
            Scanner scan=new Scanner(System.in);
            while(scan.hasNext()) {
        
                BigDecimal a=scan.nextBigDecimal();
                BigDecimal b=scan.nextBigDecimal();
                /**
                 * 去掉尾部0,并转化为字符串(为了防止出现像4.0,1e5这样的情况)
                 */
                System.out.println(a.add(b).stripTrailingZeros().toPlainString());   
            }
            
        }
        
    }

--------------------

## 二、Java快速幂取模内置函数 ##

--------------------

[https://ac.nowcoder.com/acm/contest/3800/A][https_ac.nowcoder.com_acm_contest_3800_A]  
由于做了这一道快速幂取模的题，有简单的快速幂取模，发现long long根本存不下，于是试了试Java BigInteger发现比较复杂，于是开始了百度，居然还有这个函数

a.modPow(b, p);
    //其中a，b，p均是BigInteger类型的数

于是完整代码为：

import java.math.BigInteger;
    import java.util.Scanner;
    public class Main {
        
    	public static void main(String args[]) {
        
    		Scanner scan=new Scanner(System.in);
    		int t=scan.nextInt();
    		for(int i=1;i<=t;i++) {
        
    			BigInteger a=scan.nextBigInteger();
    			BigInteger b=scan.nextBigInteger();
    			BigInteger p=scan.nextBigInteger();
    			System.out.println(a.modPow(b, p));
    		}
    	}
    }

--------------------

## 三、Java大数进制转换 ##

--------------------

Java大数BigInteger中，存在n进制转换为10进制，以及10进制转换为n进制的操作

#### 1、n进制转换为10进制 ####

利用了BigInteger中的构造方法；

//利用了BigInteger中的构造方法；
    String a="123";
    int n=4;
    BigInteger num=new BigInteger(a,n);    //num为在n进制下的a转换为10进制得到的数

#### 2、10进制转换为n进制 ####

利用了BigInteger中的toString()方法；

//利用了BigInteger中的toString()方法
    BigInteger a=BigInteger.valueOf(123);
    int n=4;
    String num=a.toString(n);       //num为在10进制下的a转换为n进制下的数

来道开胃菜…  
[洛谷P1604 B进制星球][P1604 B]

代码如下：

import java.math.BigInteger;
    import java.util.*;
    public class Main{
        
    	public static void main(String args[]) {
        
    		Scanner scan=new Scanner(System.in);
    		
    		int n=scan.nextInt();
    		
    		//n进制下的两个数a,b
    		String a=scan.next(); 
    		String b=scan.next();
    		
    		//转化为10进制
    		BigInteger num1=new BigInteger(a,n);
    		BigInteger num2=new BigInteger(b,n);
    		
    		//求和
    		BigInteger sum=num1.add(num2);
    		
    		//转换为n进制
    		String s=new BigInteger(sum+"",10).toString(n);
    		
    		//由于10进制后字母表示的都是大写表示，所以转换为大写
    		s=s.toUpperCase();
    		
    		System.out.println(s);
    		
    	}
    	
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1000
[https_blog.csdn.net_zhongkelee_article_details_52289163]: https://blog.csdn.net/zhongkelee/article/details/52289163
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190922110300363.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190922110420340.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4,size_16,color_FFFFFF,t_70
[hdu 1002_A _ B Problem II]: http://acm.hdu.edu.cn/showproblem.php?pid=1002
[HDU 1316_How Many Fibs]: http://acm.hdu.edu.cn/showproblem.php?pid=1316
[HDU 1063_Exponentiation]: http://acm.hdu.edu.cn/showproblem.php?pid=1063
[HDU 1753_A_B]: http://acm.hdu.edu.cn/showproblem.php?pid=1753
[https_ac.nowcoder.com_acm_contest_3800_A]: https://ac.nowcoder.com/acm/contest/3800/A
[P1604 B]: https://www.luogu.com.cn/problem/P1604