# ZOJ 3987 Numbers （贪心）

## Description

DreamGrid has a nonnegative integer $n$. He would like to divide $n$ into $m$ nonnegative integers $a_1, a_2, \dots, a_m$ and minimizes their bitwise or (i.e. $n=a_1 + a_2 + \dots + a_m$ and $a_1 \text{ OR } a_2 \text{ OR } \dots \text{ OR } a_m$ should be as small as possible).

## Input

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

The first line contains two integers $n$ and $m$ ( $0 \le n < 10^{1000}, 1 \le m < 10^{100}$ ). 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

5
3 1
3 2
3 3
10000 5
1244 10


## Sample Output

3
3
1
2000
125


## 思路

• 若可以，则说明溢出部分会被放置在当前位，于是尽可能多的填充当前第 $i$ 位共 $m$ 个二进制位。
• 若不可以，则说明剩余的数字可以被安置在低位，当前位为 $0$ 。

## AC 代码

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

public class Main {

private static Scanner cin;
static BigInteger n, m;

public static void solve() {
int len = 0;
BigInteger tmp = n;
while (tmp.compareTo(BigInteger.ZERO) != 0) {
tmp = tmp.shiftRight(1);
len++;
}
BigInteger ans = BigInteger.ZERO;
for (int i = len - 1; i >= 0 && n.compareTo(BigInteger.ZERO) > 0; i--) {
BigInteger cnt = BigInteger.ONE.shiftLeft(i);
tmp = cnt.subtract(BigInteger.ONE).multiply(m); // 检验n是否可以填满m个低位
if (tmp.compareTo(n) < 0) { // 若不可以填满则说明当前位一定被占用
n = n.subtract(cnt.multiply(m.min(n.shiftRight(i)))); // 尽可能多的填充当前位
ans = ans.or(cnt);
}
}
System.out.println(ans);
}

public static void main(String[] args) {
cin = new Scanner(System.in);
int T;
T = cin.nextInt();
while ((T--) > 0) {
n = cin.nextBigInteger();
m = cin.nextBigInteger();
solve();
}
}
}