第1章 利用快速幂提高幂运算效率

1.1 快速幂取模

1.1.1 快速幂取模的概念

设有整数a、自然数i，快速幂求解ai的思想就是每次把指数变小（指数除以2）、底数变大（进行底数平方运算），以减少运算次数，即：如果i是偶数，则，否则，。整数快速幂的程序段如下：

数论计算中有这样一种运算：求一个数的幂对另外一个数的模的运算，即abmodn，其中a和b是非负整数，n是正整数。这样的运算被称为模取幂。在许多素数测试子程序和RSA公开密钥加密系统中，模取幂运算是一种很重要的运算。所以，我们希望找到一种高效的方法来计算abmodn的值。

快速模取幂运算基于整数快速幂，即，用二进制来表示b时，采用反复平方法。设幂次b的二进制表示为(bk,bk-1,…,b1,b0)，即位长为k+1，其中bk为最高有效位，b0为最低有效位。快速模取幂运算的过程随着a的幂值从0到b成倍增长，最终计算出ab%n，其程序段如下：

显然，快速模取幂的算法复杂度为O(log2b)。

【1.1.1.1 Raising Modulo Numbers】

给出n对数字Ai和Bi(1≤i≤n)，以及一个整数M。请求解() modM。

输入

输入包含Z个测试用例，在输入的第一行给出正整数Z。接下来给出每个测试用例。每个测试用例的第一行给出整数M(1≤M≤45000)，总和将除以这个数取余数；接下来的一行给出数字的对数H(1≤H≤45000)；接下来的H行，在每一行给出两个被空格隔开的数字Ai和Bi，这两个数字不能同时等于零。

输出

对于每一个测试用例，输出一行，是表达式() modM的结果。

试题来源：CTU Open 1999

在线测试：POJ 1995，ZOJ 2150

试题解析

本题可以基于整数快速幂和模运算规则，通过快速模取幂的算法求解。基本模运算规则如下：

在参考程序中，通过基于整数快速幂和模运算规则的快速模取幂函数modexp(a,b,m)求解ab%m。

参考程序

1.1.2 快速幂取模的应用

在快速幂取模的应用实验中，加法原理和乘法原理被用于解题。

定理1.1.2.1（加法原理） 设A和B是有限集合S的两个互不相交的子集，且A∪B=S，则|S|=|A|+|B|。

证明：集合S中的元素在子集A中的个数有|A|个，因为A和B互不相交，且A∪B=S，所以S中的元素不在A中必在B中，且B中的元素不在A中，则在S中不在A中的元素有|B|个，即|S|=|A|+|B|。■

例如，每天从上海到北京的高铁车次有25次，民航航班有20班，则每天从上海到北京乘坐高铁和民航的方式共有25+20=45（种）。

定理1.1.2.2（乘法原理） 设A和B是有限集合，|A|=p，|B|=q，则|A×B|=p×q。

例如，有2门数学课和4门计算机课，某学生要选数学课和计算机课各一门，则有2×4=8种选课方法。

【1.1.2.1 Teams】

从前有一种古老的游戏，这个游戏的特点是，每个队的队员数量没有限制，只要队中有队长就行。（这个游戏完全是战略性的，所以有时候玩家少了会增加获胜的机会）。因此，有n名队员，教练选择k(1≤k≤n)名队员参加比赛，并让其中一人担任队长。给您的任务很简单，只要找出一个教练可以用多少种方式从他的n名队员中挑选一支参赛队即可。这里要注意，队员相同但队长不同的参赛队被认为是不同的队伍。

输入

输入的第一行给出测试用例数T(T≤500)。接下来的T行每行给出n的值（1≤n≤109），即教练所拥有的队员数量。

输出

对于输入的每一行，输出测试用例的编号，然后给出可以以多少种方式选择队伍。请输出答案模100000007的结果。有关确切的格式，请参见样例输入和样例输出。

试题来源：The first contest of the new season, 2009

在线测试：UVA 11609

试题解析

先从n名队员中选k名队员，再从k名队员里选一个队长，根据乘法原理，有C(n,k)×C(k, 1)种方式；又因为1≤k≤n，根据加法原理，选择队伍的方式数为。

因为C(n,k)×C(k,r)=C(n,r)×C(n-r,k-r)，其中k≥r，所以C(n,k)×C(k, 1)=C(n, 1)×C(n-1,k-1)，则，而为(1+1)n-1的展开式，所以选择队伍的方式数为n×2n-1。

参考程序通过快速幂取模运算求解2n-1%1000000007。

参考程序

【1.1.2.2 Key Set】

给出一个由n个整数{1, 2,…,n}组成的集合S。如果一个集合中的整数之和是偶数，则该集合被称为键集（key set）。问：集合S中有多少非空子集是键集？

输入

输入给出多个测试用例。输入的第一行给出一个整数T(1≤T≤105)，表示测试用例的个数。

对于每个测试用例，在一行中给出一个整数n(1≤n≤109)，表示集合中的整数数目。

输出

对于每个测试用例，输出键集数模100000007运算的结果。

试题来源：2015 Multi-University Training Contest 6

在线测试：HDOJ 5363

试题解析

本题给出一个由n个整数{1, 2,…,n}组成的集合S。问：集合S中有多少这样的非空子集：子集里面所有元素的和为偶数？

