[CCPC] 2017秦皇岛 NumbersI | Java BigInteger | 贪心

[CCPC] 2017秦皇岛 NumbersI | Java BigInteger | 贪心

题目描述

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. n=a1+a2+…+am and a1 OR a2 OR … OR am 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≤n＜101000,1≤m＜10100). It is guaranteed that the sum of the length of n does not exceed 20000.

output

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

样例输入

53 13 23 310000 51244 10

样例输出 Copy

3312000125

main_code:

import java.math.BigInteger;import java.util.Scanner; public class Main { public static BigInteger a[] = new BigInteger[5007];///2 ** x public static void main(String[] args) { Scanner cin = new Scanner(System.in); int pos = 0; a[0] = BigInteger.valueOf(1); for(int i=1;i<=5000;i++){ a[i] = a[i-1].multiply(BigInteger.valueOf(2)); }// System.out.println(a[3]); int T = cin.nextInt(); BigInteger n,m; while(T > 0) { T -= 1; n = cin.nextBigInteger(); m = cin.nextBigInteger(); if (m.equals(BigInteger.valueOf(1))) {/// m == 1 System.out.println(n); continue; } BigInteger tn = n; BigInteger sum = BigInteger.valueOf(0), ans = BigInteger.valueOf(0); for (int i = 0; ; i++) { if(sum.compareTo(n) >= 0) break; sum = sum.add(m.multiply(a[i])); pos = i; } for (int i = pos; i >= 0; i--) { BigInteger t = a[i].subtract(BigInteger.valueOf(1)); if (t.multiply(m).compareTo(tn) >= 0) { continue; } BigInteger cnt = tn.divide(a[i]); cnt = cnt.min(m); ans = ans.add(a[i]); tn = tn.subtract(cnt.multiply(a[i])); } System.out.println(ans); } }}/** 5 3 1 3 2 3 3 10000 5 1244 10 * **/ /************************************************************** Problem: 4827 Language: Java Result: 正确 Time:1058 ms Memory:85000 kb****************************************************************/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。