数论与组合数学计科0907班.ppt

数论与组合数学,计科0907班 何剑 Email:,主讲内容,数论 解模线性方程 解模线性方程组（中国剩余定理） 欧拉函数，欧拉定理 组合数学 鸽巢原理 全排列的生产 catalan数 polya计数,数论入门,解模线性方程： 求解方程 ax = b (%n) 其中a,b,n已知，求x 解法： 欧几里德方法求gcd： gcd(a,b) = gcd(b,a%b); /循环计算式,直到b=0. 扩展欧几里德： ax = b(%n) ax + ny = b 的整数解 设 d=gcd(a,n)，则方程等价为 ax + ny = b; (a = a/d ; n = n/d ; b = b/d;需要d | b,不整除无解 ）,如何解ax+ny = b?,ax+ny=b 的解是 ax+ny=1 的解的b倍 观察欧几里德循环过程： ax + ny = 1 与 gcd(a,n)=gcd(n,a % n); 方程 nx+(a % n)y=1 的解与ax+ny=1的解 是否可以通过某种变换使得x=f(x),y=g(y); 答案是显然的： y = x; x = x - a/n*y; 注意到a % n = a - a/n*n，自己演算一下就知道了,Ex_gcd(a,b,n),int ex_gcd(int a,int b,int ,模线性方程组,中国剩余定理： x = b0 (mod m0) x = b1 (mod m1) . x = bn-1 (mod mn-1) 当m0,m1,.mn-1两两互质时，方程有唯一解！解的范围在0T-1;T=m0*mn-1 如何解满足中国剩余定理的方程： 记Mi=M/mi(0=in),因为gcd(Mi,mi)=1,故有二整数pi,qi满足Mi*pi+mi*qi=1.如果记ei=Mi*pi. 那么有： ei = 0(mod mj, j!=i) 或 1(mod mj, j=i) 于是解就是:,素数相关问题,欧拉函数phi(x): phi(x)=y|y *定义为 a*b % (x). 也就是一个(mod x) 下的包含乘法的群。 欧拉定理:aphi(x) = 1 (%x) a属于整数集Z 由群论中的拉格朗日定理直接可得！ 拉格朗日定理： 有限群G中任意一个元素的阶o(a) | #G. o(a)定义为ao(a) % #G = a; 既a的周期 phi(x)怎么求： phi(x) = x * (1-1/fac0) * (1-1/faci) *.(1-1/facn-1) 简单来说就是每个x的质因子都删掉一部分数！,组合数学,N个人坐在跟自己编号不同的位置上，有多少种方法？ 12个不同颜色的珠子串成一条项链，能够做成多少个不同的项链？,什么是组合数学？,第一个问题是经典的错排问题，考虑第N个人 若前N-1个人已完全错排则有第N个人和前N-1个任意一个人换即可. 若前N-1个人未完全错排，其中有一个仍在自己位置上，则第N个人跟它换即可. 若有两个人未错排，则无论如何都无法完全错排所以可得 FN=(N-1)*(FN-1+FN-2),什么是组合数学？,第二个问题是一个圆排列。 珠子串成一条线的排列数：12！ 除去由旋转产生的重复排列：12！/12=11！ 除去由翻转产生的重复排列：11！/2,存在性问题-鸽巢原理,鸽巢原理是组合数学中最简单也是最基本的原理，也叫 Dirichlet抽屉原理。 即“若有n个鸽子巢，n+1个鸽子，则至少有一个巢内有至少有两个鸽子。”,鸽巢原理-编程例题,POJ2356 Find a multiple 题目大意：给出n个任意的整a1,a2.an，求一段连续和上s(i,j)=ai+a(i+1)+aj使得s(i,j)是n的整数倍。（N=10000),暴力枚举？,Si=a1+a2+.+ai; 暴力枚举i,j使得(sj-si) 能整除N？ 空间效率：O(N); 时间效率：O(N2);(n=10000). 太慢了！,思考,观察Si.恰好有个N个Si,又是N的倍数，联想到鸽巢原理！ 1)如果Si中存在一个数Sk为n的倍数，那么选前k个数即可 2)如果Si中不存在n的倍数，那么S1,S2,.Sn除以n所得的n个余数将分布在区间1,n-1中，那么必定存在i,j(ij)，使得Si mod n = Sjmod n，那么我们可以选择ai+1+ai+2+.+aj,程序代码,#include #include #define maxn 10001 int Amaxn; int Lmaxn; int main() int N,i,j,s=0; scanf(“%d“,if(Ls=0) printf(“%dn“,i-Ls); for(j=Ls+1; j=i; j+) printf(“%dn“,Aj); return 0; Ls=i; ,鸽巢原理加强形式,令q1,q2,.,qn为正整数。若将 q1+q2+qn-n+1 个物体放入n个盒子内，必有，或者第一个盒子至少有q1个物体，或者第二个盒子至少有q2个物体，或者第n个盒子至少有qn个物体。,证明,反证法：若n个盒子中任意一个盒子都小于qi个物体，则物体总数不超过： (q1-1)+(q2-1)+.+(qn-1)=q1+q2+qn-n; 该数比所分发物体总数少1，因此我们断言，对于某个盒子i，至少含有qi个物体。,数学应用,N2+1个人肩并肩地排成一条直线，总能选出n+1个人向前迈出一步，使得从左到右他们的身高是递增（或递减）的。,证明,问题抽象成数学模型：即从有n2+1个数的实数列ai中，选出一段子序列，使其单增（或单减）。 1.我们假设不存在长度为n+1的递增子序列，且令mk为以ak开头的最长子序列的长度。则有1=mk=n，既m1,m2,m(n2+1)是1到n之间的n2+1个整数，则必有： m(k1)=m(k2)=m(k(n+1) 其中1=k1k2.k(n+1)=n2+1,证明,又由于mk为以ak开头的最长子序列的长度，若akikj)则必有m(ki)=m(kj)+1与m(ki)=m(kj)相矛盾，因此有a(ki)a(kj)既 a(k1)=a(k2)=.=a(k(n+1)既a(ki)为一个递减子序列。 同理可得若无递减子序列则必有递增子序列,计算问题实例排列的生成,题目描述：给一个无重复项的数列pi按字典序输出pi的所有全排列。（字典序即从第1项到第n项逐个比较大小） 例如：123 132 213 312 321,计算问题字典序法生成全排列,问题简化：怎样从给定的序列生成下一个恰好字典序比其大的序列。 考察数列12354，发现末尾2项54是降序排列，则无论如何交换其中的项，只能使字典序变小。 得出结论：必然从末尾开始找到第一个pi,使得pip(i+1).既pi+1pn是最长降序。交换时必是pi与pi+1pn中某项交换 由于要使序列字典序尽可能小，则从pi右边的各项中找一个恰好比pi大的pj,又因末尾为降序，故从左至右找到第一个比pi大的pj即可。,计算问题字典序法生成全排列,由于此时pi+1pn仍满足降序，故将其逆转可得目标最小序列 例如12453逆转成12435，则12435即为由上一个排列12354生成的排列. 这样的规则可以保证生成的排列按照从小到大的顺序生成，所以从123n开始到n321结束即可生成全排列。,代码实现,#include main() FILE *fp; fp=fopen(“pailie.out“,“w“); int n,i,p100,k,j,k1,k2,l,t; long num=1; scanf(“%d“,代码实现,for(k=2;k=0 ,排列组合编程例题,POJ3421 X-factor Chains Given a positive integer X, an X-factor chain of length m is a sequence of integers, 1 = X0, X1, X2, , Xm = X Satisfying Xi Xi+1 and Xi | Xi+1 Find the maximum length of X-factor chains and the number of chains of such length,solution,可以考虑这样一个序列： X0, X1/X0, X2/X1, , Xm/ Xm-1 这个序列中所有元素都为X的因数，且所有元素的乘积为X。那么问题可以转换为寻找X所有的质因数及其个数，以及由所有质因数的构成排列的个数。 其中的组合问题即为前面的多重集合的排列计数。,特殊的计数序列-Catalan数,问题的提出：有2n个人排成一行进入剧场。入场费50美分。2n个人中的n个人有50分一个的分币，n个人有1美元的纸币，售票处刚开始没钱，有多少种列队方法使得售票处时刻都有钱找零。,特殊的计数序列-Catalan数,数学模型： n个+1和n个-1构成的2n项 a1,a2a2n 其部分和满足 a1+a2+ak = 0 (k=1,2,32n) 这种的数列有多少个？,特殊的计数序列-Catalan数,利用减法原理。数列的个数等于所有的排列个数减去不满足条件的排列个数。 其中，所有的排列个数：C(2n,n) 不满足条件的排列中，考虑最小的k，使得部分和a1+a2+ak 0, 则有：a1+a2+ak = -1 且ak=-1.,特殊的计数序列-Catalan数,此时，将前k项反号，即1-1,-1-1。那么整个序列中，有n+1个1，n-1个-1，一共有C(2n,n-1)种。这种排列和不满足条件的n个1和-1的排列是一一对应的。 那么满足条件的排列数：C(2n,n)-C(2n,n-1)= C(2n,n)/(n+1),Catalan数的一个应用,凸多边形的划分：将一个凸多边形通过其对角线的分割使其成为若干个三角形，问有多少种分法。,solution,确定一条基边