蓝桥杯算法入门（Python） 课件 第7章数学

7.1模运算蓝桥杯算法入门数学概述2大学C组数学：素数、GCD、LCM、快速幂

[2-5]大学B组数学：排列组合、二项式定理、容斥原理、模意义下的逆元、矩阵运算、高斯消元；计算几何（基础计算和基本位置关系判定）、概率论、博弈论大学A组数学：生成函数、莫比乌斯反演、快速傅里叶变换红色：常考黑色：少见数学题是出题最多的题型之一和杂题（模拟）的题量差不多模运算一个数太大，无法直接输出，或者不需要直接输出，那么可以把它取模，缩小数值再输出。模运算：a除以m的余数

amodm=a%m0≤amodm≤m-1模运算的简单应用：例：m=10，就是取a的个位数例：m=2，若余数为0，a为偶数，否则a为奇数。3模运算的性质加：(a+b)modm=((amodm)+(bmodm))modm减：(a-b)modm=((amodm)-(bmodm))modm乘：(a*b)modm=((amodm)*(bmodm))modm但是，除法这样做是错的：

(a/b)modm=((amodm)/(bmodm))modm例： (100/50)mod20=2 (100mod20)/(50mod20)mod20=0

两者不相等。除法的取模，需要用到逆元4例题7.1：刷题统计【lanqiaoOJ2098】5问题描述：小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做a道题目，周六和周日每天做b道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于n题？输入：输入一行包含三个整数a,b和n.输出：输出一个整数代表天数。输入样例：

102099输出样例：8对于50%的评测用例，1≤a,b,n≤106；对于100%的评测用例，1≤a,b,n≤1018。6a,b,n=map(int,input().split())week=a*5+b*2#每周做题数量days=(n//week)*7#做n题需要的整周，对应天数k=n%week

#整周以外的剩余题数ifk<=a*5:

#剩余题数在周一到周五内

days+=k//a+(k%a!=0)else:#周六和周日

days+=5k-=a*5days+=k//b+(k%b!=0)print(days)设一共需要x周y天。先算出一周能做w题，然后算出做n题需要的整周数x，还有n-wx=k题需要在y天内做完计算出y天，题目的答案是7x+y。k用求余计算。题解例题7.2：倍数问题【lanqiaoOJ168】7问题描述：众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你n个数，希望你从这n个数中找到三个数，使得这三个数的和是k的倍数，且这个和最大。数据保证一定有解。输入：第一行包括2个正整数表示n和k。第二行n个正整数，代表给定的n个数。输出：输出一行一个整数代表所求的和。输入样例：

431234输出样例：9对于30%的数据，n≤100；对于60%的数据，n≤1000；对于100%的数据，1≤n≤105，1≤k≤103，n个数都不超过108。8（1）30%得分。枚举，每次选3个数求和，计算复杂度O(n3)，通过30%测试。（2）100%得分。取三个数a、b、c，要求a+b+c能整除k，也就是说： (a+b+c)%k=0分开求余，得： a%k+b%k+c%k=x，其中x=0,k,2kx不可能等于3k，因为a%k、b%k、c%k都小于k。把题目转化为：a%k有k种取值，b%k也有k种取值，而选定a、b之后，可以通过a、b、x、计算出c，所以只需要枚举a%k和b%k即可，计算复杂度O(k2)，能通过100%的测试。题解罗勇军7.2快速幂蓝桥杯算法入门快速幂例：n=109，求nn的最后一个数字

