NOIP基础数论.pptx

2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天1NOIP基础数论前言2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天2数论在OI中是一个很重要的分支数论在NOIP中的考察算法并不很多近年来NOIP中数论的出现率变高甚至出现了我以前认为NOIP不会涉及的期望所以说掌握一些数论知识还是很重要的数论在OI中主要包括数论定理和数论算法接下来我们就从最简单的取模讲起简单概念取模2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天3余数的概念想必大家都知道a对b取模得到的结果就是a除以b的余数记作a mod b例如24 mod 9=6为描述方便，以下均将mod写为%x y (%p)表示x与y对p取模的结果相等，又称同余基本性质取模2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天4关于取模的几个基本性质：x+a y+a (%p)x-a y-a (%p)x*a y*a (%p)(以上假设xy(%p)(a+b)%p=(a%p+b%p)%p(a-b)%p=(a%p b%p)%p(a-b)%p=(a-b+p)%pa*b%p=(a%p)*(b%p)%p有了以上性质，我们就可以边计算边取模简单概念最大公约数2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天5如果a%x=0，我们称x是a的约数(或因数)，也称a是x的倍数a与b的最大公约数，是指一个最大的整数x，使得x同时是a和b的约数我们将a与b的最大公约数记作gcd(a,b)例如：gcd(18,24)=6那如何求解最大公约数呢？欧几里得算法最大公约数2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天6欧几里得算法又称辗转相除法算法公式：有了这个公式，我们就可以轻松求解最大公约数了，时间复杂度为log级别欧几里得算法的证明最大公约数2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天7为什么gcd(a,b)=gcd(b,a%b)？设gcd(a,b)=d，a=md，b=nd则gcd(m,n)=1(也称m与n互质)a%b=所以gcd(b,a%b)=gcd(nd,m%n*d)=d*gcd(n,m%n)因此只要证gcd(n,m%n)=1欧几里得算法的证明最大公约数2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天8假设gcd(n,m%n)=q1设m=kn+r(0=r0且最小呢？我们假设已经得到ax+by=gcd(a,b)的一组解若求解ax+by=c：当c%gcd(a,b)0时，无解否则，令k=c/gcd(a,b)axk+byk=gcd(a,b)*k=c得到x=xk，y=yk算法扩展扩展欧几里得算法2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天14如果要求x非负且最小呢？我们假设已经得到ax+by=c的一组解令g=gcd(a,b)lcm(a,b)=a*b/gax+lcm(a,b)+by-lcm(a,b)=ca(x+b/g)+b(y-a/g)=c由此可得，x加上或减去任意倍数的b/gcd(a,b)后均有对应的y的解令t=b/gcd(a,b)，(x%t+t)%t就是x的最小非负解例题BZOJ1477青蛙的约会2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天15有一个环形棋盘，每个格子编号为1.n，有两只青蛙A和B，起始坐标分别为x,y，每一秒，A向后跳a格，B向后跳b格，求最早几秒后两青蛙相遇或永远不会相遇。n,x,y,a,b均在int范围内题解BZOJ1477青蛙的约会2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天16假设t秒后相遇，由题意得：x+at y+bt(%n)(a-b)t y-x(%n)(a-b)t+kn y-x然后就可以用exgcd求t的最小非负整数解了例题BZOJ2299HNOI2011向量2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天17给出一对数a,b，你可以任意使用(a,b)(a,-b)(-a,b)(-a,-b)(b,a)(b,-a)(-b,a)(-b,-a)这些向量，问是否能拼凑出一个向量(x,y)(每个向量可以多次使用)每个测试点有50000组询问简要题解BZOJ2299HNOI2011向量2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天18所有操作可以化简为以下几种：x或y+或-2ax或y+或-2bx+a,y+bx+b,y+a并且第3、4种操作最多用一次，可以枚举第3、4种操作的使用次数2an+2bm=x有解当且仅当x是gcd(2a,2b)的倍数2an+2bm=y有解当且仅当y是gcd(2a,2b)的倍数简单概念质数2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天19这个大家小学应该学过质数，又称素数，是指除1和本身外没有其他约数的正整数，例如2,3,5,7,11否则称为合数质数在数论中十分常见，有许多关于质数的美妙性质简单概念唯一分解定理2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天20唯一分解定理(也称基本算数定理)：任意一个正整数c，将其分解为若干质数的正整数次幂的乘积，该分解方法唯一形如：c=p1a1*p2a2*pnan，p1pn均为质数这个定理可以感性地理解一下算法介绍质因数分解2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天21将正整数c，化作c=p1a1*p2a2*pnan，(p1pn均为质数)的形式，这一过程叫做质因数分解质因数分解有显然的O(c)的做法，不再赘述，我们考虑更快的做法假如c有大于 的质因数，那么它仅有一个该类因数且次数为1证明？算法介绍质因数分解2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天22于是我们可以只枚举小于等于 的数并判定其是否为c的因数，若是则从中除去若结束后，c仍大于1，那么此时的c就是那个大于 的质因数。时间复杂度O()扩展质因数分解与gcd,lcm2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天23将两个正整数A,B质因数分解A=p1a1*p2a2*pnanB=p1b1*p2b2*pnbn那么：gcd(a,b)=p1min(a1,b1)*p2min(a2,b2)*pnmin(an,bn)lcm(a,b)=p1max(a1,b1)*p2max(a2,b2)*pnmax(an,bn)由于max(a,b)=a+b-min(a,b)所以易证明lcm(a,b)=a*b/gcd(a,b)扩展质因数分解与约数个数2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天24将正整数A质因数分解A=p1a1*p2a2*pnan那么A的约数个数为：(a1+1)*(a2+1)*(an+1)算法介绍质数的判定2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天25判断一个数n是否为质数，可以枚举每个小于n且大于0的数i，判断n是否为i的倍数，时间复杂度O(n)我们还有更快的方法n如果有一个约数d，那么n/d也为其约数，d和n/d中至少有一个小于等于因此只需枚举所有小于等于 的数字进行判定即可，时间复杂度算法介绍质数筛法2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天26如果我们想要求出n以内的所有质数，最简单的方法可以枚举每个数，判断是否为质数，时间复杂度为 ，太慢！对此我们有筛法常用的有两种：埃氏筛法，时间复杂度O(n log n)欧拉筛法，俗称线性筛法，时间复杂度O(n)算法介绍埃氏筛法2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天27将一个大小为n的数组a置为1，枚举n以内的每个数，将以其倍数为下标的位置置为0，最终a数组内为1的位置下标为质数，正确性由质数的定义可知时间复杂度的证明需要使用调和级数：算法介绍欧拉筛法2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天28观察埃氏筛法，其缺点在于一个位置可能被反复置0，浪费了时间在欧拉筛法中，对于每个合数c，使得它只被作为其最小质约数的倍数筛掉每个合数只被筛掉一次，复杂度O(n)一道原题NOIP2012同余方程2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天29给定正整数a,b，求ax 1(%b)的最小正整数解，保证有解a,b均在int范围内题解NOIP2012同余方程2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天30这道题其实并不难ax 1(%b)ax=1+byax-by=1典型的exgcd的形式，求x的最小正整数解由于保证有解，相当于保证了gcd(a,b)=1但是通过这道题可以引申出一些新的知识简单概念逆元2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天31对于正整数a,b，如果能找到正整数x使得ax 1(%b)，我们称x是a在模b意义下的逆元在这里，实际上a与x互为模b意义下的逆元由上一道题目可知，a在模b意义下存在逆元，当且仅当gcd(a,b)=1，即a与b互质逆元有什么用呢？算法介绍逆元2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天32众所周知，在取模的意义下是不能直接作除法的例如：12%11=1，(12/3)%11=4但是(1/3)%114但是，我们找到3在模11意义下的逆元4发现(12*4)%11=4逆元的作用：在模意义下，除以一个数，相当于乘上这个数的逆元这样我们就可以在模意义下作除法了！算法介绍费马小定理2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天33如何求解逆元呢？首先，我们可以通过exgcd进行求解，该方法适用于所有有解的情况但是当模数为质数时，有另一种方法费马小定理小定理：ap-1 1(%p),p为质数,a与p互质由此可得：a*ap-2 1(%p)所以，当模数为质数p时，a的逆元等于ap-2算法介绍快速幂2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天34你说你不会求ap-2？我们有O(log n)的快速幂！为了求解an，我们将指数n划分为若干2的次幂的和例如，求解a26，26=21+23+24=2+8+16所以a26=a2*a8*a16我们又发现a2=(a1)2,a4=(a2)2,a8=(a4)2我们就可以用log n的时间求出a,a2,a4,a8 接下来只需要将需要的a的次幂相乘，即可得到答案算法介绍快速幂2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天35那么哪些次幂是需要的呢？我们来观察指数的二进制例如，26的二进制为11010，从最低位起，0和1就分别表示了对应的次幂是否需要指数的二进制可以通过不断除2和模2来得到代码展示快速幂2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天36一道原题NOIP2013转圈游戏2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天37n 个小伙伴（编号从 0 到 n-1）围坐一圈玩游戏。按照顺时针方向给 n 个位置编号，从0 到 n-1。最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，依此类推。游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第 m+1 号位置，依此类推，第nm号位置上的小伙伴走到第 0 号位置，第n-m+1 号位置上的小伙伴走到第 1 号位置，第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。现在，一共进行了 10k轮，请问x号小伙伴最后走到了第几号位置。(n,m,k在int范围内)题解NOIP2013转圈游戏2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天38此题作为当年第一题，并不难位置为x的人，在一轮游戏后变为(x+m)%n在r轮游戏后，变为(x+m*r)%n题目要求进行10k轮游戏，那么位置就变为(x+m*10k)%n直接求解即可，10k用快速幂求解一道例题HNOI2008越狱2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天39监狱有连续编号为1.n的n个房间，每个房间关押一个犯人，有m种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱，答案对100003取模n，m在long long范围内例如：当n=3,m=2时，答案为6题解HNOI2008越狱2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天40计数题有一种技巧叫做取补集直接求可能发生越狱的方案数并不好求可能发生越狱的方案数=所有的方案数-不能发生越狱的方案数所有的方案数=mn不能发生越狱的方案数=m*(m-1)(n-1)Answer=mn-m*(m-1)(n-1)，快速幂即可简单概念排列与组合2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天41阶乘：n!=1*2*n（规定0!=1）排列：有n个不同的物品，从中选出m个排成一列，问形成的排列的方案数。对于第一个位置，我们有n种选择；第二个位置，有(n-1)种选择；第m个位置，有(n-m+1)种选择。Answer=n*(n-1)*(n-m+1)我们将其记作：简单概念排列与组合2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天42组合：有n个不同的物品，从中选出m个物品，不考虑顺序性，问方案数。我们考虑n个物品选出m个的排列，由于在组合中不考虑顺序性，所以每一种组合在排列中重复出现了m!次，所以只需要将排列数除以m!。我们将其记作：练习排列与组合2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天431、用1 2 3 4 5这五个数字，组成没有重复数字的三位数，且为偶数，共有多少个？2、2名老师和4名学生排成一排，老师不站在两端，方案数有多少种？3、5名同学排成一排，甲与乙必须相邻的方案数有多少种？扩展排列与组合2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天44关于组合，还有三个重要的性质：算法介绍排列与组合2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天45这个性质非常重要利用这条性质，我们可以在O(n2)的时间的递推出所有0=i=n,0=j=i的当j=0时，C=1一道原题NOIP2016组合数问题2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天46给定k,n,m，有t组询问，每次询问给出x,y，问0=i=x,0=j=min(i,y)中有多少组(i,j)使得是k的倍数保证x=n,y=mn,m=2000，t=10000题解NOIP2016组合数问题2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天47以下用Cij表示由于n,m=2000，所以我们可以在O(n2)的时间内递推出所有的Cij如果一个数a是k的倍数，那么a%k=0由于”+”与”%”可以混合运算，所以可以求出所有Cij%k询问有多少个Cij，是k的倍数，就是询问有多少个Cij%k=0题解NOIP2016组合数问题2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天48我们将Cij%k填入一个以00为左上角、nm为右下角的矩阵观察询问范围：0=i=x,0=ji时Cij无意义，那么写成0=j=y，这样每次询问的范围就是一个包含左上角的矩阵对Cij%k=0的数量作二维前缀和，就可以每次O(1)回答询问时间复杂度O(n2+t)一道原题NOIP2011计算系数2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天49给定一个多项式(ax+by)k，请求出多项式展开后xnym 项的系数，保证n+m=k答案对10007取模k=1000题解NOIP2011计算系数2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天50给定一个多项式(ax+by)k，请求出多项式展开后xnym 项的系数，保证n+m=k答案对10007取模k=1000该题涉及到二项式定理：题解NOIP2011计算系数2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天51具体证明可以用归纳法，也可以用数学方法理解一下回归到题目，(ax+by)k的xnym项的系数就是Ckn*an*bm由于k=1000，Ckn可以递推求得扩展排列与组合2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天52Cnm表示n个不同的物品选m个的方案数把n个相同的物品放入m个不同的盒子、且每个盒子非空的方案数？插板法。Cn-1m-1把n个相同的物品放入m个不同的盒子、且每个盒子可以为空的方案数？新添加m个物品，使得盒子为非空。Cn+m-1m-1扩展排列与组合2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天53在坐标系中，从(0,0)出发，每次向上或向右走一个单位长度，走到(m,n)的方案数？Cn+mn简单概念概率2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天54某个事件A发生的可能性的大小，称之为事件A的概率，记作P(A)假设某事的所有可能结果有n种，事件A涵盖其中的m种，那么P(A)=m/n例如投掷一枚骰子，点数小于3的概率为2/6=1/3简单概念概率2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天55如果两个事件A和B所涵盖的结果没有交集，那么P(A或B发生)=P(A)+P(B)还是掷骰子P(点数小于3或点数大于4)=2/6+2/6=2/3如果A和B所涵盖的结果有交集那么P(A或B发生)=P(A)+P(B)-P(A与B同时发生)P(点数小于3或点数为偶数)=2/6+3/6-1/6=2/3简单概念概率2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天56记事件B为“事件A不发生”那么P(A)+P(B)=1，即P(B)=1-P(A)P(点数不小于3)=1-2/6=2/3在两个互不干互不干扰的事中，事件A在其中一件事中，事件B在另外一件事中那么P(A与B同时发生)=P(A)*P(B)掷两个骰子，P(第一个点数小于3且第二个点数为偶数)=(2/6)*(3/6)=1/6简单概念期望2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天57事件A有多种结果，记其结果的大小为x，那么x的期望值表示事件A的结果的平均大小，记作E(x)E(x)=每种结果的大小与其概率的乘积的和例如，记掷一枚骰子的点数为xE(x)=1*(1/6)+2*(1/6)+3*(1/6)+4*(1/6)+5*(1/6)+6*(1/6)=7/2若c为常数，那么：E(x+c)=E(x)+c，E(c*x)=c*E(x)简单概念期望2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天58记两个事件的结果分别为x,yE(x+y)=E(x)+E(y)例如：E(语文成绩+数学成绩)=E(语文成绩)+E(数学成绩)若两个事件互相独立，E(x*y)=E(x)*E(y)E(语文成绩*数学成绩)=E(语文成绩)*E(数学成绩)例题BZOJ4318OSU!2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天59一个长度为n的01串按以下方式生成：第i个位置有ai的概率为1，(1-ai)的概率为0一个01串的价值如下计算：每一个极长全1子串的长度的三次方之和例如101101的价值为10求该01串的价值的期望n=100000题解BZOJ4318OSU!2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天60当一个全1子串长度从L变为L+1后，对价值贡献的增量为3L2+3L+1如果我们知道该01串末尾1的长度L的期望和L2的期望，那么我们就能知道以ai的概率添加一个1后对价值的期望贡献的增量只要再维护末尾1长度L的期望和L2的期望即可Li=ai*(Li-1+1)L2i=ai*(L2i-1+2*Li-1+1)fi=fi-1+ai*(3*L2i-1+3*Li-1+1)例题2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天61接下来一起看几道数论例题 例题巨大的斐波那契数2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天62定义斐波那契数f(i)：给定a,b，求f(ab)%1000a,b0且S尽量小，只需输出最小的S值即可n=100000，Ai2的情况，与n=2时的证明方法类似，此时有解当且仅当S是gcd(A1,A2,.,An)的倍数，因此Smin=gcd(A1,A2,.,An)时间复杂度O(n log 109)例题大质数2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天67给定L,R，求区间L,R内质数的个数L=R=1012，R-L=106题解大质数2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天68若x不为质数，那么x必然有一个小于等于x的因数x=1012 x=106也就是说，利用埃氏筛法，只需要用106以内的数就可以把L,R内的非质数筛除由于R-L=0,y=0)写在后面2018.2.28.基基础数数论 淄博淄博实验中学中学 唐梓天唐梓天70如果你将来要参加省选，参加NOI，那这些数论知识都只是最浅的一层但这些知识作为基础，一定要打好数论的练习主要依靠多总结套路，锻炼数学推导能力，甚至需要一些大胆的猜想，这在将来更深层次的数论学习中非常重要