2013ACM单数论.ppt

ACM 数论 初等数论的概念 整除性和约数： 假设d和a是整数，d|a（读作d整除a），意味着存在某个整数k，有a=kd。 如果d|a，并且d≥0，则称d是a的约数。 每个整数a都可以被其平凡约数1和a整除，a的非平凡约数也称为a的因子。 初等数论的概念 素数和合数 对于某个整数a1，如果它仅有平凡约数1和a则称p是素数。否则p是合数。 可以证明素数有无限多个。 筛法求素数。 求素数方法 1）p[N]存储所有的素数，二重循环，用已经求出的不大于平方根的所有素数试除 for(i=2;in;++i) for(j=0;jm p[j]*p[j]=i;++j) 如果p[j]整除i，则i不是素数 如果都不能整除，则i是素数，添加到素数列表p[N];(m++) Eratosthenes筛法 2）给定一个范围（求这个范围内的素数），进行如下步骤： 0.从2开始，2是第一个素数。也是第一个新素数。取出2。 1.筛掉所有新素数的倍数。 2.留下来的数里面第一个（最小的）是新素数。取出这个新素数。 3.重复1和2直到没有数存在。 O(n)筛素数 void Init() { int i,j,q,n,cnt=0; memset(mark,0,sizeof(mark)); n=1000; for(i=2;i=n;i++) { if(mark[i]==0) { prime[cnt++]=i; } for(j=0;jcnt;j++) { if(prime[j]*in)break; mark[prime[j]*i]=prime[j]; if(mark[i]==prime[j]) { //printf(%d %d mark=%d\n,i,j,mark[i]); break; } } } } 内网B、C题 初等数论概念 除法定理，余数 除法定理：对任意整数a和任意正整数n，存在唯一的整数q和r，使得a=qn+r，其中0≤rn。 值q成为除法的商，值r=a(mod n)称为除法的余数。 初等数论的概念 公约数与最大公约数 d是a的约数并且也是b的约数，则d是a和b的公约数。 两个不同时为0的整数a和b的最大公约数表示为gcd(a, b)。 初等数论的概念 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。 初等数论的概念 互质数： 如果两个整数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)。 欧几里德算法： EUCLID(a, b) if b = 0 than return a else return EUCLID(b, a % b) 二进制最大公约数算法： 如果a和b都是都是偶数，那么gcd(a, b) = 2gcd(a/2, b/2)。 如果a是奇数，b是偶数，那么gcd(a, b) = gcd(a, b/2)。 如果a和b都是奇数，那么gcd(a, b) = ((a–b)/2, b)。 吉林大学模板 思考： 将两个整数的欧几里德算法推广到求m个整数的最大公约数。 （两种方法） Extended-Euclidean 算法 定理：对于不完全为0的非负整数a，b，gcd（a，b）表示a，b的最大公约数d，必然存在整数对x，y，使得gcd（a，b）=d=ax+by。 扩展欧几里德算法： 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) 扩展欧