在集合S中有n/2个偶数、(n+1)/2个奇数。要使S的子集里面所有元素的和为偶数，则在该子集中，偶数个数为0, 1, 2,…,n/2，奇数个数为偶数个。假设S中有a个偶数、b个奇数，则根据加法原理和乘法原理，S中元素和为偶数的子集数为(C(a, 0)+C(a, 1)+C(a, 2)+…+C(a,a))×(C(b, 0)+C(b, 2)+C(b, 4)+…+C(b, 2×(b/2)))。根据二项式定理以及推论，C(a, 0)+C(a, 1)+C(a, 2)+…+C(a,a)=(1+1)a=2a，C(b, 0)-C(b, 1)+C(b, 2)-C(b, 3)+…+(-1)bC(b,b)=(1-1)b=0，该二项式展开式中奇数项系数之和等于偶数项系数之和，所以C(b, 0)+C(b, 2)+C(b, 4)+…+C(b, 2×(b/2))=(1+1)b/2=2b-1。所以，S中元素和为偶数的子集数为2a+b-1，即2n-1。

又因为键集是非空的子集，所以要去掉C(a, 0)×C(b, 0)的情况。本题要求对键集数模100000007运算的结果，所以最终结果为(2n-1-1) mod 100000007。由于结果比较大，因此通过快速幂取模进行计算。

参考程序

【1.1.2.3 Turn the pokers】

暑假，Alice在家里待了很长时间，无所事事。她出去买了m张扑克牌，打算玩扑克。但她不想玩传统的游戏，想要改变。她把这些扑克牌面朝下，然后，把扑克牌翻转n遍，每遍她能翻转Xi张扑克牌。她想知道能得到多少种结果。你能帮她解决这个问题吗？

输入

输入给出若干测试用例。

每个测试用例第一行给出两个非负整数n(n>0)和m(m≤100000)。接下来的一行给出n个整数Xi(0≤Xi≤m)。

输出

对于每个测试用例，在一行中输出对答案数进行模1000000009运算的结果。

提示

对于第2个样例，0表示牌面向下，1表示牌面向上。初始时状态为000。第一个结果为000→111→001→110，第二个结果为000→111→100→011，第三个结果为000→111→010→101。因此，有3种结果（110, 011, 101）。

试题来源：2014 Multi-University Training Contest 1

在线测试：HDOJ 4869

试题解析

对于扑克牌，0表示牌面向下，1表示牌面向上。初始时牌面都向下。如果最后有x张牌的牌面向上，一共有m张扑克牌，这种情况对答案的贡献为C(m,x)。所以要知道最后可能的牌面向上的牌数。

每次翻转扑克牌的张数Xi是确定的。如果Xi为奇数，那么这次翻转后1的个数的增量一定是奇数（增量可以是负奇数）；同理，如果Xi为偶数，那么这次翻转后1的个数的增量也一定是偶数（增量可以是负偶数）。所以，如果所有Xi的和为奇数，则最后的牌面向上的牌数是奇数；同理，如果所有Xi的和为偶数，则最后的牌面向上的牌数也是偶数。设所有翻转完成后，牌面向上的牌数最小是L，最大是R，牌面向上的牌数为L+2，L+4，…，R-2也都是可以达到的，而且L和R一定是同奇偶的。根据加法原理，最后可能的牌面向上的牌数为C(m,L)+C(m,L+2)+…+C(m,R-2)+C(m,R)。

因此，首先要确定L和R。

计算牌面向上的最小牌数L，就是计算最小的1的数目，每次都尽可能多地把1转化为0；而计算牌面向上的最大牌数R，就是计算最大的1的数目，每次都尽可能多地把0转化为1。可以用两组if语句分别确定L和R。

第一组if语句确定L。

●如果当前牌面向上的最小牌数L大于或等于现在翻牌的数量Xi，即L≥Xi，就把Xi张牌面向上的牌翻转，也就是把1变成0，则L=L-Xi；

●如果当前牌面向上的最小牌数L小于现在翻牌的数量Xi，而牌面向上的最大牌数R大于或等于本次翻牌的数量Xi，即L<Xi≤R，因为翻牌数量在上下限之间，所以可以把当前牌面朝上的牌的数量变为0或1（不是绝对能变为0，因为有可能当前牌面向上的牌数为奇数，而翻牌的次数是偶数），所以要判断L和Xi的奇偶性是否一样，如果一样，则牌面向上的最小牌数L变为0，否则变为1。

●如果当前牌面向上的最大牌数R小于现在翻牌的数量Xi，即R<Xi，则在把1全部变为0的同时，还有Xi-R个0变为1，即L=Xi-R。

第二组if语句确定R。

●如果当前牌面向上的最大牌数R和现在翻牌的数量Xi的和没有超过总牌数m，即R+Xi≤m，则把Xi张牌面向下的牌翻转，0变成1，这样使1最多，即R=R+Xi。

●如果当前牌面向上的最大牌数R和现在翻牌的数量Xi的和超过总牌数m，而如果当前牌面向上的最小牌数L和现在翻牌的数量Xi的和没有超过总牌数m，即L+Xi≤m<R+Xi，则要判断L+Xi和m的奇偶性是否相同，如果相同，则新状态中必定所有牌的牌面都朝上，即全是1，R=m，如果不同，则R=m-1。

●如果当前牌面向上的最小牌数L和现在翻牌的数量Xi的和超过总牌数m，即L+Xi>m，把m个1变成0，那么还要翻L+Xi-m张牌，最终得到m-(L+Xi-m)个1，所以R=2m-L-Xi。

在确定L和R之后，计算C(m,L)+C(m,L+2)+…+C(m,R-2)+C(m,R)。

因为，所以，。用数组c表示组合数C(m,i)，则c[0]=1，c[i]=c[i-1]×(m-i+1)/i。本题要求对结果进行模1000000009运算。根据费马小定理，如果p是素数、a是正整数，且GCD(a,p)=1，则ap-1≡1(modp)。所以和ap-2模p同余。设p=1000000009，c[i]=c[i-1]×(m-i+1)%p×ip-2%p。所以，需要通过快速幂取模运算求解。

参考程序