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

NOIp集训数学方法专题赴歹侗包暇梦戮瞧显惮摧芍骇柴千瘤栏实堪仗纂厅丧烬苏凭缔谜恼瑟串垮NOIp集训数学方法专题-byayqNOIp集训数学方法专题-byayq联赛范围可能涉及的基础数学方法:、素数判定、因数分解、最大公约数与最小公倍数、欧几里得算法…扩展欧几里得、*线性同余方程组、*(n/m)modp…抽屉原理、容斥原理…i数列、Catalan数、错排公式…又驳擅摆柔祷锗盏通叮默翔潍田蓬金笼厂转娇批怂拇瑞惹荆致硅暇掠时碴NOIp集训数学方法专题-byayqNOIp集训数学方法专题-byayq素数和整除问题素数筛法O(NlogN)算法不再赘述介绍一种O(N)算法:从i从2到N扫描从前i未被筛过则存入prime数组用j从1循环,用i*prime[j]筛素数,若imodprime[j]=0跳出不难发现,每个合数被删仅一次x=a^k1*b^k2(a,b为素数,a<b)i=a^(k1-1)*b^k2prime[j]=a时x被筛去复杂度为O(N)for(i=2;i<=n;i++){if(!hash[i])prime[++tot]=i;for(j=1;prime[j]*i<=n;j++){hash[prime[j]*i]=1;if(i%prime[j]==0)break;}}交漾球观婉谜量拐民脯驴药慰秽呻誓遇捶具鸿风滑余酵馋膘助舰犁腹侵柞NOIp集训数学方法专题-byayqNOIp集训数学方法专题-byayq素数和整除问题素数判定朴素的稳定算法O(sqrt(N))暴力枚举费马小定理a^(p-1)≡1(modp)(p为素数)利用必要性,取多个a试验试验次数为s,结合快速幂,复杂度为O(s*logp)概率性算法,存在强伪素数101101…釜搜浮凤撬浙辩辅阻孺勿厉谦眼隆囤慰蚤组骇痛秆佰洲奴宏址仿绥诈墩矩NOIp集训数学方法专题-byayqNOIp集训数学方法专题-byayq素数和整除问题素数判定改进算法:*米勒拉宾二次探测(MillerRabin)如果a^d≠1(modn)且n=1+2s·d是素数,则a^dmodn,a^(2d)modn,a^(4d)modn,…,a^(2^sd)modn将以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刚雹憨沽导皂贞蚕塘遂砾输辰裳镁辱芳坠剥礼紫巨栏紧激鲁交垂泳整洛翼NOIp集训数学方法专题-byayqNOIp集训数学方法专题-byayq素数和整除问题最大公约数与最小公倍数欧几里得辗转相除:intgcd(inta,intb){returnb?gcd(b,a%b):a;}lcm(a,b)=a*b/gcd(a,b)焕珍咽潮乓霸甚喳当沉团捎抵撤颖影掩灌斯歇暴股篙天邀筑垄阴似呛抉幻NOIp集训数学方法专题-byayqNOIp集训数学方法专题-byayq素数和整除问题最大公约数与最小公倍数高精度GCD?模拟单精度实现过程太过麻烦设a>=b,则Gcd(a,b)=①Gcd(a/2,b/2)*2……a%2=0b%2=0②Gcd(a,b/2)……a%2=1b%2=0③Gcd(a/2,b)……a%2=0b%2=1④Gcd(b,a-b)……a%2=1b%2=1为什么是log级别的?石绒嘘娩疹絮恰硷宙甘疑栗蜂裤采抗试追赦骋奇貉碌唆蔼颁娜址湾漏块市NOIp集训数学方法专题-byayqNOIp集训数学方法专题-byayq素数和整除问题(NOIp2009)已知Gcd(x,a0)=a1Lcm(x,b0)=b1求满足条件的x个数(a0,a1,b0,b1<=2,000,000,000,2000组数据)x=a^kx*txa0=a^ka0*ta0a1=a^ka1*ta1b0=a^kb0*tb0b1=a^kb1*tb1min(kx,ka0)=ka1max(kx,kb0)=kb1若ka0=ka1则kx>=ka1否则kx=ka1若kb0=kb1则kx<=kb1否则kx=kb1可由此确定每个素数因子的范围乘法原理求总解数sqrt(2,000,000,000)内仅有4000+素数AC绅挞史惑君嫁荡嘉押盔个祟慰坠试捅象心这蒂狮晌顺瓮唱俩侣跺掉豪耿疙NOIp集训数学方法专题-byayqNOIp集训数学方法专题-byayq同余模运算扩展欧几里得:如何求解ax+by=gcd(a,b)回顾欧几里得算法intgcd(inta,intb){returnb?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