H胖胖的健身计划

2020年1月17日 1047点热度 0人点赞 0条评论

H胖胖的健身计划

时间: 1ms        内存:128M

描述:

L老师布置了一道思考题,一个人一次可以上一个台阶,也可以上两个台阶,问上到n级台阶有多少种走法?H胖胖非常聪明,拿出胖胖的小手掐指算起来。登上第一级台阶有一种登法;登上两级台阶,有两种登法;登上三级台阶,有三种登法;登上四级台阶,有五种方法……所以,1,2,3,5,8,13,……。 

H胖胖为了保持身体苗条,给自己制定了一个锻炼计划,决定用刚才计算的数列确定每天自己锻炼的步数,就是说第1天走1步,第2天走2步,第3天走5步,第4天走8步,第5天走13步,……。 

H胖胖的同学LYQ正好在学习矩阵相乘,帮他想到了一个快递计算的方法如下公式所示。 


H胖胖拿出手机查阅了快速幂的百度百科,看到如下信息: 

快速幂 

顾名思义,快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N), 与朴素的O(N)相比效率有了极大的提高。 

原理 

以下以求a的b次方来介绍: 

把b转换成二进制数。 

该二进制数第i位的权为    

例如 

 

11的二进制是1011 

11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1 

因此,我们将a¹¹转化为算 

   

但是H胖胖的手机太不给力,后面的代码实在看不清了,请正在做题的你帮帮他吧。 

输入:

一个整数n(0<n<10^12)

输出:

H胖胖走的步数%100007的结果

示例输入:

6

示例输出:

13

提示:

参考答案:

解锁文章

没有看到答案?微信扫描二维码可免费解锁文章

微信扫描二维码解锁

使用微信扫描二维码打开广告页面后可以立即关闭,再刷新此页面即可正常浏览此文章

所跳转广告均由第三方提供,并不代表本站观点!

已经扫描此二维码?点此立即跳转

code

这个人很懒,什么都没留下

文章评论