竞赛辅导数论问题.ppt

数论问题数论问题 Lecture by Hao Wu常见的数论问题 •1.数的幂运算 •2.欧拉定理的应用 •3.素数测试•4.Pell方程•5.其它 案例案例1：模的运算：模的运算 描述描述•人与人是不同的,有些人喜欢阅读满是女孩子的杂志，有些人喜欢在地下室引爆炸弹，而还有一些却喜欢一些麻烦的数字游戏比如ESSE论坛的一次活动：•每个人选择两个数字Ai和Bi写在纸上，其他人不能看见过了一段时间后，每个人说出自己纸上的数字，然后每个人的目标是求出所有的AiBi的和模M的值，最先算出结果的，就是胜利者•作为一个程序员，你当然有办法编一个程序，以最快的速度算出结果，赢得比赛 •相当于求•A1B1+A2B2+...+AHBH) mod M. 解解题思路思路（（1 1）） •取模运算可以与加、减、乘、乘方交换次序；•(a+b)%m=a%m+b%m•a*b%m=(a%m)*(b%m)•ab%m=(a%m)b 解解题思路思路（（2 2））•有一类常见的运算，就是求形如的值，一般情况下，我们可以用幂的定义来做：通过乘法的倍乘来实现，需要做b次乘法和模运算如果b比较大时，这样的方法就不行了，本节介绍一种只需要O(log2b)次乘法和模运算的方法。

 解解题思路思路（（3 3））•首先将指数变成二的幂次和的形式如5=1+4=20+22，11=1+2+8=20+21+23如果b可以表示为的形式，那么ab可以表示为解解题思路思路（（4 4））•表面上看这样的表达式更复杂了，但注意到上面的表达式的乘积项不超过(log2b)，同时，形如（i=0,1….）有如下的递推式： 解解题思路思路（（5 5））•后项可以通过前项的平方来得到所以可以先的值求出来，不超过(log2b)次乘法 核心代核心代码及解及解释 （（1 1））•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•}核心代核心代码及解及解释 （（2 2））•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

•看看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除以29的余数 输入入样例例 •1•10000•0 输出出样例例 •6•10 解解题思路思路（（1 1））•题目要求的是（2004X）的因子和对29取模的结果•求某个数A的所有因子和，首先将该数分解： •其中p1,p2,...,pn都是素数，则A的任意因子可以表示为：•其中0i1r1,....0inrn 解解题思路思路（（2 2））•如：2004=22*3*167，则 解解题思路思路（（3 3））解解题思路思路（（4 4））•X还很大(            )，根据Euler定理所以首先将X对28取模，x=X%28是取模的结果，x就很小了(0x<28，有了这点，输入的X再大也没关系)，简单计算就可以得到r的值 解解题思路思路（（5 5））解解题思路思路（（6 6））•当X=10000时，计算200410000=220000*310000*16710000的所有因子和对29取模的结果 20001%28=9,10001%28=5,167%29=22.r=(29-1)(35-1)(225-1)%29=18*10*12%29=14S%29=r*9%29=14*9%29=10, 2004100000的所有因子和对29取模的结果是10 核心代核心代码及解及解释 （（1 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; //S=r/332,r的值•return r*9%29; //S%29=r*9%29•}核心代核心代码及解及解释 （（2 2））•int main(){•while(scanf("%d",&x),x)•printf("%d\n",mod29(x%28));•}案例案例3 3：：2 2x x mod n=1 mod n=1 •Time Limit: 1000ms• Special Time Limit:2500ms• Memory Limit:32768KB 描述描述 •给定一个整数n，求一个最小的整数x，使得2x mod n = 1 输入入 •每行一个正整数n,.(0  n  231-1) 输出出 •如果最小的正整数存在，输出一行2^x mod n = 1，其中的x和n用输入的n值和最小的x值代替；否则，输出一行2^? mod n = 1 输入入样例例 •2•5 输出出样例例•2^? mod 2 = 1•2^4 mod 5 = 1 解解题思路思路（（1 1））•本题首先想到的可能是暴力搜索，从x=1开始，逐步加大x，找到使得2^x mod n = 1的x就输出。

但考虑到n比较大，满足2^x mod n = 1的x可能也很大，所以直接求解的方法不行 解解题思路思路（（2 2））•Euler定理 解解题思路思路（（3 3））•x一定是phi(n)的因子 解解题步步骤 •1．  求解x=phi(n);•2．  找出phi(n)的所有素因子pi;•3．  让x=x/pi,直到2x mod n1或pi不能整除x.如果2x mod n1，x=x*pi;•4．  重复2；•x就是满足2^x mod n = 1最小的x 解解题思路思路（（4 4））•因为求phi(n)和找出phi(n)的所有素因子pi都需要知道在215546340内的所有素数，所以在问题求解前，先作预处理：利用筛法将所有小于46340的素数求出来 核心代核心代码及解及解释 （（1 1））•int prime[5000], no_prime; • //根据素数分布定律，小于46340的素数约5000个•sieve() • //采用筛法求所有小于46340的素数{short p[23170]; • //求所有小于46340的素数，因为大于2的偶数都不是素数，所以筛法只对应所有的大于1小于46340的奇数•//如果p[i]=1表示2*i+3是素数,否则p[i]=0表示2*i+3不是素数。

for(i=0;i<23170;++i)p[i]=1; • //初始化，假定所有奇数都是素数•for(i=0;i<106;++i) •//106=sqrt(46340)/2-3•if(p[i])for(k=(i<<1)+3,j=(k+1)*(i+1)-1;j<23170;j+=k)p[j]=0;for(prime[i=j=0]=2;i<23170;++i)if(p [i])prime[++j]=(i<<1)+3;nb_prime=j+1;} 核心代核心代码及解及解释 （（2 2））•int ttn(int i,int n){ //函数计算2i mod n=?__int64 t=2,r=1; //用64位长整型防止中间结果溢出,,while(i) {if(i&1)r=t*r%n;t=t*t%n;i>>=1;}return r;} 核心代核心代码及解及解释 （（3 3））•int phi(int n) { // 函数求phi(n)result=temp=n;k=sqrt(n);for(i=0;prime[i]<=k&&i1)r[j++]=temp; for(i=0;i