Numbers CCPC 大数除法

 1 import java.math.BigInteger;
 2 import java.util.Scanner;
 3  
 4 public class Main 
 5 {
 6     public static BigInteger two = BigInteger.valueOf(2);
 7     public static BigInteger one = BigInteger.ONE;
 8     public static BigInteger zero = BigInteger.ZERO;
 9     public static BigInteger n, m;
10     public static BigInteger a[] = new BigInteger[4005];
11     public static void init()
12     {
13         a[0] = one;
14         for(int i = 1; i <= 4002; i++)
15             a[i] = a[i - 1].multiply(two);
16     }
17     public static void main(String[] args) 
18     {
19         Scanner cin = new Scanner(System.in);
20         int t = cin.nextInt();
21         init();
22         while(t > 0)
23         {
24             t--;
25             int up = 0;
26             n = cin.nextBigInteger();
27             m = cin.nextBigInteger();
28             BigInteger sum = zero, temp = n, ans = zero;
29             for(int i = 0; sum.compareTo(n) < 0; i++)
30             {
31                 sum = sum.add(m.multiply(a[i]));
32                 up = i;
33             }
34             for(int i = up; i >= 0; i--)
35             {
36                 BigInteger b = a[i].subtract(one);
37                 //if(T.multiply(m).compareTo(temp) >= 0) continue;
38                 if((b.multiply(m)).compareTo(temp) >= 0) continue;
39                 BigInteger k = temp.divide(a[i]); // 可以分为几个
40                 k = k.min(m);
41                 ans = ans.add(a[i]);
42                 temp = temp.subtract(a[i].multiply(k)); // 减去
43             }
44             System.out.println(ans);
45         }
46         cin.close();
47     }
48 }