2017CCPC秦皇岛G ZOJ 3987Numbers（大数+贪心）

Numbers

Time Limit: 2 Seconds Memory Limit: 65536 KB

DreamGrid has a nonnegative integer n $. He would like to divide n into m nonnegative integers a1,a2,...am and minimizes their bitwise or (i.e.a1+a2+...+am=n and a1 OR a2 OR a3...OR am should be as small as possible).$

Input

There are multiple test cases. The first line of input contains an integer $, indicating the number of test cases. For each test case:$

The first line contains two integers n $and m ( 0<=n<=1e1000 1<=m<=1e100).$

It is guaranteed that the sum of the length of $does not exceed 20000$

Output

For each test case, output an integer denoting the minimum value of their bitwise or.

Sample Input

Sample Output

Author: LIN, Xi
Source: The 2017 China Collegiate Programming Contest, Qinhuangdao Site

/*
* 题意：给你一个1e1000的数，让你分成最多1e100位，然后互相进行或运算，得到的值最小
*
* 思路：让高位最小然后向低位贪心,判断当前为能否为0，能为0的条件是,后面几位都是1,并且有m个,加起来如果大于当前值的话
*   那么这位就可以为0,否则只能为1,既然为1了,那么尽量多填1,这样保证了结果最优    
* */
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner in=new Scanner(System.in);
        int t;
        BigInteger n,m,x,sum;
        BigInteger [] pre=new BigInteger[4005];//表示后缀和
        String s;
        x=new BigInteger("1");
        pre[0]=new BigInteger("0");
        for(int i=1;i<4005;i++){
            pre[i]=pre[i-1].add(x);
            x=x.multiply(new BigInteger("2"));
        }
        t=in.nextInt();
        for(int ca=0;ca<t;ca++){
            n=in.nextBigInteger();
            m=in.nextBigInteger();
            sum=n;
            int tol=0;
            while(n.compareTo(new BigInteger("0"))==1){
                tol++;
                n=n.divide(new BigInteger("2"));
            }
            x=new BigInteger("0");
            //判断这一位的累加和能不能用后边的所有空间放下，能的话就转移到下一位，不能的话就把这一位都填满
            for(int i=tol;i>=1;i--){//枚举每位
                x=x.multiply(new BigInteger("2"));
                int ok=sum.compareTo(pre[i - 1].multiply(m));
                if ( ok<=0) {//能用剩余的空间放下
                    continue;
                } else {//放不下
                    x = x.add(new BigInteger("1"));
                    BigInteger cur = pre[i].subtract(pre[i - 1]);
                    BigInteger cnt = sum.divide(cur);
                    if (cnt.compareTo(m) >= 0) {
                        sum = sum.subtract(cur.multiply(m));
                    } else {
                        sum = sum.subtract(cur.multiply(cnt));
                    }
                }
            }
            System.out.println(x);
        }
    }
}