Java大数练习 运用BigInteger类的各种方法

作者:nefu-ljw

时间:2020年3月4日

来源:CSDN

Q:孩子三岁还不会写高精度怎么办?

A:来学Java吧!学会Java大数,解决你的烦恼!(虽然Python更加简单,但是ACM比赛不让用Python)

 

hdu 1042 N!

多组询问,求n的阶乘,n最大到1e4。大数乘法,需要用到BigInteger类中的multiply方法了。
(Java概念:Java中的”方法”即C++中的”函数”,由类创建的对象来调用方法)

import java.util.*;//星号*(通配符)表示包中所有的类
import java.math.*;//含BigInteger类

public class Main {

    public static void main(String [] args) {
       	final int N=(int)1e4;//声明常量N 类似C++中的const int N=1e4 
		//java中的1e4是double类型,需要强制转换
		//final关键字表示变量无法赋值修改
        Scanner cin=new Scanner(System.in);
        BigInteger a[]=new BigInteger[N+10];
        a[0]=BigInteger.ONE;//a[0]=1
        for(int i=1;i<=N;i++) 
            a[i]=a[i-1].multiply(BigInteger.valueOf(i));
        //注意把int类型的i转化为BigInteger类型的方法:BigInteger.valueOf(i)
        while(cin.hasNext()) {
            int n=cin.nextInt();
            System.out.println(a[n]);
        }
    }
}

洛谷 P1932 A+B A-B A*B A/B A%B Problem

大数运算,加、减、乘、除、取余,C++不想写(不会写)怎么办?那就用Java大数吧!
(洛谷题解区的C语言代码动辄100行以上,大佬们可以用C++试试)

import java.util.*;//星号*(通配符)表示包中所有的类
import java.math.*;//含BigInteger类

public class Main {

    public static void main(String [] args) {
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext()) {
            BigInteger a=cin.nextBigInteger();
            BigInteger b=cin.nextBigInteger();
            System.out.println(a.add(b));//加
            System.out.println(a.subtract(b));//减
            System.out.println(a.multiply(b));//乘
            System.out.println(a.divide(b));//除
            System.out.println(a.mod(b));//取余
        }
    }
}

洛谷 P2152 [SDOI2009]SuperGCD

大数GCD,几行代码秒掉 提高+/省选- 难度的题。

import java.util.*;
import java.math.*;

public class Main {

	public static void main(String[] args) {
		Scanner cin=new Scanner(System.in);
		BigInteger a=cin.nextBigInteger();
		BigInteger b=cin.nextBigInteger();
		System.out.println(a.gcd(b));
	}
	
}

洛谷 P1045 麦森数

这题有点难啊,容易想到大数快速幂,但是直接乘的话会超时,因为Java自带的大数乘法是直接高精度模拟乘法的过程,是O(n2)的复杂度,n=3100000肯定超时了。

因为只要求最后500位,所以可以在进行大数快速幂的时候对10500取模。(10500也由大数快速幂得到)

对于求 2n-1 本来的位数len,分析一下:2n-1与2n位数相同(因为2n最后一位一定不为0,否则它会有5这个因子),所以可以直接用公式 len=(int)log10(2n)+1=(int)[n*log10(2)]+1。

Java求对数比较坑,只能求以e为底的对数,求log10(2)要用对数换底公式转换:log10(2)=loge(2)/loge(10)。

import java.util.*;//星号*(通配符)表示包中所有的类
import java.math.*;//含BigInteger类

public class Main {

    public static void main(String [] args) {
        Scanner cin=new Scanner(System.in);
        int n=cin.nextInt();
        BigInteger p=qpow(BigInteger.valueOf(10),500);//p是模数,p=10^500
        BigInteger s=qpowmod(BigInteger.valueOf(2),n,p);
        String ans=s.toString();
        double tmp=(Math.log(2)/Math.log(10));//log10(2)=loge(2)/loge(10)
        int len=(int)(1.0*n*tmp)+1;//用公式计算数的长度
        System.out.println(len);
        len=ans.length();//取模后ans中数的长度(注意可能不满500位)
        int num0=500-len;//0的个数
        for(int i=1;i<=num0;i++) {
        	System.out.printf("0");
        	if(i%50==0)System.out.println();
        }
        for(int i=num0+1;i<=500;i++) {
        	System.out.print(ans.charAt(i-1-num0));
        	if(i%50==0)System.out.println();
        }
    }
    
