TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3464
  • 题目
  • P3464快速乘积
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    给你一个正整数n(1<=n<=1000),问最少需要几次乘法和除法计算就能从x得到xn?
    例如得到x31需要六次计算:
    1.x2=x*x
    2.x4=x2*x2
    3.x8=x4*x4
    4.x16=x8*x8
    5.x32=x16*x16
    6.x31=x32/x


    当然,也可以是x^2 = x × x, x^3 = x^2 × x, x^4 = x^2 × x^2, x^7 = x^4 × x^3, x^11 = x^4 × x^7, x^22 = x^11 × x^11, x^33 = x^11 × x^22, x^31 = x^33 / x^2. 但这种计算的次数不是最少的。

    注意:计算过程中指数不能是负数

    输入格式

    输入一个正整数n

    输出格式

    输出一个整数,表示最少需要计算的次数

    样例输入

    样例1:
    31
    样例2:
    70

    样例输出

    样例1:
    6
    样例2:
    8