《竞赛辅导数论问题.ppt》由会员分享，可在线阅读，更多相关《竞赛辅导数论问题.ppt（45页珍藏版）》请在三一文库上搜索。
1、数论问题,Lecture by Hao Wu,常见的数论问题,1.数的幂运算 2.欧拉定理的应用 3.素数测试 4.Pell方程 5.其它,案例1：模的运算,描述,人与人是不同的,有些人喜欢阅读满是女孩子的杂志，有些人喜欢在地下室引爆炸弹，而还有一些却喜欢一些麻烦的数字游戏。比如ESSE论坛的一次活动： 每个人选择两个数字Ai和Bi写在纸上，其他人不能看见。过了一段时间后，每个人说出自己纸上的数字，然后每个人的目标是求出所有的AiBi的和模M的值，最先算出结果的，就是胜利者。 作为一个程序员，你当然有办法编一个程序，以最快的速度算出结果，赢得比赛。,相当于求 A1B1+A2B2+.+AHBH)
2、 mod M.,解题思路（1）,取模运算可以与加、减、乘、乘方交换次序； (a+b)%m=a%m+b%m a*b%m=(a%m)*(b%m) ab%m=(a%m)b,解题思路（2）,有一类常见的运算，就是求形如的值，一般情况下，我们可以用幂的定义来做：通过乘法的倍乘来实现，需要做b次乘法和模运算。如果b比较大时，这样的方法就不行了，本节介绍一种只需要O(log2b)次乘法和模运算的方法。,解题思路（3）,首先将指数变成二的幂次和的形式。如5=1+4=20+22，11=1+2+8=20+21+23。如果b可以表示为的形式，那么ab可以表示为,解题思路（4）,表面上看这样的表达式更复杂了，但注意到
3、上面的表达式的乘积项不超过(log2b)，同时，形如（i=0,1.）有如下的递推式：,解题思路（5）,后项可以通过前项的平方来得到。所以可以先的值求出来，不超过(log2b)次乘法。,核心代码及解释 （1）,voidcal(unsigned*r,longunsigneda,unsignedm) /计算a的2j次方对m取模的结果,用数组r保存 r0=a%m; for(i=1;i32;+i) ri=(long)ri-1*ri-1%m;/ri+1=ri*ri ,核心代码及解释 （2）,unsignedcalc(unsignedm,longunsigneda,longunsignedb) /函数计算a
4、b%m的值 intbl32,r32;/bl是b的二进制结果，ri=a的2j次方对m取模的结果 cal(r,a,m);/计算ri while(b)/将b用二进制形式表示,结果保存在bl中 bli+=b%2; b=1; for(j=0,k=1;ji;+j)/计算乘方，时间复杂度为i=O(log2b) if(blj)/如果b对应二进制位bj为1,则对应的rbj在幂的乘积表达式中，否则不在 k=k*rj%m; Return k;,核心代码及解释 （3）,Int main() scanf(“%d“,欧拉定理1,如果p是素数，则对任意的a，有,欧拉定理2,如果p不是素数，则对任意的a，有,p1,p2,pk
5、是p的所有素数因子,案例2：快乐2004,Time Limit: 1000ms Special Time Limit:2500ms Memory Limit:32768KB,描述,考虑到一个正整数X，S是所有2004X的因子的和，你的目标是求出S除以29的余数。 看看X=1的例子，20041的所有因子为1,2,3,4,6,12,167,334,501,668,1002和2004，因此S=4704，而4704 mod 29 =6。,输入,输入有多个测试序列，每个测试序列一行一个正整数X，(1=X=10000000)。 X=0表示输入结束，并且不需要处理。,输出,对每个测试序列，输出一行就是S除以
6、29的余数。,输入样例,1 10000 0,输出样例,6 10,解题思路（1）,题目要求的是（2004X）的因子和对29取模的结果 求某个数A的所有因子和，首先将该数分解： 其中p1,p2,.,pn都是素数，则A的任意因子可以表示为：,其中0i1r1,0inrn,解题思路（2）,如：2004=22*3*167，则,解题思路（3）,解题思路（4）,X还很大( )，根据Euler定理,所以首先将X对28取模，x=X%28是取模的结果，x就很小了(0x28，有了这点，输入的X再大也没关系)，简单计算就可以得到r的值,解题思路（5）,解题思路（6）,当X=10000时，计算200410000=2200
7、00*310000*16710000的所有因子和对29取模的结果,20001%28=9,10001%28=5,167%29=22. r=(29-1)(35-1)(225-1)%29=18*10*12%29=14 S%29=r*9%29=14*9%29=10, 2004100000的所有因子和对29取模的结果是10,核心代码及解释 （1）,int mod29(int x) for(r=0;r=x;+r) f=f*(r=x?2:4)%29; /f表示22x+1的值 t=t*3%29; /t表示3x+1的值 d=d*22%29; /d表示167x+1的值 r=(f-1)*(t-1)*(d-1)%29
8、; /S=r/332,r的值 return r*9%29; /S%29=r*9%29 ,核心代码及解释 （2）,int main() while(scanf(“%d“, ,案例3：2x mod n=1,Time Limit: 1000ms Special Time Limit:2500ms Memory Limit:32768KB,描述,给定一个整数n，求一个最小的整数x，使得2x mod n = 1,输入,每行一个正整数n,.(0 n 231-1),输出,如果最小的正整数存在，输出一行2x mod n = 1，其中的x和n用输入的n值和最小的x值代替；否则，输出一行2? mod n = 1,
9、输入样例,2 5,输出样例,2? mod 2 = 1 24 mod 5 = 1,解题思路（1）,本题首先想到的可能是暴力搜索，从x=1开始，逐步加大x，找到使得2x mod n = 1的x就输出。但考虑到n比较大，满足2x mod n = 1的x可能也很大，所以直接求解的方法不行。,解题思路（2）,Euler定理,解题思路（3）,x一定是phi(n)的因子,解题步骤,1 求解x=phi(n); 2 找出phi(n)的所有素因子pi; 3 让x=x/pi,直到2x mod n1或pi不能整除x.如果2x mod n1，x=x*pi; 4 重复2； x就是满足2x mod n = 1最小的x。,解
10、题思路（4）,因为求phi(n)和找出phi(n)的所有素因子pi都需要知道在215。546340内的所有素数，所以在问题求解前，先作预处理：利用筛法将所有小于46340的素数求出来,核心代码及解释 （1）,int prime5000, no_prime; /根据素数分布定律，小于46340的素数约5000个 sieve() /采用筛法求所有小于46340的素数short p23170; /求所有小于46340的素数，因为大于2的偶数都不是素数，所以筛法只对应所有的大于1小于46340的奇数 /如果pi=1表示2*i+3是素数,否则pi=0表示2*i+3不是素数。 for(i=0;i23170
11、;+i)pi=1; /初始化，假定所有奇数都是素数 for(i=0;i106;+i) /106=sqrt(46340)/2-3 if(pi)for(k=(i1)+3,j=(k+1)*(i+1)-1;j23170;j+=k)pj=0;for(primei=j=0=2;i23170;+i)if(p i)prime+j=(i1)+3;nb_prime=j+1;,核心代码及解释 （2）,int ttn(int i,int n) /函数计算2i mod n=?_int64 t=2,r=1; /用64位长整型防止中间结果溢出,while(i) if(i,核心代码及解释 （3）,int phi(int n)
12、 / 函数求phi(n)result=temp=n;k=sqrt(n);for(i=0;primei=k,核心代码及解释 （4）,int main()sieve();while(scanf(“%d“,Description Given a big integer number, you are required to find out whether its a prime number. Input The first line contains the number of test cases T (1 = T = 20 ), then the following T lines each contains an integer number N (2 = N 254). Output For each test case, if N is a prime number, output a line containing the word “Prime“, otherwise, output a line containing the smallest prime factor of N. Sample Input 2 5 10 Sample Output Prime 2,