ZOJ - 3987

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 nnn 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

让高位最小然后向低位贪心，判断当前为能否为0，能为0的条件是后面几位都是1，并且有m个，加起来如果大于当前值的话那么这位就可以为0，否则只能为1，既然为1了，那么尽量多填1，这样保证了结果最优。

Copy From 907

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#Copy From 907
T = int(input())
for t in range(T):
	n,m = [int(x) for x in input().split()]
	ans,p = int(0),int(1)
	while((p - 1) * m < n):
		p <<= 1
	while(n != 0):
		while((p-1) * m >= n):
			p >>= 1
		ans += p
		if(p * m <= n):
			n -= p * m
		else:
			n %= p
	print(ans)