提高班第四讲初等数论.ppt

初等数论题,Presented by 汪演增 -AchillesUSC,目录,1、素数 2、快速幂取模 3、唯一质因子分解定理 3、最大公约数（欧几里得算法） 4、扩展欧几里得算法 5、同余以及线性同余方程 6、特殊的线性同余方程组：中国剩余定理,素数,1、判断n是否为素数,for(int i=2;i*i=n;i+) if(n%i=0) flag=1;break;,2、如果要求106区间内的素数呢？,概念：除了1和此整数自身外，不能被其他自然数整除的数。,2）给定一个范围（求这个范围内的素数），进行如下步骤： 0.从2开始，2是第一个素数。也是第一个新素数。取出2。 1.筛掉所有新素数的倍数。 2.留下来的数里面第一个（最小的）是新素数。取出这个新素数。 3.重复1和2直到没有数存在。,Eratosthenes筛法,memset(flag,0,sizeof(flag); for(int i=2;i*i=1000000;i+) if(!flagi) for(int g =i;g=1000000;g+=i) flagg=1; ,快速幂取模,1、108怎么求？,3、10（108）%9999?,2、10180呢？,1.模取运算的性质 (1)(a+b)%c = (a%c)+(b%c)%c (2)(a*b)%c = (a%c)*b)%c,10._int64 fn(_int64 a,_int64 k) 11. 12. if(k=0)return 1; 13. if(k=1)return a%mod; 14. _int64 tmp1=fn(a,k/2); 15. _int64 tmp2=tmp1*tmp1%mod; 16. if(k 18.,(ak)%mod,快速幂（风格简洁）,_int64 quickmod(_int64 x, _int64 n) _int64 pw = 1; while (n 0) if (n ,质因子分解定理,唯一因子分解 唯一质因子分解定理：合数a仅能以一种方式，写成如下的乘积形式： a=p1e1p2e2prer 其中pi为素数，p1p2pr，且ei为正整数。,那么怎么求的一个合数n的所有素因子呢？,暴力法： 1、先求出每一个n的素因子，然后穷举,筛选法的妙用： 思路不明白没关系，看代码,for(int i=2;i*i=n;) if(n%i=0) couti“ “; while(n%i=0) n/=i; else i+; if(n!=1) coutnendl;,其他一些关于约数的公式,初等数论的概念,除法定理，余数 除法定理：对任意整数a和任意正整数n，存在唯一的整数q和r，使得a=qn+r，其中0rn。 值q成为除法的商，值r=a(mod n)称为除法的余数。,公约数与最大公约数 d是a的约数并且也是b的约数，则d是a和b的公约数。 两个不同时为0的整数a和b的最大公约数表示为gcd(a, b)。,互质数： 如果两个整数a与b只有公因数1，即如果gcd(a, b)=1，则a与b称为互质数（互素）。 定理：对任意整数a，b和p，如果gcd(a, p)=1且gcd(b, p)=1，则gcd(ab, p) = 1。,最大公约数 gcd（最大公因子）,Euclidean算法求两个正整数a和b的gcd。先令r0为a，r1为b，接着执行如下运算：,GCD递归定理：对任意非负整数a和任意正整数b，gcd(a, b) = gcd(b, a mod b)。,例：求8251和6105的最大公因数。,8251=61051+2146 6105=21462+1813 2146=18131+333 1813=3335+148 333=1482+37 148=374 最后除数37是148和37的最大公因数，也就是8251与6105的最大公因数。,欧几里德算法（辗转相除法）： int gcd(a,b) /return b?gcd(b,a%b):a; if(!b)return a; return gcd(b,a%b); ,LCM(Least Common Multiple),有了 GCD, LCM 就好办了 LCM ( a, b ) = a * b / GCD ( a, b ) 实际上最好写成a/GCD(a,b)*b 思考：为什么下面的写法好？,扩展欧几里得 算法,扩展欧几里得定理： 对于不完全为0的非负整数a，b，gcd（a，b）表示a，b的最大公约数d，必然存在整数对x，y，使得gcd（a，b）=d=ax+by。,扩展欧几里德算法是用来在已知a, b求解一组x，y使得ax+by = Gcd(a, b) =d,设 ab。 1、显然当 b=0时，gcd（a，b）=a。 此时 x=1，y=0； 2、ab！=0 时， 设 ax1+by1=gcd(a,b); bx2+(a mod b)y2=gcd(b,a mod b); 根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);,则:ax1+by1=bx2+(a mod b)y2; 即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2; 根据恒等定理得：x1=y2; y1=x2-(a/b)*y2; 这样我们就得到了求解 x1,y1 的方法： x1，y1 的值基于 x2，y2. 上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。,void extend_Eulid(int a,int b) int temp; if(b=0) x=1;y=0;q=a; /q是什么？ else extend_Eulid(b,a%b); temp=x; x=y; y=temp-a/b*y; ,扩展欧几里得典型例题：,POJ 1061 青蛙的约会,TIPS：抽象模型，建立方程就已成功了一半,根据题意，青蛙若想碰面的话，则必有(x+mt)-(y+nt)=p*L;(p为任意整数)。方程化为：(m-n)t-(y-x)=pL;则有(m-n)t-(y-x) mod L=0。即为：(m-n)t mod L=y-x 为线性同余方程。此方程有解当且仅当y-x能被m-n和L的最大公约数(记为gcd(m-n,L)整除,即gcd(m-n,L)|y-x有解。这时，如果x0是方程的一个解，即当t=x0时，(m-n)t mod L=y-x成立。,设d=gcd(m-n,L)，根据扩展欧几里得定理，则必存在整数对(r,s)使得(m-n)*r+L*s=d;则可得t=r*(y-x)/d。,scanf(“%I64d%I64d%I64d%I64d%I64d“, ,设m0，若mab，即abkm，则称a同余于b模m，记为 a、b关于模m同余的充要条件是整数a和b被同一正整数m除时，有相同的余数。,同余,同余的性质,例：求3406写成十进位数时的个位数.,根据题意是要求a满足3406 a（mod 10） 显然32 9 9（mod 10）， 34 1 （mod 10）， 从而3404 1 （mod 10）， 因此3406 3404 32 9（mod 10） 所以个位数是9.,这个可以用我们之前学的的方法做吗？,模的逆元,若m1，（a，m）1，则存在c使得 ca1（mod m） 我们把c称为是a对模m的逆，记为 a1（mod m）或a1,求解模线性方程,定理：方程ax=b(mod n)对于未知量x有解，当且仅当gcd(a, n)|b 定理：方程ax=b(mod n)或者对模n有d个不同的解，其中d=gcd(a, n)或者无解。,求解模线性方程,定理：假设方程ax=b(mod n)有解（即有d|b，其中d=gcd(a, n)），x0是该方程的任意一个解，则该方程对模n恰有d个不同的解，分别为：xi=x0+i(n/d)(i = 1, 2, , d-1)。,求解模线性方程,定理：设d=gcd(a, n)，假定对整数x和y，有d=ax+ny。如果d|b，则方程ax=b(modn)有一个解的值为x0，满足x0=x(b/d)mod n。,（中国剩余定理CRT）设m1,m2,.,mk是两两互素的正整数，即gcd(mi,mj) =1,ij,i,j = 1,2,.,k 则同余方程组： xb1 （mod m1） xb2 （mod m2） . xbk （mod mk) 模m1,m2,.,mk有唯一解，即在m1,m2,.,mk的意义下，存在唯一的x，满足： xbi mod m1,m2,.,mk