简单数论.pptxVIP

简单数论——李富数论简而言之,数论是研究整数的理论在ACM竞赛中,经常用到数论的相关知识纯数论的题目不多,大部分是和其他类型的问题结合起来的约数,倍数,模线性方程,欧拉定理,素数 内容1.初等数论的概念2.求素数的方法3.最大公约数4.欧拉函数5.模线性方程6.中国剩余定理7.唯一因子分解8.其他1.初等数论的概念整除性和约数：假设d和a是整数，d|a（读作d整除a），意味着存在某个整数k，有a=kd。如果d|a，并且d≥0，则称d是a的约数。每个整数a都可以被其平凡约数1和a整除，a的非平凡约数也称为a的因子。1.初等数论的概念素数和合数对于某个整数a1，如果它仅有平凡约数1和a则称p是素数。否则p是合数。可以证明素数有无限多个。筛法求素数。1.初等数论的概念除法定理余数除法定理：对任意整数a和任意正整数n，存在唯一的整数q和r，使得a=qn+r，其中0≤rn。值q成为除法的商，值r=a(mod n)称为除法的余数。1.初等数论的概念公约数与最大公约数d是a的约数并且也是b的约数，则d是a和b的公约数。两个不同时为0的整数a和b的最大公约数表示为gcd(a, b)。1.初等数论的概念互质数：如果两个整数a与b只有公因数1，即如果gcd(a, b)=1，则a与b称为互质数（互素）。定理：对任意整数a，b和p，如果gcd(a, p)=1且gcd(b, p)=1，则gcd(ab, p) = 12.求素数的方法试除法求1~n的所有素数p[N]存储所有的素数，二重循环，用已经求出的不大于平方根的所有素数试除for(i=2;in;++i)for(j=0;jm p[j]*p[j]=n;++j)如果p[j]整除i，则i不是素数如果都不能整除，则i是素数，添加到素数列表p[N];缺陷：时间复杂度太高2.求素数的方法筛法求1~n所有素数初始时容器内为2到n的所有数取出最小的数p,p一定是质数,删去p的所有倍数(注:只需从p2开始删除即可)重复上述步骤直到容器为空用bool数组实现即可缺陷:一个数可能被重复删去多次,影响效率3.最大公约数gcd(a, b) 的性质：定理：如果a，b是不全为0的任意整数，则gcd(a, b)是a与b的线性组合{ax+by:x,y∈Z}中的最小正元素。推论1：对于任意整数a，b，如果d|a并且d|b，则d|gcd(a, b)。推论2：对于所有整数a和b以及任意非负整数n，gcd(an, bn)=n*gcd(a,b)。推论3：对所有正整数n，a和b，如果n|ab并且gcd(a, n)=1，则n|b。3.最大公约数GCD递归定理：对任意非负整数a和任意正整数b，gcd(a, b) = gcd(b, a mod b)欧几里德算法：EUCLID(a, b) if b = 0 than return a else return EUCLID(b, a % b)3.最大公约数LCM(Least Common Multiple)LCM ( a, b ) = a * b / GCD ( a, b ) 实际上最好写成a/GCD(a,b)*b4.欧拉函数记φ(x)为与x互质且小于x的正整数个数4.欧拉函数求解单个n的phi(n)时，用试除法找出所有的质因数，然后再利用公式可以求解求解1-n的欧拉函数表时用类似筛法的方法例题一：Uva 11426题目大意：输入正整数n，求：gcd(1,2)+gcd(1,3)+……+gcd(n-1,n), 满足所有1=ij=n的gcd(i,j)的和输入格式：不超过100组数据，2=n=4 000 000例题一：Uva 11426简单解题思路：定义f[n]=gcd(1,n)+gcd(2,n)+gcd(3,n)+……+gcd(n-1,n)S[n]=f[1]+f[2]+f[3]+……+f[n]求f[n]: gcd(x,n)=d; g(n,i)表示以i为最大公因数的数的个数gcd(x/d,n/d)=1; g(n,i)=phi(n/i); f[n]=sum{phi(n/i)|i是n的约数} 优化：求f[n]时用筛法的思路，从对每个i枚举他的倍数n，更新f[n]4.模线性方程二元模线性方程(二元一次不定方程):形如ax≡c(mod b)或ax+by=c扩展欧几里德算法原理:令d=gcd(a,b),原方程有整数解当且仅当d|cbx+(a%b)y=d= ay+b(x-[a/b]*y)=d4.模线性方程算法步骤:整数a,b,c,设d=gcd(a,b)在用欧几里德算法求gcd(a,b)的过程中求方程ax+by=d的一组整数解:若b=0,则x=1,y=0;否则,递归调用gcd(b,a%b),可以得到bx+(a%b)y=d的解x,y,令x=y,y=x-[a/b]y即满足ax+by=d若d|c,设c=kd,则有a(kx)+b(