NOIp集训 数学方法专题 - by ayq.ppt

NOIp集训 数学方法 专题  联赛范围可能涉及的基础数学方法： 素数和整除问题 素数筛法 O(NlogN)算法不再赘述 介绍一种O(N)算法： 从i从2到N扫描 从前i未被筛过则存入prime数组 用j从1循环，用i*prime[j]筛素数，若i mod prime[j] = 0 跳出 素数和整除问题 素数判定 朴素的稳定算法O(sqrt(N))暴力枚举 费马小定理 a^(p-1)≡1 (mod p) ( p为素数 ) 利用必要性，取多个a试验 试验次数为s，结合快速幂，复杂度为O(s*logp) 概率性算法，存在强伪素数 101101… 素数和整除问题 素数判定 改进算法：*米勒拉宾二次探测(Miller Rabin) 如果a^d≠1(mod n)且n=1+2s·d是素数，则 a^d mod n，a^(2d)mod n，a^(4d)mod n,…,a^(2^sd)mod n 将以1结束,而且在头一个 1 的前边的值将是n –1 随机取样a 首先判断是否a^d%n==1 是-n为素数 否-不断将d平方，直到d=n-1，判断此过程中a^d%n=n-1是否出现 是-n为素数 否-n非素数 经检验a取2,7,61时效果非常好，10^8内未出现错误 特判n=a 素数和整除问题 最大公约数与最小公倍数 欧几里得辗转相除： int gcd(int a,int b) { return b?gcd(b,a%b):a; } lcm(a,b)=a*b/gcd(a,b) 素数和整除问题 最大公约数与最小公倍数 高精度GCD? 模拟单精度实现过程太过麻烦 设a=b，则 Gcd(a,b)= ①Gcd(a/2,b/2) *2 ……a%2=0 b%2=0 ②Gcd(a,b/2) ……a%2=1 b%2=0 ③Gcd(a/2,b) ……a%2=0 b%2=1 ④Gcd(b,a-b) ……a%2=1 b%2=1 为什么是log级别的？ 素数和整除问题 (NOIp 2009) 已知 Gcd(x,a0)=a1 Lcm(x,b0)=b1 求满足条件的x个数 (a0,a1,b0,b1=2,000,000,000，2000组数据) x = a^kx * tx a0= a^ka0 * ta0 a1= a^ka1 * ta1 b0= a^kb0 * tb0 b1= a^kb1 * tb1 min (kx,ka0)=ka1 max(kx,kb0)=kb1 若 ka0=ka1 则 kx=ka1 否则 kx=ka1 若 kb0=kb1 则 kx=kb1 否则 kx=kb1 可由此确定每个素数因子的范围 乘法原理求总解数 sqrt(2,000,000,000)内仅有4000+素数 同余模运算 扩展欧几里得： 如何求解 ax+by=gcd(a,b) 回顾欧几里得算法 int gcd(int a,int b) { return b?gcd(b,a%b):a; } 递归到底时 a=gcd(a,b)，b=0，令x=1，y=0，满足ax+by=gcd(a,b) a%b=a-a/b*b ax+by=c - bx’+(a-a/b*b)y’=c xa+yb=c - y’a+(x’-a/b*y’)b=c 回溯时令 x=y’ y=x’-a/b*y’ 同余模运算 求解 ax+by=c ? 判断c是否整除gcd(a,b)，整除则有解，反之无解 求解ax+by=gcd(a,b) 若ax+by=gcd(a,b)的解为(x’,y’) 则ax+by=c的解(x,y)=(c/gcd(a,b)*x’, c/gcd(a,b)*y’) 如何求出不定方程的所有整数解？ (x+k*b/gcd(a,b)，y-k*a/gcd(a,b))为所有合法解 其中k∈Z 同余模运算 *线性同余方程组 来看一个简单的情况，只有两个方程 x ≡ a1 ( mod m1 ) ① x ≡ a2 ( mod m2 ) ② ①等价于 x=a1+m1y1 ②等价于 x=a2+m2y2 联立得 a1+m1y1=a2+m2y2 不妨设a2=a1 用ex_gcd求解 m1y1-m2y2=a2-a1 若gcd(m1,m2)不整除a2-a1，则无解 解得最小的非负整数y1 令m3=lcm(m1,m2) a3=y1*m1+a1 这样我们便成功将这两个方程合并为 x ≡ a3 ( mod m3 ) 同余模运算 *思考 a=n%p，b=m%p，p为素数 已知a,b的值(n,m