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();

            }

        }

    }

}

巴特西

luoguP1045 （Java大数）

最新文章

热门文章