{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003e从 \u003ci\u003ex\u003c/i\u003e 开始,反复乘以 \u003ci\u003ex\u003c/i\u003e,我们可以用三十次乘法计算出 \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e:\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e3\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e3\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e, …, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e30\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e.\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003e平方操作可以显著缩短乘法序列。以下是用八次乘法计算 \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e 的方法:\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e3\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e6\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e3\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e3\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e7\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e6\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e14\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e7\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e7\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e15\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e14\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e30\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e15\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e15\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e30\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e.\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003e这并不是计算 \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e 最短的乘法序列。有很多方法只需七次乘法。以下是其中一种:\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e × \u003ci\u003ex, x\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e8\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e8\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e10\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e8\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e20\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e10\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e10\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e30\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e20\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e10\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e30\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e.\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003e如果除法也可用,我们可以找到更短的操作序列。有可能用六次操作(五次乘法和一次除法)计算 \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e:\u003c/p\u003e\u003cblockquote\u003e\u003cp\u003e\u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e × \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e2\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e8\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e4\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e16\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e8\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e8\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e32\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e16\u003c/sup\u003e × \u003ci\u003ex\u003c/i\u003e\u003csup\u003e16\u003c/sup\u003e, \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e \u003d \u003ci\u003ex\u003c/i\u003e\u003csup\u003e32\u003c/sup\u003e ÷ \u003ci\u003ex\u003c/i\u003e.\u003c/p\u003e\u003c/blockquote\u003e\u003cp\u003e如果除法和乘法一样快的话,这是计算 \u003ci\u003ex\u003c/i\u003e\u003csup\u003e31\u003c/sup\u003e 最有效的方法之一。\u003c/p\u003e\u003cp\u003e你的任务是编写一个程序,找出用乘法和除法计算给定正整数 \u003ci\u003en\u003c/i\u003e 的 \u003ci\u003ex\u003csup\u003en\u003c/sup\u003e\u003c/i\u003e 所需的最少操作次数。序列中出现的乘积和商应该是 \u003ci\u003ex\u003c/i\u003e 的正整数次幂。换句话说,例如 \u003ci\u003ex\u003c/i\u003e\u003csup\u003e−3\u003c/sup\u003e 绝不应出现。\u003c/p\u003e\u003c/span\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e输入是一个或多个行的序列,每行包含一个整数 \u003ci\u003en\u003c/i\u003e。 \u003ci\u003en\u003c/i\u003e 为正整数,且小于或等于 1000。输入以 0 表示结束。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e你的程序应该打印计算 \u003ci\u003ex\u003csup\u003en\u003c/sup\u003e\u003c/i\u003e 所需的最少总乘法和除法次数。这些数字应该分别写在单独的一行上,不应包含任何多余字符,如前导或尾随空格。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n31\r\n70\r\n91\r\n473\r\n512\r\n811\r\n953\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n6\r\n8\r\n9\r\n11\r\n9\r\n13\r\n12\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}