题意: 把 n 分成 m 份, 使得 or 值最小
首先, 我们要找到他的最高位, 如果 (2 * k - 1 ) * m> n> (2 *(k-1) - 1) * m, 然后我们就必须把 k 位赋为 1, 为什么呢? 你可以想一下 (2 * k - 1 ) * m 了, 然后如果 再不分的话, 就会超过 m 份.
- import java.math.BigInteger;
- import java.util.Scanner;
- public class Main
- {
- public static BigInteger two = BigInteger.valueOf(2);
- public static BigInteger one = BigInteger.ONE;
- public static BigInteger zero = BigInteger.ZERO;
- public static BigInteger n, m;
- public static BigInteger a[] = new BigInteger[4005];
- public static void init()
- {
- a[0] = one;
- for(int i = 1; i <= 4002; i++)
- a[i] = a[i - 1].multiply(two);
- }
- public static void main(String[] args)
- {
- Scanner cin = new Scanner(System.in);
- int t = cin.nextInt();
- init();
- while(t> 0)
- {
- t--;
- int up = 0;
- n = cin.nextBigInteger();
- m = cin.nextBigInteger();
- BigInteger sum = zero, temp = n, ans = zero;
- for(int i = 0; sum.compareTo(n) <0; i++)
- {
- sum = sum.add(m.multiply(a[i]));
- up = i;
- }
- for(int i = up; i>= 0; i--)
- {
- BigInteger b = a[i].subtract(one);
- //if(T.multiply(m).compareTo(temp)>= 0) continue;
- if((b.multiply(m)).compareTo(temp)>= 0) continue;
- BigInteger k = temp.divide(a[i]); // 可以分为几个
- k = k.min(m);
- ans = ans.add(a[i]);
- temp = temp.subtract(a[i].multiply(k)); // 减去
- }
- System.out.println(ans);
- }
- cin.close();
- }
- }
来源: http://www.bubuko.com/infodetail-3680238.html