帝国cms 网站地图 自定义,厦门网站开发费用,织梦做分类信息网站,ui设计在线培训机构快速幂的作用#xff1a;解决 求 a ^ n 的问题 (n可以大于1e18)#xff0c; 如果用for循环的话#xff0c;毫无疑问直接炸掉 …… 所以也就用了算法复杂度在 o(log n)的快速幂算法来解决此类问题。快速幂递归法(基于二分思想)#xff1a;那么既然要用到二分法那么怎么二分解决 求 a ^ n 的问题 (n可以大于1e18) 如果用for循环的话毫无疑问直接炸掉 …… 所以也就用了算法复杂度在 o(log n)的快速幂算法来解决此类问题。快速幂递归法(基于二分思想)那么既然要用到二分法那么怎么二分 既然要递归那么如何递归第一个问题如何二分 就以2 ^ 10 为例 我们可以以指数入手进行二分 10 是一个偶数 那么 二分一下就是 2^5 * 2^5 之后 2^5 中 5为奇数 那么就让 2^5 2 * 2^4 那么就有了2^4 那么对于 2^4 就又有了偶数的2 ^ 4进行二分。初始二分变化2^102^5 * 2^52^52 * 2^42^42^2 * 2^22^22^1 * 2^12^12 * 2^0由可以看出 要对指数的偶数和奇数进行区分从而进行拆分这样可以大大的增大程序的效率就把 o(n)的算法化成了o(log n)。第二个问题如何进行递归 其实很明了可以看出如果想要递归一定也是以指数为参数进行因为指数是变化而且牵扯到二分递归的出口就是指数为零结束我们可以把奇数和偶数进行 if 判断如果指数为偶数那么就返回 fib(a , b/2 , m) (其中a为底数b为指数m为模)。递归法代码以及解析如下#includeusing namespace std;typedef long long ll;ll binarypow(ll a,ll b,ll m) {if(b0) return 1;//如果b为0那么a^01//b为奇数转换为b-1if(b%21) return a*binarypow(a,b-1,m)%m;//可以把if(b%21)该为if(b1)这样会更快一点。else {//b为偶数转换为b/2ll mulbinarypow(a,b/2,m);return mul*mul%m;}}int main() {ll a,b,m;cinabm;ll resultbinarypow(a,b,m);coutreturn 0;}快速幂迭代法迭代法要用到一些二进制以及位计算的思想就如2^13 我们依然以指数入手我们可以把13化为二进制 就是 1 1 0 1 我们发现 1 出现在了 3 号位 2 号位 以及 0 号位 。那么 13 2^3 2^2 2^1 8 4 1 那么划开不就是2 ^ 13 2 ^ 8 * 2 ^ 4 2 ^ 1如果把一个指数这样进行拆分那么不就可以对那么问题 1 如何拆分问题如何拆分 我们可以用 if (b 1) 判断指数的末尾是否为 1 (其中b 为指数 末尾为1 说明是奇数末尾为0说明为偶数)如果为 1 那么就让一个变量乘以当前的 例如 变量 int ans 1 让ans * a(a为底数)然后每一次都要a^2 (移到下一位)。然后通过b1把指数移到下一位判断下一位的末尾数是1 还是 0 然后就这样进行一步一步的拆分。文字看不懂的话再加一个表来辅助理解。bb 1ansa空空1a110111*aa^21100aa^4111a * a^4a^811a^5 * a^8空迭代法代码以及解析如下#includeusing namespace std;typedef long long ll;ll binarypow(ll a,ll b,ll m){ll ans1;while(b0){if(b1){//如果b的二进制末尾为1 就相当于被选中了。//就如2^13 2^(131101) 2^(1101) 3 2 0 号为 1 那么被选中 2^13 2^8 * 2^4 * 2^1ansans*a%m;//令ans累积上a}aa*a%m;//令a平方b1;//将b的二进制右移一位即}return ans;}int main(){ll a,b,m;cinabm;ll resultbinarypow(a,b,m);coutreturn 0;}
