《ACM数论南开大学》由会员分享，可在线阅读，更多相关《ACM数论南开大学（22页珍藏版）》请在金锄头文库上搜索。
1、Butterfly0923Doraemonokjackfeng2008年南开大学ACM协会暑期集训数论二分法in乘方如何计算an ？1）计算a*a*a*a*a*a，需要计算n-1次乘法，时间复杂度O(n)2）考虑实例a4，计算b=a*a，再算c=b*b，则c=a4，但是只用了两次乘法，效率提高。比如a9=a*(a4)*(a4)，只需用4次乘法，一般的，an时间复杂度为O(logn)二分法in乘方第二种算法与二进制的关系9=(1001)2，a9=a8*a;10=(1010)2，a10=a8*a2;从二进制最后一位开始，如果第k位是1，就乘以a(2(k-1),计算每个a(2k)需要logn，得到答
2、案最多需要乘logn次，所以复杂度是O(logn)如果把a看作矩阵，上面方法可应用于矩阵乘方（注：这并不是最快的办法，有兴趣的同学可以做一下poj3134）求素数方法1）pN存储所有的素数，二重循环，用已经求出的不大于平方根的所有素数试除for(i=2;in;+i)for(j=0;jm & pj*pj=n;+j)如果pj整除i，则i不是素数如果都不能整除，则i是素数，添加到素数列表pN;素数2）增加布尔型数组bN记录是否为素数，初始化所有值=1，从头开始遍历，如果bi=1，则i是素数，将所有的i的倍数j均修改为bj=0for(i=2;in;+i)如果bi=1则添加到素数列表p，然后利用循环fo
3、r(j=i;jb*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|x,y是整数，则A中最小正元素是gcd(a,b)费马小定理及其推广若p为素数，gcd(a,p)=1则a(p-1)=1(mod p)推广：若gcd(a,n)=1则af(a)=1(mod n)其中f(a)为a的欧拉函数，这里注意到，如果n为素数，则由于n的欧拉函数=n-1，可以推出费马小定理Extended-Euclid 算法扩展欧几里德算法
4、：EXTENDED-EUCLID(a, b) if b = 0 then return (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(mod n)对于未知量x有解，当且仅当gcd(a, n)|b定理：方程ax=b(mod n)或者对模n有d个不同的解，其中d=gcd(a, n)或者无解。14求解模线性方程定理：设d=gcd(a, n)，假定对整数x和y，有d=ax+ny。如果d|b，则方程ax=b(modn)有一个解的值为x0，
5、满足x0=x(b/d)mod n。15求解模线性方程定理：假设方程ax=b(mod n)有解（即有d|b，其中d=gcd(a, n)），x0是该方程的任意一个解，则该方程对模n恰有d个不同的解，分别为：xi=x0+i(n/d)(i = 1, 2, , d-1)。16求解模线性方程MODULAR-LINEAR_EQUATION_SOLVER(a, b, n) (d,x,y) EXTENDED-EUCLID(a, n) if (d | b) then x0 x(b/d)mod n for i 0 to d-1 do print(x0 + i(n / d) mod n else print “no
6、solution”求解模线性方程组中国剩余定理的内容如下：令n=n1n2.nk，其中ni是两两互质的数，则对 0=an与0=aini且a=aimodni首先定义mi=n/ni(i=1,2.k)，则mi是除了ni以外的所有nj的乘积，由于GCD(mi,ni)=1，所以用扩展Euclid算法得ci满足bini+cimi=1a=a1c1m1+a2c2m2+.+akckmk(modn) LCM(Least Common Multiple)有了 GCD, LCM 就好办了LCM ( a, b ) = a * b / GCD ( a, b ) 实际上最好写成a/GCD(a,b)*b思考：为什么下面的写法好
7、？其他一些关于约数的公式若n=p1e1p2e2prer，则 n的因数个数为 (1+e1)*(1+e2)*(1+er) n所有因数的和为(1+p1+p12+p1e1)*(1+p2+p22+p2e2) *(1+pr+pr2+prer)n!n!=p1n1*p2n2*pknk勒让德定理：ni=n/pi+n/pi2+n/pi3+其中表示向下取整欧拉函数 (x)表示与x互质且小于x的正整数的个数如果x为素数，则欧拉函数等于x-1求法：将x分解为p1n1*p2n2*pknk，则欧拉函数=p1(n1-1)*pk(nk-1)*(p1-1)*(pk-1)ExerciseNKOJ:1053: 哥德巴赫猜想1236: ab1430: Fibonacci1249: 分解素因子1200: Euclids Game 1389: Divisors1214: Relatives 1379 C Looooooops1602 GossipingPOJ:1061:青蛙的约会2891:Strange Way to Express Integers
