http://122.207.68.93/OnlineJudge/problem.php?id=1299

第二个样例解释..

3 6

3->4->6..两步..

由此可以BFS也可以DP..但关键是要离线把100000内每个数的约数情况预先处理出来..否则会超时...

Program:

#include<iostream>

#include<stdio.h>

#include<cmath>

#include<cstring>

#include<string.h>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

#define pi acos(-1)

#define ll long long

#define oo 2139062143

#define MAXN 200005

using namespace std;

struct node

{

       int next;

}h[MAXN];

int n,m,dp[MAXN],p[3000000][2];

int main()

{

       int x,i,k;

       m=0;

       memset(h,0,sizeof(h));

       memset(p,0,sizeof(p));

       for (i=1;i<=MAXN;i++)

          for (x=i*2;x<=MAXN;x+=i)

          {

                p[++m][0]=i;

                p[m][1]=h[x].next;

                h[x].next=m;

          }

       while (~scanf("%d%d",&n,&m))

       {

             memset(dp,0x7f,sizeof(dp));

             dp[n]=0;

             for (x=n;x<=m;x++)

             {

                   k=h[x].next;

                   while (k)

                   {

                        i=p[k][0];

                        if (x+i<=m)

                           if (dp[x+i]==-1 || dp[x+i]>dp[x]+1)

                              dp[x+i]=dp[x]+1;

                        k=p[k][1];

                   }

             }

             if (dp[m]==oo) printf("sorry, can not transform\n");

               else       printf("%d\n",dp[m]);

       }

       return 0;

}