题目描述 Description
从m开始，我们只需要6次运算就可以计算出m31：
m2=m×m，m4=m2×m2，m8=m4×m4，m16=m8×m8，m32=m16×m16，m31=m32÷m。
请你找出从m开始，计算mn的最少运算次数。在运算的每一步，都应该是m的正整数次方，换句话说，类似m-3是不允许出现的。
输入描述 Input Description
输入为一个正整数n
输出描述 Output Description
输出为一个整数，为从m开始，计算mn的最少运算次数。
样例输入 Sample Input
样例1
1
样例2
31
样例3
70
样例输出 Sample Output
样例1
0
样例2
6
样例3
8
数据范围及提示 Data Size & Hint
n（1<=n<=1000）
数据没有问题，已经出现过的n次方可以直接调用
/*迭代加深搜：论写好剪枝的重要性*/
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#define M 3010
using namespace std;
int vis[M],q[M],len,n,flag;
void dfs(int x,int t,int limit)
{
if(x*pow(,limit-t)<n)return;//加了一堆剪枝，都不如这一个好用
if(flag)return;
if(x==n){flag=;return;}
if(t==limit)return;
for(int i=;i<=len;i++)
{
if(x-q[i]>=n&&!vis[x-q[i]])
{
q[++len]=x-q[i];vis[x-q[i]]=;
dfs(x-q[i],t+,limit);
--len;vis[x-q[i]]=;
}
if(x+q[i]<*n&&!vis[x+q[i]])
{
q[++len]=x+q[i];vis[x+q[i]]=;
dfs(x+q[i],t+,limit);
--len;vis[x+q[i]]=;
}
}
}
int main()
{
scanf("%d",&n);
for(int i=;i<=;i++)
{
len=;memset(vis,,sizeof(vis));
vis[]=;q[++len]=;
dfs(,,i);
if(flag)
{
printf("%d",i);
return ;
}
}
return ;
}