6_8快速N次方

如果更快的求一个整数k的n次方。如果两个整数相乘并得到结果的时间复杂度为O(1),得到整数k的N次方的过程请实现时间复杂度为O(logN)的方法。

给定k和n,请返回k的n次方,为了防止溢出,请返回结果Mod 1000000007的值。

测试样例:
2,3
返回:8

class QuickPower {
public:
    int getPower(int k, int N) {
        // write code here 
        if(0==N) return 1;
        if(0==k) return 0;
        int mod = 1000000007;
        long res = 1;
        long tmp = k;
        while(N != 0){
            if((N & 1) == 1){
                res *= tmp;
            }
            N >>= 1;
            tmp = (tmp*tmp)%mod;
            res %= mod;
        }
        return (int)res;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 归去来兮。 1.1 说明 本篇为《挑战程序设计竞赛(第2版)》[http://www.ituring.com.cn...
    尤汐Yogy阅读 14,495评论 0 160
  • 如果更快的求一个整数k的n次方。如果两个整数相乘并得到结果的时间复杂度为O(1),得到整数k的N次方的过程请实现时...
    IT_Matters阅读 1,128评论 0 0
  • 今天参加了一场精英女性盛典,嘉宾们分享着自己的故事,坚持着自己的初心,每一位都是如钻石般闪亮,但来自日本的近藤麻理...
    王霞般若阅读 320评论 0 3
  • 前年本来打算记流水账来记录自己的生活,用来告诫自己警醒生活,可是后来发现我根本没办法长期坚持下来,上一篇文章发现还...
    yooshady阅读 390评论 1 1
  • 文/蒙山樵夫 学生时代读中国现代文学史,曾一度迷恋徐志摩的诗歌,对这位生气勃勃、才华四射、率真善良、执着于自由、美...
    蒙山樵夫下山来阅读 742评论 2 1