ACM_数论——南开大学

《ACM_数论——南开大学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Butterfly0923Doraemonokjackfeng2008年南开大学ACM协会暑期集训数论二分法in乘方如何计算a^n？1）计算a*a*a*…*a*a*a，需要计算n-1次乘法，时间复杂度O(n)2）考虑实例a^4，计算b=a*a，再算c=b*b，则c=a^4，但是只用了两次乘法，效率提高。比如a^9=a*(a^4)*(a^4)，只需用4次乘法，一般的，a^n时间复杂度为O(logn)二分法in乘方第二种算法与二进制的关系9=(1001)2，a^9=a^8*a;10=(1010)2，a^10=a^8*a^2;从二进制最后一位开始，如果第k位

2、是1，就乘以a^(2^(k-1)),计算每个a^(2^k)需要logn，得到答案最多需要乘logn次，所以复杂度是O(logn)如果把a看作矩阵，上面方法可应用于矩阵乘方（注：这并不是最快的办法，有兴趣的同学可以做一下poj3134）求素数方法1）p[N]存储所有的素数，二重循环，用已经求出的不大于平方根的所有素数试除for(i=2;i

3、，从头开始遍历，如果b[i]==1，则i是素数，将所有的i的倍数j均修改为b[j]=0for(i=2;i

4、最优的了，但是如果只求某一个Fn，可以改进GCD（GreatCommonDivisor)Euclid算法intgcd(inta,intb){intmod;while(mod=a%b)a=b,b=mod;returnb;}//注意这里面必须a,b都为正数，否则要加其他判断语句Extended-Euclid算法:同时求出v,u使gcd(a,b)=u*a+v*b（重要）非递归的不好写，建议写递归的扩展欧几里得算法注意到对于gcd(a,b)=d我们对(a,b)用欧几里德辗转相除会最终得到(d,0)此时对于把a=d,b=0带入a*x+b*y=d，显然x=

5、1，y可以为任意值，这里y可以为任意值就意味着解会有无数个。我们可以用a=d,b=0的情况逆推出来任何gcd(a,b)=d满足a*x+b*y=d的解。如果x0,y0是b*x+(a%b)*y=d的解，那么对于a*x+b*y=d的解呢？扩展欧几里得算法b*x+(a%b)*y=d=>b*x+(a-[a/b]*b)*y=a*y+b*(x-[a/b]*y)，所以a*x+b*y=d的解x1=y0，y1=x0-[a/b]*y0;这样我们可以程序迭代了。注：a,b为正整数，设集合A={x*a+y*b

6、x,y是整数}，则A中最小正元素是gcd(a,b)费马小定理及其

7、推广若p为素数，gcd(a,p)=1则a^(p-1)=1(modp)推广：若gcd(a,n)=1则a^f(a)=1(modn)其中f(a)为a的欧拉函数，这里注意到，如果n为素数，则由于n的欧拉函数=n-1，可以推出费马小定理Extended-Euclid算法扩展欧几里德算法：EXTENDED-EUCLID(a,b)ifb=0thenreturn(a,1,0)(d’,x’,y’)←EXTENDED-EUCLID(b,a%b)(d,x,y)←(d’,y’,x’–(a/b)*y’)return(d,x,y)13求解模线性方程定理：方程ax=b(modn)对

8、于未知量x有解，当且仅当gcd(a,n)

9、b定理：方程ax=b(modn)或者对模n有d个不同的解，其中d=gcd(a,n)或者无解。14求解模线性方程定理：设d=gcd(a,n)，假定对整数x’和y’，有d=ax’+ny’。如果d

10、b，则方程ax=b(modn)有一个解的值为x0，满足x0=x’(b/d)modn。15求解模线性方程定理：假设方程ax=b(modn)有解（即有d

11、b，其中d=gcd(a,n)），x0是该方程的任意一个解，则该方程对模n恰有d个不同的解，分别为：xi=x0+i(n/d)(i=1,2,…,d-1)。16求解模线性方程MOD

12、ULAR-LINEAR_EQUATION_SOLVER(a,b,n)(d,x’,y’)←EXT