ZOJ 3987(バイナリ列挙+java大数)

2673 ワード

タイトルリンク:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3987
題意:1つの数nと1つの数mをあげて、nという数をmの数に分けて加算して、このmの数のor値が最小になります.
考え方:直接バイナリの角度から考えて、m個数のor値を最小にして、つまりm個数の中で最高位はできるだけ低くすべきで、私達はまず1つのk
(2^k−1)*m>n>(2^(k−1)*mであれば、m個のバイナリ数のうち少なくとも1個の数の最高位がkであることが分かる.今私たちはあるいは演算をするので、この時できるだけ多くの数のk位を1にしなければならないので、答えans+=2^kは、nが0になるまで高位から低位にプッシュします.
コード:
 
import java.util.*;
import java.math.*;
public class Main{
    public static void main(String[] args){
        Scanner cin=new Scanner(System.in);
        int T=cin.nextInt();
        while(T-->0){
            BigInteger n=cin.nextBigInteger();
            BigInteger m=cin.nextBigInteger();
            BigInteger ans=BigInteger.valueOf(0);
            BigInteger nn=n;
            int len=0;
            while(nn.compareTo(BigInteger.ZERO)>0){
                nn=nn.divide(BigInteger.valueOf(2));
                len++;
            }
            for(int i=len-1;i>=0;i--){
                BigInteger num1=BigInteger.valueOf(2).pow(i).subtract(BigInteger.ONE);
                BigInteger num2=num1.multiply(m);
                while(num2.compareTo(n)<0){
                    BigInteger num3=n.divide(BigInteger.valueOf(2).pow(i));
                    if(num3.compareTo(m)>0) num3=m;
                    n=n.subtract(BigInteger.valueOf(2).pow(i).multiply(num3));
                    ans=ans.add(BigInteger.valueOf(2).pow(i));
                }
            }
            System.out.println(ans);
        }
    }
}