【C++】整数幂运算模板（分治+递归）

本文主要是介绍【C++】整数幂运算模板（分治+递归），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

例如2^101，如果采用循环或者普通递归计算的话，会计算101次。

2^101=2*4^50=2*16^25=2*16*256^12……，最终可以优化为极短的计算次数。

代码如下：

#include <iostream>
using namespace std;
long long res(long long base,long long top){if(top==0) return 1;//0次幂 if(top==1) return base;//1次幂 if(top%2) return base*res(base*base,top/2);//奇数次幂 else return res(base*base,top/2);//偶数次幂 
}
int main(){long long base,top;//底数和指数 cin>>base>>top;cout<<res(base,top);
}

 

这篇关于【C++】整数幂运算模板（分治+递归）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---