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

1.1 快速幂取模

1.1.1 快速幂取模的概念

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

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

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

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

【1.1.1.1 Raising Modulo Numbers】

给出 n 对数字 A _i 和 B _i (1≤ i ≤ n )，以及一个整数 M 。请求解( ) mod M 。

输入

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

输出

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

试题来源：CTU Open 1999

在线测试：POJ 1995，ZOJ 2150

试题解析

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

在参考程序中，通过基于整数快速幂和模运算规则的快速模取幂函数modexp( a , b , m )求解 a ^b % 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 ≤10 ⁹ ），即教练所拥有的队员数量。

输出

对于输入的每一行，输出测试用例的编号，然后给出可以以多少种方式选择队伍。请输出答案模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 ×2 ^{n -1} 。

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

参考程序

【1.1.2.2 Key Set】

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

输入

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

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

输出

对于每个测试用例，输出键集数模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 =2 ^a ，C( b , 0)-C( b , 1)+C( b , 2)-C( b , 3)+…+(-1) ^b C( b , b )=(1-1) ^b =0，该二项式展开式中奇数项系数之和等于偶数项系数之和，所以C( b , 0)+C( b , 2)+C( b , 4)+…+C( b , 2×( b /2))=(1+1) ^b /2=2 ^{b -1} 。所以， S 中元素和为偶数的子集数为2 ^{a + b -1} ，即2 ^{n -1} 。

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

参考程序

【1.1.2.3 Turn the pokers】

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

输入

输入给出若干测试用例。

每个测试用例第一行给出两个非负整数 n ( n >0)和 m ( m ≤100000)。接下来的一行给出 n 个整数 X _i (0≤ X _i ≤ 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 )。所以要知道最后可能的牌面向上的牌数。

每次翻转扑克牌的张数 X _i 是确定的。如果 X _i 为奇数，那么这次翻转后1的个数的增量一定是奇数（增量可以是负奇数）；同理，如果 X _i 为偶数，那么这次翻转后1的个数的增量也一定是偶数（增量可以是负偶数）。所以，如果所有 X _i 的和为奇数，则最后的牌面向上的牌数是奇数；同理，如果所有 X _i 的和为偶数，则最后的牌面向上的牌数也是偶数。设所有翻转完成后，牌面向上的牌数最小是 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 大于或等于现在翻牌的数量 X _i ，即 L ≥ X _i ，就把 X _i 张牌面向上的牌翻转，也就是把1变成0，则 L = L-X _i ；

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

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

第二组if语句确定 R 。

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

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

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

在确定 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，则 a ^{p -1} ≡1(mod p )。所以 和 a ^{p -2} 模 p 同余。设 p =1000000009， c [ i ]= c [ i -1]×( m-i +1)% p × i ^{p -2} % p 。所以，需要通过快速幂取模运算求解。

参考程序 GWS+eaEGpIEmkwMttFi+M98KHCA96PgV4PCE7h6PlUGUX4aczBLPbP7je8W7VSJ8