第16章

数论问题

陈宇：数论的模版

在群共享里的 自己浙大模版里有

本章将要讨论在ACM程序设计竞赛中出现比较多的一类问题：数论问题。由于数论问题涉及的数学知识比较多、比较深奥，不能在短短的一章中全部予以介绍，只能通过介绍一些案例来说明常见的数论问题。

16.1 数的幂运算

有一类常见的运算，就是求形如amodm的值，一般情况下，我们可以用幂的定义来做：通过乘法的倍乘来实现，需要做b次乘法和模运算。如果b比较大时，这样的方法就不行了，本节介绍一种只需要O(log2b)次乘法和模运算的方法。

幂的计算方法

首先将指数变成二的幂次和的形式。如5=1+4=20+22，11=1+2+8=20+21+23。如果b可以表示为b?2b0?2b1???2bk的形式，那么ab可以表示为

ba?aib2b0?2b1???2bk?a2b0?2??a2b12bk

表面上看这样的表达式更复杂了，但注意到上面的表达式的乘积项不超过(log2b)，同时，形如a2（i=0,1….）有如下的递推式：

a2ii?1?a2??

i2也就是说，后项可以通过前项的平方来得到。所以可以先将形如a2（i=0,1….）的值求

i出来，记为ri?a2（i=0,1….log2b）,则a?rb?rb???rb，不超过(log2b)次乘法。

采用以上的方法计算乘方的时间复杂度为O(log2b)。

12kb16.1.1 〖案例1〗高级模运算 10388 hnu oj

人与人是不同的,有些人喜欢阅读满是女孩子的杂志，有些人喜欢在地下室引爆炸弹，而还有一些却喜欢一些麻烦的数字游戏。比如ESSE论坛的一次活动：

每个人选择两个数字Ai和Bi写在纸上，其他人不能看见。过了一段时间后，每个人说出自己纸上的数字，然后每个人的目标是求出所有的AiBi的和模M的值，最先算出结果

ACM程序设计培训教程

的，就是胜利者。

作为一个程序员，你当然有办法编一个程序，以最快的速度算出结果，赢得比赛。

输入包含Z组测试数据，输入第一行只包含数字Z。随后是测试数据：第一行是一个数字M(1≤M≤45000)。第二行是数字H（1≤H≤45000）表示参加游戏的人数。接下来H行，每行两个数Ai和Bi（1≤Ai，Bi≤231）。表达式的值：

(A1B1+A2B2+...+AHBH)mod M.

3

16 4 2 3 3 4 4 5 5 6 36123 1

2374859 3029382 17 1 318132

对于每组测试数据，输出以下

样例输出2

13195 13

取模运算可以与加、减、乘、乘方交换次序；

(a+b)%m=a%m+b%m a*b%m=(a%m)*(b%m) ab%m=(a%m)b

所以表达式的任何中间结果都可以进行取模运算，使得中间结果不至于太大而溢出。

本题的关键在于计算形如ab%m的表达式的值，因为b的值较大，采用连乘的方法是不行的，采用本节介绍的只需要O(log2b)次乘法和模运算的方法。

232· ·

第16章 数论问题

voidcal(unsigned*r,longunsigneda,unsignedm){ //计算a的2j次方对m取模的结果,用数组r保存 r[0]=a%m;

for(i=1;i<32;++i)

r[i]=(long)r[i-1]*r[i-1]%m;//ri+1=ri*ri

}

unsignedcalc(unsignedm,longunsigneda,longunsignedb){ //函数计算ab%m的值

intbl[32],r[32];//bl是b的二进制结果，r[i]=a的2j次方对m取模的结果 cal(r,a,m);//计算r[i]

while(b){//将b用二进制形式表示,结果保存在bl中

bl[i++]=b%2; b>>=1;}

for(j=0,k=1;j

if(bl[j])//如果

b对应二进制位bj为1,则对应的rbj在幂的乘积表达式中，否则不在

k=k*r[j]%m;

returnk;}

intmain(){ scanf(\while(z--){

scanf(\ for(j=s=0;j

scanf(\ s=(s+calc(m,a,b))%m;}//计算

AjBj的值，并将其和求出来，结果用变量s保存

printf(\

16.2 欧拉定理的应用

定理(Fermat)1：如果p是素数，则对任意的a，有ap?1modp?1。

定理(Euler)2：如果p不是素数，则对任意的(a,p)=1，有a?(p)modp?1，其中的

?1??1??1???????(p)?p?1?1??1???????，p1,p2,…,pk是p的所有素数因子。 ppp1??2?k???16.2.1 〖案例2〗快乐2004

考虑到一个正整数X，S是所有2004X的因子的和，你的目标是求出S除以29的余数。

看看X=1的例子，20041的所有因子为1,2,3,4,6,12,167,334,501,668,1002和2004，因

·233·

ACM程序设计培训教程

此S=4704，而4704 mod 29 =6。

输入有多个测试序列，每个测试序列一行一个正整数X，(1<=X<=10000000)。 X=0表示输入结束，并且不需要处理。

对每个测试序列，输出一行就是S除以29的余数。

10000 0

10

题目要求的是（2004X）的因子和对29取模的结果 求某个数A的所有因子和，首先将该数分解：

A?p11?p22??pnn，其中p1,p2,...,pn都是素数，则A的任意因子可以表示为：

d?p11?p22??pnn，其中0?i1?r1,....0?in?rn

pnn?1p11?1p22?1???? 将其求和，为S?p1?1p2?1pn?1r?1r?1r?1rrriii如：2004=22*3*167，则

23?132?11672?1S????7?4?168?4704

2?13?1167?1而2004X?22X?3X?167X

22X?1?13X?1?1167X?1?1r???所以S?，其中r?(22X?1?1)(3X?1?1)(167X?1?1) 2?13?1167?1332X还很大(1?X?10000000)，根据Fermat定理,任意素数p,任意数a,有ap?1modp?1，则a28mod29?1，所以abmod29?abmod28mod29

所以首先将X对28取模，x=X(是取模的结果，x就很小了(0?x<28，有了这点，输入的X再大也没关系)，简单计算就可以得到r的值。

最后，考虑到：S?rmod29，也即r?29k?332S，k是满足等式的任意整数。

332而9?332?103?29?1，9?(r?29k)?9?332S?S?103?29S 所以r?9mod29?Smod29

例如当X=10000时，计算200410000=220000*310000*16710000的所有因子和对29取模的结果

220001?1310001?116710001?1r其S? ???2?13?1167?1332 234· ·