luoguP1045 （Java大数）

题目链接：https://www.luogu.org/problemnew/show/P1045

题意：给定p（1000<p<3100000），求2^p-1的位数和最后500位（若不足高位补零）。

思路：首先，2^p-1和2^p有相同的位数，因为2^p末位一定不为0。所以2^p-1的位数为log10(2^p)+1，即p*log10(2)+1。

　　　手写快速幂计算2^p，并对Mod=10^500取模，计算结果减一之后注意判断是否为负，若为负，则加上模数，之后将BigInteger转字符串输出即可。

代码：

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

public class Main {    
    public static BigInteger qpow(BigInteger a,int b,BigInteger Mod)
    {
        BigInteger ans = BigInteger.ONE;
        while(b!=0)
        {
            if((b&1)==1)
                ans = ans.multiply(a).mod(Mod);
            a = a.multiply(a).mod(Mod);
            b >>= 1;
        }
        return ans;
    }
    public static void main(String[] args)
    {
        Scanner cin = new Scanner(System.in);
        BigInteger two = BigInteger.valueOf(2);
        int p = cin.nextInt();
        BigInteger Mod=BigInteger.TEN.pow(500);
        BigInteger tmp = qpow(two,p,Mod);
        tmp = tmp.subtract(BigInteger.ONE);
        if(tmp.compareTo(BigInteger.ZERO)<0)
            tmp.add(Mod);
        String s=tmp.toString();
        int len=s.length();
        int cnt=0;
        System.out.println((int)(p*Math.log10(2)+1));
        for(int i=1;i<=500-len;++i){
            System.out.print('0');
            cnt++;
            if(cnt==50){
                cnt=0;
                System.out.println();
            }
        }
        for(int i=0;i<len;++i){
            System.out.print(s.charAt(i));
            cnt++;
            if(cnt==50){
                cnt=0;
                System.out.println();
            }
        }
    }
}