组合数学 (一): 快速幂运算

谁践踏了优雅 2022-03-21 08:58 273阅读 0赞

### 快速幂 ###

*  快速幂运算
 *   *  C语言实现
 *  应用

# 快速幂运算 #

普通幂运算复杂度为 *O(N)*  
快速幂运算复杂度为 *O(lgN)*

举个例子:  
如果计算  7 13 7^\{13\} 713

*  普通幂运算:
    
        int result = 1;
          for (int i = 0; i < 13; i++) { 
          	result *= 7;
          }
    
    连乘13次, 简单明了
 *  快速幂运算:  
    十进制数 *13* 的二进制为 *1101* 即 1 + 4 + 8, 所以  7 13 = 7 1 + 4 + 8 = 7 ∗ 7 4 ∗ 7 8 7^\{13\} = 7^\{1 + 4 + 8\} = 7 \*7^4 \* 7^8 713=71\+4\+8=7∗74∗78  
    **只需3次乘法运算**, 每次运算时乘数取平方即可
    
        int result = 1;
        	遍历13的二进制位 { 
        		if (第 i 位 == 1) { 
        			result *= 7 ^ (2 ^ i);
        		}
        	}
    
    容易看出, **循环的次数是数字*b*的二进制中的最大的位数**, 即 *lgN* 次. 每次循环体内的运算为 *O(1)*, 因此总复杂度为 *O(lgN)* .  
    **但是由于整形数据一般是32 / 64位, 所以最大运算次数是32 / 64次, 因此也可以说复杂度是O(1)**

## C语言实现 ##

int pow(int a, int b) { 
    	int result = 1;
    	while (b) { 
    		if (b & 1) result *= a;
    		a *= a;
    		b >>= 1;
    	}
    	return result;
    }

# 应用 #

*  杨辉三角第 i 行作为十进制数是 11 的 i 次方 (i 从0开始), 因此计算第 n 行 (n < 1 e 8) 可以用快速幂运算
 *  (拓展) 矩阵快速幂, 在后续组合数学问题中会用到

发表评论取消回复

表情：

评论列表（有 0 条评论，273人围观）

还没有评论，来说两句吧...

相关阅读

相关矩阵快速幂：PIPI的数学题IV

矩阵快速幂：PIPI的数学题IV 文章目录矩阵快速幂：PIPI的数学题IV 问题：思路：代

Dear 丶/ 2023年10月06日 22:03/ 0 赞/ 3 阅读

相关幂运算

幂的概念：幂是乘方运算得结果，乘方运算涉及三个概念底数、指数和幂，如下图 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_s

谁借莪１个温暖的怀抱￠/ 2022年12月11日 02:22/ 0 赞/ 141 阅读

相关快速幂运算

include<iostream> using namespace std; typedef long long ll;

今天药忘吃喽~/ 2022年08月03日 14:52/ 0 赞/ 151 阅读

相关快速幂运算

/\ \ 基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题收藏关注给出3个正整数A B C，求A^B Mod C。例如，3 5

朴灿烈づ我的快乐病毒、/ 2022年07月26日 06:31/ 0 赞/ 209 阅读

相关 ACdream 1007 a + b (数学+快速幂)

题目链接： [ACdream 1007 ][ACdream 1007] 题目： ![这里写图片描述][SouthEast] ![这里写图片描述][SouthEas

左手的ㄟ右手/ 2022年06月13日 01:18/ 0 赞/ 172 阅读

相关矩阵运算，矩阵快速幂，模板

include<cstdio> include<algorithm> include<cstring> include<iostream>

以你之姓@/ 2022年06月11日 05:41/ 0 赞/ 222 阅读

相关 Applese 涂颜色（组合数学 + 快速幂 + 费马小定理 + 大数运算）

链接：[https://ac.nowcoder.com/acm/contest/330/E][https_ac.nowcoder.com_acm_contest_330_E]

客官°小女子只卖身不卖艺/ 2022年04月23日 08:30/ 0 赞/ 183 阅读

相关组合数学 (一): 快速幂运算

快速幂快速幂运算 C语言实现应用快速幂运算普通幂运算复杂度为 O(N) 快速幂运算复杂度为 O(lgN) 举个例子: 如

谁践踏了优雅/ 2022年03月21日 08:58/ 0 赞/ 274 阅读

相关幂运算

//1.基本实现方法递归时间复杂度O(n) double pow(int x,int n){ if(n<0)

短命女/ 2021年09月26日 13:06/ 0 赞/ 295 阅读

相关 bzoj1008越狱(组合数学+快速幂)

Problem 1008. – \[HNOI2008\]越狱 1008: \[HNOI2008\]越狱 Time Limit: 1 Sec Memory Limit

我不是女神ヾ/ 2021年09月15日 13:34/ 0 赞/ 320 阅读