【usaco2002.4】Power Hungry Cows

2014年2月5日1,3010

题目描述

农夫约翰的奶牛可以很快地计算整数的次方,但是需要你的帮助。因为他们将要计算很大的数的次方(还是数的很大次方……我英语,悲剧),他们只能使用两个工作变量来处存临时结果。

第一个动作变量被赋值为底数(用X表示);另一个赋值为1.牛们既能把两个变量相乘也能相除,并存储在任一工作变量中,但是所有结果都被存为整数(只能存为整数?我按这个做的AC)。

例如,他们想计算X^31,一种方法是这样的

这样x^31就被在六次计算中得出,给出需要计算的指数,找出计算它的最少步骤.

输入:

一行,整数P

 

输出:

一行,最少步骤

样例输入:

样例输出:

代码

内存限制30M。。。什么蛋疼

写了个bfs+hash超时了、、

看了下题解发现 if(ans||x>200||y>20000)return;//???这是为什么。。算了蒟蒻搞不懂就这么写上去了

应该这题用意是打表吧