快速幂pascal模板
以洛谷P1226为例：
P1226 取余运算||快速幂
题目描述
输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。
输入格式：三个整数b,p,k.
输出格式：输出“b^p mod k=s”s为运算结果
输入样例#1：
2 10 9
输出样例#1：
2^10 mod 9=7
代码：
program rrr(input,output);
var
b,p,k:longint;
function pow(a,b,p:longint):longint;
var
i,j,ans:longint;
begin
i:=b;j:=a;ans:=1;
while i>0 do
begin
if i mod 2=1 then ans:=ans*j mod p;
j:=j*j mod p;
i:=i div 2;
end;
exit(ans);
end;
begin
assign(input,'r.in');assign(output,'r.out');reset(input);rewrite(output);
readln(b,p,k);
write(b,'^',p,' mod ',k,'=',pow(b,p,k));
close(input);close(output);
end.
幂的运算方法总结 姓名：__________ 指导：__________ 日期：__________
作为整式乘除的前奏，幂的运算看似非常简单，实际运用起来却灵活多变。不过，只要熟悉运算的一些基本方法原则，问题就迎刃而解了。而且通过这些方法原则的学习，不但能使我们熟悉幂的运算，还可得到全面的思维训练，现在对此做一探索。
幂的运算的基本知识就四条性质，写作四个公式： ①am×an=am+n ②(am)n=amn ③(ab)m=ambm ④am÷an=am-n 只要理解掌握公式的形状特点，熟悉其基本要义，直接应用一般都容易，即使运用公式求其中的未知指数难度也不大。 问题1 已知a7am=a3a10，求m的值。 思路探索：用公式1计算等号左右两边，得到等底数的同幂形式，按指数也相等的规则即可得m的值。 方法思考：只要是符合公式形式的都可套用公式化简试一试。 方法原则：可用公式套一套。 但是，渗入幂的代换时，就有点难度了。 问题2 已知xn=2,yn=3,求(x2y)3n的值。 思路探索： (x2y)3n中没有xn和yn，但运用公式3就可将(x2y)3n化成含有xn和yn的运算。 因此可简解为，(x2y)3n=x6ny3n=(xn)6(yn)3=26×33=1728 方法思考：已知幂和要求的代数式不一致，设法将代数式变形，变成已知幂的运算的形式即可代入求值。 方法原则：整体不同靠一靠。 然而，遇到求公式右边形式的代数式该怎么办呢？
问题3 已知a3=2,am=3,an=5，求am+2n+6的值。 思路探索：试逆用公式，变形出与已知同形的幂即可代入了。 简解：am+2n+6=ama2na6=am(an)2(a3)2=3×25×4=300 方法思考：遇到公式右边的代数式时，通常倒过来逆用公式，把代数式展开，然后代入。 方法原则：逆用公式倒一倒。 当底数是常数时，会有更多的变化，如何思考呢？ 问题4 已知22x+3－22x+1=48，求x的值。 思路探索：方程中未知数出现在两项的指数上，所以必须统一成一项，即用公式把它们变成同类项进行合并。由此，可考虑逆用公式1，把其中常数的整数指数幂，化作常数作为该项的系数。 简解： 22x+3－22x+1 =22x×23－22x×21 =8×22x－2×22x =6×22x=48 ∴22x=8 ∴2x=3∴x=1.5 方法思考:冪的底数是常数且指数中有常数也有未知数时，通常把常数的整数指数冪化成常数作为其它冪的系数，然后进行其它运算。 问题5
数论 素数问题、同余问题、中国剩余定理、Nim积、高斯消元法求线性方 程组解、Pell方程、polya计数、矩阵二分快速幂、伪素数、基本数 值计算方法（定积分求解，多项式求根，周期性方程） 1、与整数除法运算相关的算法 整除问题： 欧几里得算法及利用其求最小公倍数： 拓展欧几里得算法及利用其解线性同余方程： a^b%c几种计算方法 中国剩余定理 #include
快速幂取模算法 在网站上一直没有找到有关于快速幂算法的一个详细的描述和解释，这里，我给出快速幂算法的完整解释，用的是C 语言，不同语言的读者只好换个位啦，毕竟读C 的人较多~ 所谓的快速幂，实际上是快速幂取模的缩写，简单的说，就是快速的求一个幂式的模(余)。在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法，产生了快速幂取模算法。我们先从简单的例子入手：求c a b mod = 几。 算法1.首先直接地来设计这个算法： int ans = 1; for (int i = 1;i<=b;i++) { ans = ans * a; } ans = ans % c; 这个算法的时间复杂度体现在for 循环中，为O （b ）.这个算法存在着明显的问题，如果a 和b 过大，很容易就会溢出。 那么，我们先来看看第一个改进方案：在讲这个方案之前，要先有这样一个公式： c c a c a b b mod )mod (mod =.这个公式大家在离散数学或者数论当中应该学过，不过这里为了方便大家的阅读，还是给出证明： 引理1： c c b c a c de c de c dk te tkc c e kc d tc c ab e kc b e c b d tc a d c a c c b c a c ab mo d )]mod ()mod [(mod mod ))((mod ))((mod mod mod mod )]mod ()mod [(mod )(:2?==+++=++=+=?=+=?=?=证明： 公式 上面公式为下面公式的引理，即积的取余等于取余的积的取余。 c a c c a c c c a c c a c c a c a b b b b b b mo d mod ])mod [() (mod ])mod )mod [((mod ])mod [(mod )mod (mod ===由上面公式的迭代证明：公式： 证明了以上的公式以后，我们可以先让a 关于c 取余，这样可以大大减少a 的大小， 于是不用思考的进行了改进： 算法2： int ans = 1; a = a % c; //加上这一句 for (int i = 1;i<=b;i++) {
幂模运算快速算法——滑动窗口算法 设e 的二进制表达式为：∑-== 10)2(k i i i e e ，其中}1,0{∈i e 。那么，n X e mod 的幂模运算二进制算法如下： 输入：X ，e ，n 输出：n X C e mod = Step 1: 1=C Step 2: for 1-=k i downto 0 Step 2.1: n C C C mod )*(= Step 2.2: if 1=i e then n X C C mod )*(= Step 3: return C 由二进制法的计算过程可知：当指数e 的二进制位为0时，会减少乘模的次数。二进制法的直接推广是m 进制法，其基本思想是把指数分成r bits(即m 2log bits)的数据块，每次取指数e 的r bits 进行运算，从而使整个幂模运算的效率提高。假定e 的每个比特是0或1的概率相同，则m 进制法一个数据块是全0的可能性为r -2，当r 增加时，数据块为全0的可能性会减少，因此在Step 2.2需做乘模的可能性增加；而当r 减小时，算法总的乘模次数也会增加。滑动窗口技术提供了一种折衷，允许零数据块和非零数据块是变长的，目的是增加全0数据块的数量，从而使总的乘模次数减少。 具体方法是：把k bits 指数分解成z 个零窗口或非零窗口i F ，i F 长度为)(i F L 。规定最大窗口长度为d ，即))(max(i F L d =，显然总窗口数z 可能不等于d k 。d 的取值与模数的位长有关。 对单一窗口的幂模运算进行预处理，即预计算n X w mod ，其中 12,,7,5,3-=d w ，因为指数分解的原则使非零窗口的最低有效位必定为1，故w 为为奇数，从而使预处理次数减少了一半。 滑动窗口算法处理幂模运算的过程如下： 输入：X ，e ，n 输出：n X C e mod = Step 1: 预计算。 Step 2: 将k bits 的指数e 分解成长度为)(i F L 的零窗口或非零窗口i F ，1,,2,1,0-=z i 。 Step 3: 1=C Step 4: for 1-=z i downto 0 Step 4.1: n C C i F L mod )(2= Step 4.2: if 0≠i F then n X C C i F mod )*(= Step 5: return C 窗口的划分采用了从左至右扫描的变长滑动窗口技术，因为计算是从高位至低位进行的。如果采用从
矩阵运算是属于线性代数里的一个重要内容，上学期学完后只觉得矩阵能解线性方程，不过高中的时候听说过矩阵能优化常系数递推以及将坐标上的点作线性变换，于是找了些资料研究了一下，并把许多经典题以及HDU shǎ崽大牛总结的矩阵乘法的题目[1]、[2]和开设的矩阵乘法DIY Contest给做完了，感觉收获颇丰。 一个矩阵就是一个二维数组，为了方便声明多个矩阵，我们一般会将矩阵封装一个类或定义一个矩阵的结构体，我采用的是后者： 最特殊的矩阵应该就是单位矩阵E了，它的对角线的元素为1，非对角线元素为0。 若A为n×p矩阵，B为p×m矩阵，则它们的乘积AB(有时记做A·B)将是一个n×m矩阵。其乘积矩阵AB的第i行第j列的元素为： 一般矩阵乘法采用朴素的O(n^3)的算法： 矩阵加法就是简单地将对应的位置的两个矩阵的元素相加：
在ACM的题目中，我们一般考虑的是n阶方阵之间的乘法以及n阶方阵与n维向量（把向量看成n×1的矩阵）的乘法。矩阵乘法最重要的性质就是满足结合律，同时它另一个很重要的性质就是不满足交换率，这保证了矩阵的幂运算满足快速幂取模（A^k % MOD）算法：假设k = 27，则k的二进制表示为11011，所以 按二进制展开，乘以相应的权值 ，可以看出：k的二进制的每一位矩阵A都要平方，在k二进制为1的位：末矩阵×平方后的A，在k二进制为0的位则末矩阵×E（单位矩阵），即不变。代码如下： 重载按位与(乘方)和加法时注意，加法的优先级高于按位与 *->+->^ 许多题目还要求S = A + A2 + A3+ … + A k.。其实再作一次二分即可：只需计算log(n)个A 的幂即可。 ()()3 4 3 2 5 1A 6 2 3 1 = + + + + +将二分 + ? + A A A e A+ A A A A A 若A中=m表示从i到j有m条有向边，则k A中=n表示从i经过k条有向边到达j，这样的走法有n种
快速幂求余算法 （OJ T1128） 求a^b%c（这就是著名的RSA公钥的加密方法） 当a,b很大时，直接求解这个问题不太可能，你能想到哪些优化呢？ 算法1：直观上，也许最容易想到的是利用 a*b%c=((a%c)*b)%c，这样每一步都进行这种处理，这就解决了a^b可能太大存不下的问题，但这个算法的时间复杂度依然是O(n)，根本没有得到优化。当b很大时运行时间会很长 算法2：另一种算法利用了分治的思想，可以达到O(logn)。 可以把b按二进制展开为 b=p(n)*2^n+p(n-1)*2^(n-1)+...+p(1)*2+p(0)其中p(i) (0<=i<=n)为0或1 这样a^b=a^(p(n)*2^n+p(n-1)*2^(n-1)+...+p(1)*2+p(0)) =a^(p(n)*2^n)*a^(p(n-1)*2^(n-1)*...*a^(p(1)*2)*a^p(0) 对于p(i)=0的情况,a^p(i)*2^(i-1)=a^0=1,不用处理，我们要考虑的仅仅是p(i)=1的情况， a^(2^i)=(a^(p(i)*2(i-1)))^2 (当p(i)=1时， a^(2^i)=(a^(2(i-1)))^2) 利用这一点，我们可以递推地算出所有的a^(2^i)
当然由算法1的结论a*b%c=((a%c)*b)%c，我们加上取模运算 a^(2^i)%c=((a^(2(i-1))%c)*a^(2(i-1)))%c 于是再把所有满足p(i)=1的a^(2^i)%c按照算法1乘起来再%c就是结果 示例: 3^6%7=3^(2^2)*3^(2^1)%7 =((3^(2^1))^2%7)*(3^1*3^1%7) =(((3^1*3^1%7)%7)^2%7*2%7)%7 =(4*2)%7 =8%7 =1 当然算法可以进一步改进，比如二进制的每一位不必存起来，可以边求边用 经改进后代码如下：（输入a,k,m,求a^k%m) long f(long a,long k,long m) { long b=1; while(k>=1) { if(k%2==1) b=a*b%m;
幂的运算方法总结 幂的运算的基本知识就四条性质，写作四个公式： ①a m×a n=a m+n ②(a m)n=a mn ③(ab)m=a m b m ④a m÷a n=a m-n 只要理解掌握公式的形状特点，熟悉其基本要义，直接应用一般都容易，即使运用公式求其中的未知指数难度也不大。 问题1、已知a7a m=a3a10，求m的值。 思路探索：用公式1计算等号左右两边，得到等底数的同幂形式，按指数也相等的规则即可得m的值。 方法思考：只要是符合公式形式的都可套用公式化简试一试。 方法原则：可用公式套一套。 但是，渗入幂的代换时，就有点难度了。 问题2、已知x n=2,y n=3,求(x2y)3n的值。 思路探索：(x2y)3n中没有x n和y n，但运用公式3就可将(x2y)3n化成含有x n 和y n的运算。 因此可简解为，(x2y)3n =x6n y3n=(x n)6(y n)3=26×33=1728 方法思考：已知幂和要求的代数式不一致，设法将代数式变形，变成已知幂的运算的形式即可代入求值。 方法原则：整体不同靠一靠。 然而，遇到求公式右边形式的代数式该怎么办呢？ 问题3、已知a3=2,a m=3,a n=5，求a m+2n+6的值。 思路探索：试逆用公式，变形出与已知同形的幂即可代入了。 简解：a m+2n+6=a m a2n a6=a m(a n)2(a3)2=3×25×4=300
方法思考：遇到公式右边的代数式时，通常倒过来逆用公式，把代数式展开，然后代入。 方法原则：逆用公式倒一倒。 当底数是常数时，会有更多的变化，如何思考呢？ 问题4、已知22x+3－22x+1=48，求x的值。 思路探索：方程中未知数出现在两项的指数上，所以必须统一成一项，即用公式把它们变成同类项进行合并。由此，可考虑逆用公式1，把其中常数的整数指数幂，化作常数作为该项的系数。 简解：22x+3－22x+1=22x×23－22x×21=8×22x－2×22x =6×22x=48 ∴22x=8 ∴2x=3 ∴x=1.5 方法思考:冪的底数是常数且指数中有常数也有未知数时，通常把常数的整数指数冪化成常数作为其它冪的系数，然后进行其它运算。 问题5、已知64m+1÷2n÷33m=81,求正整数m、n的值。 思路探索：幂的底数不一致使运算没法进行，怎样把它们变一致呢？把常数底数都变成质数底数就统一了。 简解：64m+1÷2n÷33m =24m+1×34m+1÷2n÷33m=24m+1-n×3m+1=81=34 ∵m、n是正整数∴m+1=4,4m+1－n=0 ∴m=3,n=13 方法思考：冪的底数是常数时，通常把它们分解质因数，然后按公式3展开，即可化成同底数冪了。 问题6、已知2a=3,2b=6,2c=12，求a、b、c的关系。 思路探索：求a、b、c的关系，关键看2a、2b、2c的关系，即3、6、12的关系。6是3的2倍，12是6的2倍，所以2c=2×2b=4×2a,由此可求。 简解：由题意知2c=2×2b=4×2a ∴2c=2b+1=2a+2 ∴c=b+1=a+2
第一题
正确答案：52488（我居然上来第一题就错了居然写了13440→_→） //cout<<8*9*9*9*9; →_→ 第二题结果填空5… 星系炸弹 在X星系的广袤空间中漂浮着许多X星人造“炸弹”，用来作为宇宙中的路标。 每个炸弹都可以设定多少天之后爆炸。 比如：阿尔法炸弹2015年1月1日放置，定时为15天，则它在2015年1月16日爆炸。有一个贝塔炸弹，2014年11月9日放置，定时为1天，请你计算它爆炸的准确日期。 请填写该日期，格式为yyyy-mm-dd即4位年份2位月份2位日期。比如：2015-02-19 请严格按照格式书写。不能出现其它文字或符号。 - 题解：不用废话，直接手算顶多3分钟，注意2016是闰年 正确答案：2017-08-05 第三题结果填空9… 三羊献瑞 观察下面的加法算式： 祥瑞生辉 + 三羊献瑞 - 三羊生瑞气 (如果有对齐问题，可以参看【图1.jpg】) 其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。 请你填写“三羊献瑞”所代表的4位数字（答案唯一），不要填写任何多余内容。 - 题解：水题，给“祥瑞生辉三羊献气”编号01234567，直接回溯穷举即可 1 #include
第三题 正确答案：1085 第四题代码填空11… 格子中输出 StringInGrid函数会在一个指定大小的格子中打印指定的字符串。要求字符串在水平、垂直两个方向上都居中。 如果字符串太长，就截断。 如果不能恰好居中，可以稍稍偏左或者偏上一点。 下面的程序实现这个逻辑，请填写划线部分缺少的代码。
2. 大数幂模与乘模运算?Montgomery 幂模算法 在实现了vlong 类型后，大数的存储和四则运算的功能都完成了。考虑到RSA 算法需要进行幂模运算，需要准备实现这些运算的方法。所以写一个vlong 的友元，完成幂模运算功能。幂模运算是RSA 算法中比重最大的计算，最直接地决定了RSA 算法的性能，针对快速幂模运算这一课题，西方现代数学家提出了很多的解决方案。经查阅相关数学著作，发现通常都是依据乘模的性质 n n b n a n b a mod ))mod ()mod ((mod )(?=?，先将幂模运算化简为乘模运算。 通常的分解习惯是指数不断的对半分，如果指数是奇数，就先减去一变成偶数，然后再对半分，例如求D=n C E mod ，E=15，可分解为如下6个乘模运算。 n C n C C C m od m od 21=?= n C n C C C m od m od 312=?= n C n C C C mod mod 6223=?= n C n C C C mod mod 734=?= n C n C C C mod mod 14445=?= n C n C C C mod mod 1556=?= 归纳分析以上方法，对于任意指数E ，可采用如图2-4的算法流程计算 。
图2-4 幂模运算分解为乘模运算的一种流程 按照上述流程，列举两个简单的幂模运算实例来形象的说明这种方法。 ①求17 mod 215的值 开始 D = 1 P = 2 mod 17 = 2 E = 15
E奇数 D = DP mod n = 2 P = PP mod n = 4 E = (E-1)/2 =7 E奇数 D = DP mod n = 8 P = PP mod n = 16 E = (E-1)/2 =3 E奇数 D = DP mod n = 9 P = PP mod n = 1 E = (E-1)/2 =1 E奇数 D = DP mod n = 9 P = PP mod n = 1 E = (E-1)/2 =0 最终D = 9 即为所求。 ②求13 mod 28的值 开始 D = 1 P = 2 mod 17 = 2 E = 8 E偶数 D = 1 P = PP mod n = 4 E = E/2 =4 E偶数 D = 1 P = PP mod n = 3 E = E/2 =2 E偶数 D = 1 P = PP mod n = 9 E = E/2 =1 E奇数 D = DP mod n = 9 P = 不需要计算 E = (E-1)/2 =0 最终D = 9 即为所求。 观察上述算法，发现E根据奇偶除以二或减一除以二实际就是二进制的移位操作，所以要知道需要如何乘模变量，并不需要反复对 E 进行除以二或减一除以二的操作，只需要验证E 的二进制各位是0 还是1 就可以了。同样是计算 ，下面给出从右到左扫描二进制位进行的幂模算法描述，设中间变D E mod C n 量D,P,E的二进制各位下标从左到右为u,u-1,u-2, 0 Powmod(C,E,n) { D=1; P=C mod n; for i=0 to u do { if(Ei=1)D=D*P(mod n); P=P*P(mod n); }
学习必备 精品知识点 幂的四则运算（知识总结） 一、同底数幂的乘法 运算法则：同底数幂相乘,底数不变，指数相加。用式子表示为： n m n m a a a +=?(m 、n 是正整数) 二、同底数幂的除法 运算法则:同底数幂相除,底数不变，指数相减。用式子表示为：n m n m a a a -=÷。(0≠a 且m 、n 是正整数，m>n 。) 三、幂的乘方 运算法则：幂的乘方，底数不变，指数相乘. 用式子表示为： ()n m mn a a =（m 、n 都是正整数） 注：把幂的 乘方转化为同底数幂的乘法 练习： 1、计算： ①()()()()2 4 5 2 2 32222x x x x -?-? ②()()() 3 2 212m n m a a a a -?-? 补充： 同底数幂的乘法与幂的乘方性质比较： 幂的运算 指数运算种类 同底数幂乘法 乘法 加法 幂的乘方 乘方 乘法 四、积的乘方 运算法则：两底数积的乘方等于各自的乘方之积。用式子表示为： () n n n b a b a ?=?(n 是正整数) 扩展 p n m p n m a a a a -+=÷? () np mp p n m b a b a = (m 、n 、p 是正整数) 提高训练 1.填空 (1) (1/10)5 ×(1/10)3 = (2) (-2 x 2 y 3) 2 = (3) (-2 x 2 ) 3 = (4) 0.5 -2 = (5) (－10)2 ×(－10)0 ×10-2 = 2.选择题 (1) 下列说法错误的是. A. (a －1)0 = 1 a ≠1 B. (－a )n = － a n n 是奇数 C. n 是偶数 , (－ a n ) 3 = a 3n D. 若a ≠0 ,p 为正整数, 则a p =1/a -p (2) [(-x ) 3 ] 2 ·[(-x ) 2 ] 3 的结果是( ) A. x -10 B. - x -10 C. x -12 D. - x -12 (3) a m = 3 , a n = 2, 则a m-n 的值是( ) A. 1.5 B. 6 C. 9 D. 8 3.计算题 (1) (-1/2 ) 2 ÷(-2) 3 ÷(-2) –2 ÷(∏-2005) 0 = = (2) (-2 a ) 3 ÷a -2 =
武汉大学 MATLAB及其应用课程 课程论文 学生姓名： 学号： 电话： 班级： 指导教师： 2016年4月4日
目录 一、实验题目 (3) 二、实验目的 (3) 三、实验设备和条件 (3) 四、实验原理 (3) 五、实验内容与过程 (6) 六、程序代码截图 (8) 七、实验结果 (10) 八、实验收获与总结 (12)
一、实验题目 利用矩阵快速幂算法与符号运算求解大型斐波那契数。 二、实验目的 <1>实现在较短的时间内完成大规模运算。 <2>充分利用MATLAB方便的矩阵运算以及超高精度的符号运算的特色，进行对大规模数值的求解运算。 三、实验设备和条件 <1>设备：MATLAB R2015a软件 <2>条件： ①MATLAB拥有着极其方便的矩阵运算，每一个数组都可以表示为相应维度的矩阵，可以通过两个数组的直接相乘来获得“矩阵1×矩阵2”运算的结果矩阵。 ②MATLAB拥有着精度超高的符号运算，而且使用起来非常方便。 四、实验原理 根据题目，“利用矩阵快速幂算法与符号运算求解大型斐波那契数”，需要将该实验的题目拆成“矩阵快速幂算法”、“大型”和“斐波那契数”几个关键点进行原理的阐述。 为了方便描述，稍排了个序进行原理讲解： <1>“斐波那契数” 斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci ）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。 而斐波那契数，就是指在已经定义了递推初始值的前提下，持续递推斐波那契数列所得的其中一个数。 <2>“大型” 对于诸如C，C++，JAVA等语言，进行高精度数字的求解总是非常具有挑战性的，即使只是进行大规模整数运算，C++也需要铺写大量的代码定义大数类和重载操作符。如果再加入矩阵运算，使用起来极其不方便。甚至在大数类定义不够严谨的情况下，轻则造成运行效率极低，数组空间溢出等问题，重则造成数据溢出还找半天找不到bug的“惨案”。 而MATLAB的符号类精度之高非常恐怖，且操作异常方便，可以像处理普通整型一样地
幂的运算 一、知识网络归纳 二、学习重难点 学习本章需关注的几个问题： ●在运用n m n m a a a +=?（m 、n 为正整数），n m n m a a a -=÷（0≠a ，m 、n 为正整数且m ＞n ），mn n m a a =)(（m 、n 为正整数），n n n b a ab =)(（n 为正整数），)0(10≠=a a ，n n a a 1 = -（0≠a ，n 为正整数）时，要特别注意各式子成立的条件。 ◆上述各式子中的底数字母不仅仅表示一个数、一个字母，它还可以表示一个单项式，甚至还可以表示一个多项式。换句话说，将底数看作是一个“整体”即可。 ◆注意上述各式的逆向应用。如计算20052004425.0?，可先逆用同底数幂的乘法法则将20054写成442004?，再逆用积的乘方法则计算 11)425.0(425.02004200420042004==?=?，由此不难得到结果为1。 ◆通过对式子的变形，进一步领会转化的数学思想方法。如同底数幂的乘法
就是将乘法运算转化为指数的加法运算，同底数幂的除法就是将除法运算转化为指数的减法运算，幂的乘方就是将乘方运算转化为指数的乘法运算等。 ◆在经历上述各个式子的推导过程中，进一步领悟“通过观察、猜想、验证与发现法则、规律”这一重要的数学研究的方法，学习并体会从特殊到一般的归纳推理的数学思想方法。 一、同底数幂的乘法 1、同底数幂的乘法 同底数幂相乘，底数不变，指数相加. 公式表示为：()m n m n a a a m n +?=、为正整数 2、同底数幂的乘法可推广到三个或三个以上的同底数幂相乘，即 () m n p m m p a a a a m n p ++??=、、为正整数 注意点： （1） 同底数幂的乘法中，首先要找出相同的底数，运算时，底数不变，直接把指数相加，所得的和作为积的指数. （2） 在进行同底数幂的乘法运算时，如果底数不同，先设法将其转化为相同的底数，再按法则进行计算. 例题： 例1：计算列下列各题 （1） 34a a ?； （2） 23b b b ?? ； （3） ()()()2 4 c c c -?-?- 简单练习： 一、选择题 1. 下列计算正确的是( ) A.ａ2+ａ3=ａ5 B.ａ2·ａ3=ａ5 C.3m +2m =5m D.ａ2+ａ2=2ａ4 2. 下列计算错误的是( ) A.5ｘ2-ｘ2=4ｘ2 B.ａm +ａm =2ａm C.3m +2m =5m D.ｘ·ｘ2m-1= ｘ2m 3. 下列四个算式中①ａ3·ａ3=2ａ3 ②ｘ3+ｘ3=ｘ6 ③ｂ3·ｂ·ｂ2=ｂ 5 ④ p 2+p 2+p 2=3p 2 正确的有( ) A.1个 B.2个 C.3个 D.4个 4. 下列各题中，计算结果写成底数为10的幂的形式，其中正确的是( ) A.100×102=103 B.1000×1010=103 C.100×103=105 D.100×1000=104 二、填空题 1. ａ4·ａ4=_______；ａ4＋ａ4=_______。 2、 b 2·b ·b 7 =________。 3、103·_______=1010 4、(-ａ)2·(-ａ)3·ａ5 =__________。 5、ａ5·ａ( )=ａ2·( ) 4=ａ18 6、(ａ+1)2·(1+ａ)·(ａ+1)5 =__________。 中等练习： 1、 (-10)3·10+100·(-102 )的运算结果是( ) A.108 B.-2×104 C.0 D.-104
算法总结 一、动态规划和递推 dp一般的解题步骤： 分析问题，弄清题意——从原问题中抽象出模型——根据模型设计状态，要求状态满足最优子结构和无后效性——直接设计状态有难度的话则需要考虑转化模型——根据设计的状态考虑转移——如果过不了题目要求的数据范围，则需要考虑优化 由于动态规划涉及的内容太多，只言片语难以讲清，所以附件中放了很多篇关于动态规划的文章，大部分系原创，并附上了一些经典的论文，主要讲了DP的优化，一些特殊的状态设计技巧 Dp和递推没有本质区别，都是用一些状态来描述问题，并记录下一些信息，根据已知信息推出未知信息，直到得到问题的解 关于DP的优化有两篇神级论文，放在附件里面了，写的非常好。 二、图论及网络流 最小生成树：克鲁斯卡尔算法和普利姆算法， ——重要性质1：最小生成树上任意两点的路径的最大边最小 ——重要性质2：最小生成树的多解（方案个数）只与相同权值的的边有关（省队集训题生成树计数） 最短路：spfa算法、堆+迪杰斯特拉算法 Spfa算法是基于松弛技术的，随机图效果极佳，最坏（网格图或存在负权环）O(nm)，适用于任意图，能够判断负权环 ——判负权环的方法：记录每个点当前从原点到它的最短路上边的条数，如果某次更新后这个条数>n-1则存在负权环 堆+迪杰斯特拉则是用了贪心的思想，不断扩大确定dist的集合，同时更新dist，如果边权有负值就不能做，复杂度是O((n+m)logn)的 拓扑排序：可以将有向图转化为一个线性的序列，满足一个点所有的前驱结点都出现在这个点在序列中的位置之前。可以判断这个有向图是否有环 ——一个简单而实用的扩展：给树做类top排序，可以有类似的功能，即每次去掉叶子结点，将树转化为一个具有拓扑关系的序列 ——再扩展：树同构判断，可用类top确定树根是谁，再最小表示法+hash即可 强连通分量、缩点：tarjan算法 核心是每个点记一个时间戳ti[i], 另外low[i]表示i点能延伸出的搜索树中节点的ti[i]的最小值，还要维护个栈记当前路径上的点，low[i]初始化为ti[i]，如果搜完i了，ti[i]=low[i]则当前栈顶到i的所有点会在一个强连同分量内。
幂的运算（基础） 【要点梳理】 要点一、同底数幂的乘法性质 +?=m n m n a a a (其中,m n 都是正整数).即同底数幂相乘，底数不变，指数相加. 要点诠释：（1）同底数幂是指底数相同的幂，底数可以是任意的实数，也可以是单项式、多项式. （2）三个或三个以上同底数幂相乘时，也具有这一性质， 即m n p m n p a a a a ++??=（,,m n p 都是正整数）. （3）逆用公式：把一个幂分解成两个或多个同底数幂的积，其中它们的底数与原来的底数相同，它们 的指数之和等于原来的幂的指数。即m n m n a a a +=?（,m n 都是正整数）. 要点二、幂的乘方法则 ()=m n mn a a (其中,m n 都是正整数).即幂的乘方，底数不变，指数相乘. 要点诠释：（1）公式的推广：(())=m n p mnp a a (0≠a ，,,m n p 均为正整数) （2）逆用公式： ()()n m mn m n a a a ==，根据题目的需要常常逆用幂的乘方运算能将某些幂变形，从 而解决问题. 要点三、积的乘方法则 ()=?n n n ab a b (其中n 是正整数).即积的乘方，等于把积的每一个因式分别乘方，再把所得的幂相乘. 要点诠释：（1）公式的推广：()=??n n n n abc a b c (n 为正整数). （2）逆用公式：()n n n a b ab =逆用公式适当的变形可简化运算过程，尤其是遇到底数互为倒数时，计 算更简便.如：1010 101122 1.22???? ?=?= ? ????? 要点四、注意事项 （1）底数可以是任意实数，也可以是单项式、多项式. （2）同底数幂的乘法时，只有当底数相同时,指数才可以相加.指数为1，计算时不要遗漏. （3）幂的乘方运算时，指数相乘，而同底数幂的乘法中是指数相加. （4）积的乘方运算时须注意，积的乘方要将每一个因式(特别是系数)都要分别乘方. （5）灵活地双向应用运算性质，使运算更加方便、简洁. （6）带有负号的幂的运算，要养成先化简符号的习惯. 【典型例题】 类型一、同底数幂的乘法性质 1、计算： （1）2 3 4 444??；（2）3 4 5 2 6 22a a a a a a ?+?-?； （3）1 1211()()()()()n n m n m x y x y x y x y x y +-+-+?+?+++?+． 【答案与解析】 解：（1）原式23494 4++==． （2）原式3452617777 2222a a a a a a a +++=+-=+-=． （3）原式11 211222() ()()()2()n n m n m n m n m n m x y x y x y x y x y +++-++-+++=+++=+++=+． 【总结升华】（2）（3）小题都是混合运算，计算时要注意运算顺序，还要正确地运用相应的运算法则，并要注意区别 同底数幂的乘法与整式的加减法的运算法则．在第（2）小题中a 的指数是1．在第（3）小题中把x y +看成一个整体． 举一反三： 【变式】计算： （1）5 3 2 3(3)(3)?-?-； （2）221() ()p p p x x x +?-?-（p 为正整数）； （3）232(2)(2)n ?-?-（n 为正整数）． 【答案】 解：（1）原式5 3 2 5 3 2 532 103(3)333333++=?-?=-??=-=-． （2）原式22122151()p p p p p p p x x x x x +++++=??-=-=-． （3）原式525216222 (2)22n n n +++=??-=-=-．
有朋友问我的博文《素性测试》中的Miller-Rabin算法的大数模幂运算快速算法怎么理解，由于在《素性测试》中没有讲解算法原理，所以在此单独一个篇文章详细讲这个算法。这是一个在密码学中比较重要的算法，在我的《素性测试》一文则是用于实现费马小定理。 首先我们先把问题简化一下，看看如何快速求a^b. 先看看我们熟知的两个数学公式： a^(2c) = (a^c)^2； a^(2c+1) = a*((a^c)^2)； 我们就利用这两个数学公式来解决这个问题，比如a=3,b=13时，我们把b写成二进制的形式13(10)=1101(2),我们从低位到高位运算，每运算一位可以将b右移一位，上面的例子可以转化成3^13 = 3^1 * 3^4 * 3^8,结合上面的两个数学公式我们可以写出如下的代码： 代码清单： [java]view plain copy
如上面的叙述叙述中可以看出快速pow算法的时间复杂度取决于b的二进制位数，而传统的一位一位累乘的pow算法的时间复杂度取决于b的大小，例如上述例子中，两种算法的运算次数分别为4次，和13次。随着b的增大，效率上的差距是显然的。 下面进入我们的主题---大数模幂运算快速算法(a^b % m) 要计算这个，我们首先还要知道一个数学公式： a^b % m = (...((a % m) * a) % m) ......* a) % m其中a%m有b个 下面我还用上面b=13的例子，利用这个公式来证明下 a^13 % m = ((a^8) % m) * ((a^4) % m) * ((a^1) % m) 证明： 由a^b % m = (...((a % m) * a) % m) ......* a) % m其中a%m有b个得 a^8 % m = (...((a % m) * a) % m) ......* a) % m其中a%m有8个 a^4 % m = (...((a % m) * a) % m) ......* a) % m其中a%m有4个 a^1 % m = (...((a % m) * a) % m) ......* a) % m 其中a%m有1个 所以((a^8) % m) * ((a^4) % m) * ((a^1) % m) = (...((a % m) * a) % m) ......* a) % m 其中a%m有13个= a^13 % m ； 证毕。 由上面我们证明的公式和第一个pow的例子，容易写出代码如下： 代码清单： [java]view plain copy
幂的运算方法总结-标准化文件发布号：（9556-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII
?幂的运算方法总结 幂的运算的基本知识就四条性质，写作四个公式： ①a m×a n=a m+n ②(a m)n=a mn ③(ab)m=a m b m ④a m÷a n=a m-n 只要理解掌握公式的形状特点，熟悉其基本要义，直接应用一般都容易，即使运用公式求其中的未知指数难度也不大。 问题1、已知a7a m=a3a10，求m的值。 思路探索：用公式1计算等号左右两边，得到等底数的同幂形式，按指数也相等的规则即可得m的值。 方法思考：只要是符合公式形式的都可套用公式化简试一试。 方法原则：可用公式套一套。 但是，渗入幂的代换时，就有点难度了。 问题2、已知x n=2,y n=3,求(x2y)3n的值。 思路探索：(x2y)3n中没有x n和y n，但运用公式3就可将(x2y)3n化成含有x n 和y n的运算。 因此可简解为，(x2y)3n =x6n y3n=(x n)6(y n)3=26×33=1728 方法思考：已知幂和要求的代数式不一致，设法将代数式变形，变成已知幂的运算的形式即可代入求值。 方法原则：整体不同靠一靠。 然而，遇到求公式右边形式的代数式该怎么办呢？ 问题3、已知a3=2,a m=3,a n=5，求a m+2n+6的值。 思路探索：试逆用公式，变形出与已知同形的幂即可代入了。
简解：a m+2n+6=a m a2n a6=a m(a n)2(a3)2=3×25×4=300 方法思考：遇到公式右边的代数式时，通常倒过来逆用公式，把代数式展开，然后代入。 方法原则：逆用公式倒一倒。 当底数是常数时，会有更多的变化，如何思考呢？ 问题4、已知22x+3－22x+1=48，求x的值。 思路探索：方程中未知数出现在两项的指数上，所以必须统一成一项，即用公式把它们变成同类项进行合并。由此，可考虑逆用公式1，把其中常数的整数指数幂，化作常数作为该项的系数。 简解：22x+3－22x+1=22x×23－22x×21=8×22x－2×22x =6×22x=48 ∴22x=8 ∴2x=3 ∴x=1.5 方法思考:冪的底数是常数且指数中有常数也有未知数时，通常把常数的整数指数冪化成常数作为其它冪的系数，然后进行其它运算。 问题5、已知64m+1÷2n÷33m=81,求正整数m、n的值。 思路探索：幂的底数不一致使运算没法进行，怎样把它们变一致呢？把常数底数都变成质数底数就统一了。 简解：64m+1÷2n÷33m =24m+1×34m+1÷2n÷33m=24m+1-n×3m+1=81=34 ∵m、n是正整数∴m+1=4,4m+1－n=0 ∴m=3,n=13 方法思考：冪的底数是常数时，通常把它们分解质因数，然后按公式3展开，即可化成同底数冪了。 问题6、已知2a=3,2b=6,2c=12，求a、b、c的关系。 思路探索：求a、b、c的关系，关键看2a、2b、2c的关系，即3、6、12的关系。6是3的2倍，12是6的2倍，所以2c=2×2b=4×2a,由此可求。 简解：由题意知2c=2×2b=4×2a ∴2c=2b+1=2a+2
数学 ——Shine_Sky -13,快速幂 先有一个问题给出n , k 求n k,如果k 很小我们完全可以用一个for 循环得出答案，但是往往OI 中要求幂的题出题人都不会良心，所以我们得学习快速幂。 虽然C++中的cmath 库中有个pow 函数可以快速求出n k但是其缺陷是不能及时取mo 所以而且又返回double 所以难以储存为我们想要的，所以我们不提起它 现在相求1001000mod1000007 如果我们用for 循环那么时间复杂度是O(k) = O(1000)的虽然这不大，但是接下来看快速幂就知道这是有多慢了 我们将k 转换为二进制就是1111101000 即1000 = 23 + 25 + 26 + 27 + 28 + 29; 由于同底数幂的运算我们可以把1001000转换为 10023 × 10025 × 10026 × 10027 × 10028 × 10029 这样我们可以发现我们只要运算log2k次也就是说6 次，怎么实现得到每一个小数的值呢，for 循环肯定不能考虑我们看到二进制就可以想到位运算，我们用k&1 判断k 的二进制最后一位是不是1，是则ans *= x 如果不是就不作为然后再将 x *= x 并k 右移一位伪代码如下： Int ans = 0; while(k 非 0) {
If(k 最后一位是1) ans *= x; X *= x; k 右移一位 } -14，矩阵乘法 数学上的东西（这几章都关于数学，这是个废话），是用来计算两个数矩形的积的其中公式为我们现在有两个矩阵A , B 如果要求他们的积，则必须满足A 的第一行与B 的第一列相同则有积C 各个位置值为; 例子：无 -13 + 14 矩阵快速幂 将上述两个结合起来，我们只要把快速幂的乘法更换一下改为一个函数，这个函数是用来求矩阵乘法的，这都不是很困难，但是我们要返回一个 2 维数组，我们用一的方法很难做到，所以要用不一般的，我们定义一个结构体 JX 储存一个矩阵，再将快速幂和矩阵乘法的返回值改为 JX 就好了，下见 Code(为了容易截图，压了行)