	static BigInteger qpow(BigInteger a,int b) {//快速幂求a^b
    	BigInteger s=BigInteger.ONE;
    	while(b!=0) {
    		if((b&1)==1) s=s.multiply(a);
    		a=a.multiply(a);
    		b=b/2;
    	}
    	return s;
    }
	
	static BigInteger qpowmod(BigInteger a,int b,BigInteger p) {//快速幂求(a^b-1)%p
    	BigInteger s=BigInteger.ONE;//s=1
    	while(b!=0) {
    		if((b&1)==1) {s=s.multiply(a);s=s.mod(p);}
    		a=a.multiply(a);
    		a=a.mod(p);
    		b=b/2;
    	}
    	s=s.subtract(BigInteger.ONE);//s=s-1
    	return s;
    }
}

测试数据

input 01

756839

output 01

227832
18288448825429774219846956862417770870640302475247
92828312585598040121588421297674731878093115313182
16753914541797571068392534875840214937021204750378
89055619401647443568291937923950889819022384242323
28767636683196318572845992994357198238764218257600
09234774987448978769799124034384499030364505405943
84275497234460834579807796823701486980464630401353
54915833132974601389482848422119619724789014565809
44396409267168409183491136926492417685905113427201
26927068487680404055813342880902603793328544677887

input 2

2976211

output 2

895929
09706254902780580488538638337749488166014345988326
02775279611779313026429691390417911643979834461015
82796840762652659657879019767719300642845223087116
62403659439552250198135538452083443036688067014742
34849992771496671872080263423105090982169268837394
90349237844608937582631965760646844828980604713404
94758793031585694216573044384886437022298236407514
12669234650178896555557671246448254579285995086138
17684057898736849005201669426891137948698576073174
93902398262481988755867710259809742681891351298047

UPD 2020.3.5 新收获

Java大数其实是自带快速幂和快速幂取模的!如果用普通的 Math.pow((double)a,(double)b) 可能会有精度误差而且范围也不够大,所以要求幂的话最好是用大数快速幂。

1、大数快速幂
pow方法 使用格式:a.pow(b),表示a^b,
其中a为BigInteger类,指数b必须是int类型。

2、大数快速幂取模
modPow方法 使用格式:a.modPow(b,c),表示a^b%c,
其中a,b,c均为BigInteger类。

洛谷 P1045 麦森数 这题可以直接调用自带方法(函数),不用手写快速幂,代码比较简洁。

import java.util.*;//星号*(通配符)表示包中所有的类
import java.math.*;//含BigInteger类
public class Main {
    public static void main(String [] args) {
        Scanner cin=new Scanner(System.in);
        int n=cin.nextInt();
        BigInteger p=BigInteger.TEN.pow(n);//p是模数,p=10^500
        BigInteger s=BigInteger.valueOf(2).modPow(BigInteger.valueOf(n),p).subtract(BigInteger.ONE);//s=2^n%p-1
        String ans=s.toString();
        double tmp=(Math.log(2)/Math.log(10));//log10(2)=loge(2)/loge(10)
        int len=(int)(1.0*n*tmp)+1;//用公式计算数的长度
        System.out.println(len);
        len=ans.length();//取模后ans中数的长度(注意可能不满500位)
        int num0=500-len;//0的个数
        for(int i=1;i<=num0;i++) {
        	System.out.printf("0");
        	if(i%50==0)System.out.println();
        }
        for(int i=num0+1;i<=500;i++) {
        	System.out.print(ans.charAt(i-1-num0));
        	if(i%50==0)System.out.println();
        }
    }
}

相关文章:

发表回复

您的电子邮箱地址不会被公开。