題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3680
題意：給定兩數(shù)n，m(0< n,m < 10^500)，要求用三種操作(-,+,*2)完成從m變換到n
題解：咋眼看還以為是簡單水題，http://poj.org/problem?id=3278 就是這題的原始版，
并且這個題目下面還白紙黑字寫明(0<N,M<10500)，匆忙寫個BFS提交，結(jié)果RE，其實題目的數(shù)據(jù)范圍
應(yīng)該是0<N,M<10^500。。。
暴搜行不通，就要有個好點(diǎn)的方法，想了一下想不到，結(jié)果看了個解題報告，才知道怎么解決

如果m > n：只有減操作
如果n > m：可以從后往前推算：
設(shè)f(x,n)表示數(shù)x變換到n需要的步數(shù) f(x,n)
那么如果x為奇數(shù)：f(x,n) = f(x/2,n) + 2
如果x為偶數(shù) ：f(x,n) = f(x/2,n) + 1
當(dāng)前答案即為 abs(m-x) + f(x,m)
一直計算直到2*x > m 。
只需要計算x和x+1的步數(shù)即可，如何證明？
以下以(x,n,y)表示，其中y = f(x,n)
 分別討論x和x+1的奇偶性，(x/2,n,y1)和((x+k)/2,n,y2)的大小(作差)
結(jié)果發(fā)現(xiàn)當(dāng)k>=2時，y2 > y1。

由于要大數(shù)，所以用java比較方便。。。
 

代碼：

import java.io.*;
import java.util.*;
import java.math.*;

public class Main 
{    
    public static Scanner in = new Scanner(System.in);
    public static BigInteger Abs(BigInteger num)
    {
        return num.abs();
    }
    public static BigInteger Min(BigInteger num1,BigInteger num2)
    {
        return num1.min(num2);
    }
    public static void main(String[] args) 
    {
        BigInteger n,m;
        while(true)
        {
            n = in.nextBigInteger();
            m = in.nextBigInteger();
            if((n.compareTo(BigInteger.ZERO) == 0) || (m.compareTo(BigInteger.ZERO) == 0))
            {
                break;
            }
            else
            {
                if(m.compareTo(n) > 0)
                {
                    System.out.println(m.subtract(n));
                }
                else
                {
                    BigInteger x1,x2,y1,y2,x;
                    x = n;
                    x1 = BigInteger.ZERO;
                    x2 = BigInteger.ONE;
                    BigInteger ans = n.subtract(m);
                    while(x.multiply(BigInteger.valueOf(2)).compareTo(m) > 0)
                    {
                        //x為偶數(shù)
                        if(x.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) == 0)
                        {
                            y1 = Min(x1.add(BigInteger.valueOf(1)),x2.add(BigInteger.valueOf(2)));
                            //x+1為奇數(shù)
                            y2 = Min(x1.add(BigInteger.valueOf(2)),x2.add(BigInteger.valueOf(2)));
                        }
                        else
                        {
                            //x為奇數(shù)
                            y1 = Min(x1.add(BigInteger.valueOf(2)),x2.add(BigInteger.valueOf(2)));
                            //x+1為偶數(shù)
                            y2 = Min(x1.add(BigInteger.valueOf(2)),x2.add(BigInteger.valueOf(1)));
                        }

                        x = x.divide(BigInteger.valueOf(2));
                        x1 = y1;
                        x2 = y2;
                        //x的步數(shù)
                        ans = Min(ans,Abs(x.subtract(m)).add(y1));
                        //x+1的步數(shù)
                        ans = Min(ans,Abs(x.subtract(m).add(BigInteger.ONE)).add(y2));
                    }

                    System.out.println(ans);
                }
            }
        }
    }
}