1、广度优先搜索 状态(a,b)代表(x^a, x^b)，令a为二者中较大的数，从(a, b)可以转移到8个状态，即(2a, b)、(a+b,b)、(2b,b)、(a,2a)、(a,a+b)、(a,2b)、(a,a-b)、(a-b,a)，分别将这8种状态加入队列继续进行搜索，直到a或b等于P。 2、A搜索 设计估价函数f(i) = g(i) + h(i)，g(i)是当前步数。h(i)是当前状态到终点步数的预估值。 对于当前状态(a,b)，当a小于P式，a成倍地增长(a=2, 即x^a和自己不断地相乘)可以更快的到达P，然后再用减法进行微调， h(i) = log(P/a)；当a > P时，由于无法确定减法的次数，为了使h小于实际值，设h(i) = 0。用(a,b,g,h)表示状态，每次取g + h最小的状态进行扩展。

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

int n;

int dfs(int x, int y, int d, int m)
{
   if(x == 0 && y == 0) return 0;
   if(d > m) return 0;
   if(x == n || y == n) return 1;
   if(n % __gcd(x, y)) return 0;
   if((y << (m - d)) < n) return 0;

   int nx, ny;
   nx = x, ny = y << 1;
   if(dfs(nx, ny, d + 1, m)) return 1;

   nx = x << 1, ny = y;
   if(nx > ny) swap(nx, ny);
   if(dfs(nx, ny, d + 1, m)) return 1;

   nx = y, ny = y << 1;
   if(dfs(nx, ny, d + 1, m)) return 1;

   nx = x, ny = x << 1;
   if(dfs(nx, ny, d + 1, m)) return 1;

   nx = x, ny = x + y;
   if(dfs(nx, ny, d + 1, m)) return 1;

   nx = x + y, ny = y;
   if(nx > ny) swap(nx, ny);
   if(dfs(nx, ny, d + 1, m)) return 1;

   nx = x, ny = y - x;
   if(nx > ny) swap(nx, ny);
   if(dfs(nx, ny, d + 1, m)) return 1;

   nx = y, ny = y - x;
   if(nx > ny) swap(nx, ny);
   if(dfs(nx, ny, d + 1, m)) return 1;

   return 0;
}

int main()
{
   scanf("%d", &n);
   for(int k = 0; ;k++)
       if(dfs(0, 1, 0, k)) {
           printf("%d\n", k);
           break;
       }

   return 0;
}