即使能直接算，也会超时。方案：（1）数字太大：取模操作。（2）计算量太大：用分治法计算、用快速幂加速。10方法1：分治容易想到一种很快的办法：先算a2，然后再算平方(a2)2，再继续平方((a2)2)2，...总共只需要算O(log2n)次，就得到了an。当n=1015时，log2n≈50，计算量极小。11deffastPow(a,n,m):ifn==0:return1ifn==1:returna%mt=fastPow(a,n//2,m)ifn%2==1:return(t*t)*a%melse:returnt*t%ma,n,m=map(int,input().split())print(str(a)+'^'+str(n)+'mod'+str(m)+'='+str(fastPow(a,n,m)))方法2：二进制倍增例如算a11分解：a11=a8+2+1=a8×a2×a1。

这里a8

、a2、a1是倍乘关系 an只有log(n)个幂如何把11分解为11=8+2+1？利用二进制。 1110=10112=23+21+20=8+2+1处理a的幂从低位往高位处理1011（右移一次，就把刚处理的低位移走了）1011，处理末尾的1：计算a。

res=a1011，处理第2个1：计算a2。res=res*a2=a1+21011，处理0：跳过a4。1011，处理1：计算a8。

res=res*a8=a1+2+812代码13deffastPow(a,n,m):ans=1whilen:ifn&1:ans*=aa=(a*a)%mn>>=1returnans%ma,n,m=map(int,input().split())print(str(a)+'^'+str(n)+'mod'+str(m)+'='+str(fastPow(a,n,m)))例题7.4：越狱https:///problem/P319714问题描述：监狱有n个房间，每个房间关押一个犯人，有m种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。答案对100,003取模。输入：输入只有一行两个整数，分别代表宗教数m和房间数n。1≤m≤108,1≤n≤1012。输出：输出一行一个整数代表答案。输入样例：

23输出样例：615简单组合数学：用总方案数减去不越狱的方案数，就是答案。（1）总方案数。一个房间可以有m种宗教，所以n个房间一共有mn种方案。（2）不越狱的方案数，就是任意两个相邻房间都不同的方案数。第1间有m种宗教；第2间不能和第1间相同，所以有m-1种；第3间还是有m-1种，因为它不能和第2间相同，但是可以和第1间相同；第4间、第5间、...、第n间也都是m-1种。所以不越狱的方案数一共是m(m-1)n-1。答案：mn-m(m-1)n-1，因为n很大，需要用快速幂计算。题解16deffastPow(a,n,m):ans=1whilen:ifn&1:ans*=aa=(a*a)%mn>>=1returnans%mm,n=map(int,input().split())mod=100003ans=fastPow(m,n,mod)-m*fastPow(m-1,n-1,mod)%modifans<0:ans+=mod#ans可能是负的，变为正数ans%=modprint(ans)罗勇军7.3素数蓝桥杯算法入门素数素数的判定素数筛质因数分解18小素数的判定

19defis_prime(n):ifn<=1:returnFalseforiinrange(2,int(math.sqrt(n))+1):ifn%i==0:returnFalsereturnTrue试除法：继续优化

例题7.6：选数

/problem/P103621问题描述：已知n个整数a1、a2、...、an，以及1个整数k(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3，4个整数分别为3、7、12、19时，可得全部的组合与它们的和为：3+7+12=223+7+19=297+12+19=383+12+19=34现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数:3+7+19=29。输入：第一行两个空格隔开的整数n,k(1≤n≤20，k<n)。第二行n个整数，分别为a1、a2、...、an，1≤ai≤5×106。输出：输出一个整数表示种类数。22n,k=map(int,input().split())a=list(map(int,input().split()))ans=0defis_prime(s):#判断s是否为素数

ifs<=1:returnFalseforiinrange(2,int(s**0.5)+1):ifs%i==0:returnFalsereturnTruedefdfs(cnt,sum,p):

#选了cnt个,和为sum;下一个从a[p]开始选

globalansifcnt==k:#已经选了k个

ifis_prime(sum):ans+=1returnforiinrange(p,n):dfs(cnt+1,sum+a[i],i+1)#继续选下一个，下一个在a[i]后面dfs(0,0,0)print(ans)一道简单的综合题：DFS+素数判定。先用DFS从n个数中任选k个，然后求和并判断是否为素数。从n个数中选k个，且这k个数没有顺序关系，这是组合问题。选数的思路是：（1）选第1个数，这个数可以是n个数中的任何一个，设选了ai。i从1到n遍历。（2）选第2个数，此时选位置i后面的数，因为这样做可以避免重复。例如样例的{3,7,12,19}，若当前的组合选了{3,12}，那么下一次只能选后面的19，不能回头选7，这样会重复，因为{3,7,12}这个组合在前面已经选过了。（3）按上述方法选其他数，直到满k个。题解素数筛：埃氏筛素数的筛选：给定n，求2~n内所有的素数。埃氏筛直接利用了素数的定义。对初始队列{2、3，4，5，6，7，8，9，10，11，12，13，...，n}，操作步骤：（1）输出最小素数2，筛掉2的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，...}（2）输出最小素数3，筛掉3的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，...}（3）输出最小素数5，筛掉5的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，...}继续以上步骤，直到队列为空。2324defE_sieve(n):k=0#统计素数个数

visit[0:n+1]=[False]*(n+1)#初始化

foriinrange(2,n+1):#从第一个素数2开始。可优化（1）

ifnotvisit[i]:k+=1prime[k]=i#i是素数，存储到prime[]中

forjinrange(2*i,n+1,i):#i的倍数都不是素数。可优化（2）

visit[j]=True#标记为非素数，筛掉

returnk#返回素数个数埃氏筛的计算复杂度：2的倍数被筛掉，计算n/2次；3的倍数被筛掉，计算n/3次；5的倍数被筛掉，n/5次......；总计算量等于n/2+n/3+n/5+n/7+n/11+…，约为O(nlog2log2n)。计算量很接近线性的O(n)，相当好。空间复杂度：代码用到了boolvisit[N+1]数组，当N=107时，约10M。由于埃氏筛只能用于处理约n=107的问题，10M空间是够用的。区间素数

素数筛：欧拉筛欧拉筛（SieveOfEuler）是线性筛，能在O(n)的线性时间里求得1～n内所有的质数。欧拉筛的原理：一个合数肯定有一个最小质因子；让每个合数只被它的最小质因子筛选一次，以达到不重复筛的目的。操作步骤：（1）逐一检查2～n的所有数。第一个检查的是2，它是第一个质数。（2）当检查到第i个数时，利用已经求得的质数去筛掉对应的合数x，而且是用x的最小质因子去筛。26质因数分解：试除法

27例题7.8：因数分解

https:///problem/B387128问题描述：每个正整数都可以分解成素数的乘积，例如：6=2×3，20=22×5。现在，给定一个正整数，请按要求输出它的因数分解式。输入：输入第一行，包含一个正整数N。2≤N≤1012。输出：输出一行，为的因数分解式。要求按质因数由小到大排列，乘号用星号*表示，且左右各空一格。当且仅当一个素数出现多次时，将它们合并为指数形式，用上箭头^表示，且左右不空格。29importmathn=int(input())foriinrange(2,int(math.sqrt(n))+1):cnt=0ifn%i==0:whilen%i==0:n//=icnt+=1ifcnt==1:print(i,end='')else:print(i,'^',cnt,sep='',end='')ifn>1:print('*',end='')ifn>1:print(n)罗勇军7.4

GCD和LCM蓝桥杯算法入门GCD、LCMGCD：最大公约数性质：gcd(a,b)=gcd(a,a+b)=gcd(a,k·a+b)gcd(ka,kb)=k·gcd(a,b)定义多个整数的最大公约数：gcd(a,b,c)=gcd(gcd(a,b),c)。若gcd(a,b)=d，则gcd(a/d,b/d)=1，即a/d与b/d互素gcd(a+cb,b)=gcd(a,b)31GCD跟闹矛盾的一对整数说，多找找共同点，你们会幸福的。库函数gcd()32frommathimport*print(gcd(45,9))#9print(gcd(0,42))#42print(gcd(42,0))#42print(gcd(0,0))#0print(gcd(20,15))#5print(gcd(-20,15))#5print(gcd(20,-15))#5print(gcd(-20,-15))#5print(gcd(234,456,6,9))#3

手写GCD：辗转相除法gcd(a,b)=gcd(b,amodb)拉梅定理：用欧几里得算法计算两个正整数的最大公约数，需要的除法次数不会超过两个整数中较小的那个十进制数的位数的5倍。推论：用欧几里得算法求gcd(a,b)，a>b，需要O((log2a)3)次位运算。33LCMa和b的最小公倍数lcm(a,b)，从算术基本定理推理得到。算术基本定理：任何大于1的正整数n都可以唯一分解为有限个素数的乘积：n=p1c1p2c2...pmcm设：a=p1c1p2c2...pmcm，b=p1f1p2f2...pmfmgcd(a,b)=p1min{c1,f1}p2min{c2,f2}...pmmin{cm,fm}lcm(a,b)=p1max{c1,f1}p2max{c2,f2}...pmmax{cm,fm}推出：gcd(a,b)*lcm(a,b)=a*b，即：

lcm(a,b)=a*b/gcd(a,b)=a/gcd(a,b)*b。34LCM跟一对恩爱整数说，你们的结合必定会诞生一个更强大的后代!裴蜀定理裴蜀定理（Bézout'slemma）：如果a与b均为整数，则有整数x和y使得ax+by=gcd(a,b)。推论：整数a与b互素当且仅当存在整数x和y，使得ax+by=1。35例题7.10：互质数的个数【lanqiaoOJ3522】36问题描述：给定a,b，求1≤x<ab中有多少个x与ab互质。由于答案可能很大，你只需要输出答案对998244353取模的结果。输入：输入一行包含两个整数a,b，用空格分隔。输出：输出一个整数表示答案。输入样例：25输出样例：16对于30%的评测用例，1≤ab

≤106；对于70%的评测用例，1≤a≤106，b

≤109；对于100%的评测用例，1≤a≤109，b

≤1018。37mod=998244353defgcd(a,b):returnaifb==0elsegcd(b,a%b)deffastPow(a,n):ans=1a%=modwhilen>0:ifn&1:ans=(ans*a)%moda=(a*a)%modn>>=1returnansa,b=map(int,input().split())mi=fastPow(a,b)ans=0foriinrange(1,m