SFQRM 2015-03-29 09:16 采纳率: 0%
浏览 4934
已采纳

一道关于大数幂运算的题目,c语言实现

题目描述
幂运算是常见的数学运算之一,其原理是用同一个数相乘多次,但是有的时候当幂指数特别大的时候,这样的运算就太浪费时间。请大家学会在幂中加特技,让幂运算的效率提高到可以接受的程度。
输入:
第一个行一个整数T,表示有T组数据
每组数据,输入x,y 求x的y次幂 (2≤ x ,y≤10^9)
输出:
每组数据输出一个整数,表示幂运算对1000000007取模后的结果
样例输入:
2
2 4
2 100000000
样例输出:
16
494499948
我的代码总是超时,求好方法!!谢谢!!

  • 写回答

9条回答 默认 最新

  • threenewbee 2015-03-29 11:17
    关注

    不知道你怎么算的
    我们知道
    a^m可以视作a^p*a^q(p+q=m)
    而如果p=m,显然,我们只要算了a^p,就可以再平方下就是最后的结果了。
    因此最简单的做法就是,将指数转化成2的幂相加的结果,这相当于二进制计算,比如100000000
    就是101111101011110000100000000(2)
    那么就是256+8192+16384+32768+65536+262144+1048576+...
    然后我们分别计算N的这些次方的幂,别忘了,我们可以通过平方翻倍很快算出来。
    最后再把结果相乘。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(8条)

报告相同问题?

悬赏问题

  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常
  • ¥15 关于风控系统,如何去选择