洛谷P1045 [NOIP2003 普及组] 麦森数--Java使用快速幂

青旅半醒 2023-01-11 09:11 167阅读 0赞

# 洛谷P1045 \[NOIP2003 普及组\] 麦森数–Java使用快速幂 #

[题目链接][Link 1]

## 基本思路 ##

通过使用快速幂取模节省运算时间,然后使用大数类保证高精度

## 代码 ##

import java.math.BigInteger;
    import java.util.*;
    public class Main {
        
    	public static void main(String[] args) {
        
    		Scanner sc=new Scanner(System.in);
    		int n=sc.nextInt();
    		System.out.println((int)(n*Math.log10(2))+1);
    		//计算麦森数后500位
    		BigInteger big=pow(BigInteger.valueOf(2),n);
    		big=big.subtract(BigInteger.ONE);
    		String s=big.toString();
    		while(s.length()<500) {
        
    			s="0"+s;
    		}
    		s=s.substring(s.length()-500,s.length());
    		int start=0;
    		for(int i=0;i<10;i++) {
        
    			if(i==9) System.out.print(s.substring(start,start+50));
    			else System.out.println(s.substring(start,start+50));
    			start+=50;
    		}
    		sc.close();
    		return;
    	}
    	// 快速幂实现
    	public static BigInteger pow(BigInteger big,int n) {
        
    		BigInteger mod=BigInteger.TEN.pow(500);
    		BigInteger res=BigInteger.ONE;
    		while(n!=0) {
        
    			if((n&1)==1) res=res.multiply(big).mod(mod);
    			big=big.multiply(big).mod(mod);
    			n=n>>1;
    		}
    		return res;
    	}
    }

其中,快速幂还有一种写法,这种方法是先将指数二进制未处的1省去,似乎可以加快部分时间,但效果基本上不明显,不太推荐这种写法

public static BigInteger pow(BigInteger big,int n) {
        
    		BigInteger mod=BigInteger.TEN.pow(500);
    		if(n==0) return BigInteger.ZERO;
    		else {
        
    			while((n&1)==0) {
        
    				big=big.multiply(big).mod(mod);
    				n=n>>1;
    			}
    		}
    		BigInteger res=BigInteger.ONE;
    		res=res.multiply(big).mod(mod);
    		n=n>>1;
    		while(n!=0) {
        
    			big=big.multiply(big).mod(mod);
    			if((n&1)==1) res=res.multiply(big).mod(mod);
    			n=n>>1;
    		}
    		return res.mod(mod);
    	}

[Link 1]: https://www.luogu.com.cn/problem/P1045