openjudge4010: 2011(java BigInteger)

3/8/2017来源:ASP.NET技巧人气:977

http://bailian.openjudge.cn/PRactice/4010

题意:已知长度最大为200位的正整数n,请求出2011^n的后四位。

第一次用java BigInteger类,参考了一下BigInteger的一些方法,就可以写出大数快速幂。

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    static BigInteger base = new BigInteger("2011");
    static BigInteger MOD = new BigInteger("10000");
    static BigInteger zero = new BigInteger("0");
    static BigInteger one = new BigInteger("1");
    static BigInteger two = new BigInteger("2");
    public static BigInteger FastMul(BigInteger n){
        if(n.equals(one)){
            return base;
        }
        if(n.mod(two).equals(zero)){
            BigInteger ret = FastMul(n.divide(two));
            return ret.multiply(ret).mod(MOD);
        }
        else{
            return base.multiply(FastMul(n.subtract(one))).mod(MOD);
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        for(int i=0; i<k; ++i){
            BigInteger n = sc.nextBigInteger();
            BigInteger ans = FastMul(n);
            System.out.println(ans.mod(MOD));
        }
    }
}

ss