O(1) 的小樂

DIV 2 1000

給定兩個整數(shù)，N，M N可以到達N+N的約數(shù)，求從N到達M的最短路徑？

實質(zhì)上就是一個BFS問題，復(fù)雜度就是O(sqrt(M)*M);

int dp[100020];
class DivisorInc
{
        public:
        int countOperations(int N, int M)
        {
            for(int i=N; i<=M; i++) dp[i]= M+M;
            dp[N]=0;
            for(int i=N; i<=M; i++)
            {
                for(int j=2; j*j<=i; j++)
                {
                    if(i%j==0)
                    {
                        if(i+j<=M) dp[i+j] = min(dp[i+j], dp[i]+1);
                        if(i+ i/j<=M) dp[i+i/j] =min(dp[i+i/j], dp[i]+1);
                    }
                }
            }
            if(dp[M] > M) return -1;
            else return dp[M];

        }
};