noip数论知识 朱全民.pptVIP

思考题13：圆桌问题 设 n 对夫妻围圆桌而坐，男女相间，每个男人都不和他的妻子相邻，有多少种可能的方案？ 分析 不妨设 n 个女人先围成一圈，方案数为( n－1 )! 。对任一这样的给定方案，顺时针给每个女人以编号1 , 2 , ··· , n。设第i号与第 i + 1号女人之间的位置为第 i 号位置，1≤ i ≤n－1。第 n 号女人与第1 号之间的位置为第 n 号位置。 设第 i 号女人的丈夫的编号也为第 i 号，1≤ i ≤ n。让 n 个男人坐到上述编号的 n 个位置上。设 ai是坐在第 i 号位置上的男人，则 ai ≠ i ，i + 1，１≤ i ≤n－1；an≠n，1。 分析 这样的限制也即要求在下面3行n列的排列中每列中都无相同元素。 １　２　３　 ···　 ···　n－１　n ２　３　４　 ···　 ···　n　　　1 a1　 a2 a3 ··· ··· an－1 an 满足这样的限制的排列 a1a2 ···an称为二重错排。 设二重错排的个数为Un，原问题所求的方案 数就是Un ( n－1)！。 分析 设Ai为 ai = i或 i+ 1 (1≤ i ≤n-1 )，an = n或1的排列 a1 a2 ··· an的集合。则 ｜Ai｜= 2 (n-1)! ，关键是计算 ∑ |∩Ai| 　 i∈I I ∈￠( n , k) 也就是从( 1 , 2 ) ( 2 , 3 ) ··· ( n-1, n ) ( n , 1)这n对数的k 对中各取一数，且互不相同的取法的计数。这相当于从1 , 2 , 2 , 3 ,3 ,4, ···,n-1, n-1, n , n , 1中取 k 个互不相邻数的组合的计数，但首尾的１不能同时取。 一般公式 回想无重复不相邻组合的计数： C’( n , r ) = C ( n- r + 1 , r ) ,这里所求的是： 思考题14：单色三角形 n点，无三点共线 每两点有红线或蓝线 有多少个三角形的三边同色？ 非单色三角形：两个顶点连接两个不同色线 第i个点连出红线ri条，则蓝线有n-1-ri条 非单色三角形有sum{ri(n-1-ri)}/2 单色呢？ * * Input 输入只包括一行5个整数x，y，m，n，L，其中x≠y 2000000000，0 m、n 2000000000，0 L 2100000000。 Output 输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行Impossible“ Sample Input 1 2 3 4 5 Sample Output 4 解题思路 此题其实就是扩展欧几里德算法－求解不定方程，线性同余方程。 　　设过s步后两青蛙相遇，则必满足以下等式： 　　　　(x+m*s)-(y+n*s)=k*l(k=0,1,2....) 　　稍微变一下形得： 　　　　(n-m)*s+k*l=x-y ??? 令n-m=a,k=b,x-y=c,即 　　　　a*s+b*l=c 只要上式存在整数解，则两青蛙能相遇，否则不能。 解题思路 求a * x + b * y = n的整数解。 　1、先计算Gcd(a,b)，若n不能被Gcd(a,b)整除，则方程无整数解；否则，在方程两边同时除以Gcd(a,b)，得到新的不定方程a * x + b * y = n，此时Gcd(a,b)=1; ???2、利用上面所说的欧几里德算法求出方程a * x + b * y = 1的一组整数解x0,y0，则n * x0,n * y0是方程a * x + b * y = n的一组整数解； 　3、根据数论中的相关定理，可得方程a * x + b * y = n的所有整数解为： ??????? x = n * x0 + b * t y = n * y0 - a * t (t为整数) 上面的解也就是a * x + b * y = n 的全部整数解。 解题思路 此时方程的所有解为：x=c*k1-b*t。 x的最小的可能值是0 令x=0，可求出当x最小时的t的取值，但由于x=0是可能的最小取值，实际上可能x根本取不到0，那么由计算机的取整除法可知：由 t=c*k1/b算出的t，代回x=c*k1-b*t中。 求出的x可能会小于0，此时令t=t+1，求出的x必大于0；如果代回后x仍是大于等于0的，那么不需要再做修正。 中国剩余定理 若有一些两两互质的整数m1, m2,… mn，则对任意的整数：a1,a2,...an，以下联立同余方程组对模数m1, m2,… mn 有公解： 公元5－6世纪前后的《孙子算经》中有“物不知数”问题：“今有物不知其数，三三数之余二 ，五五数之余三 ，七七数之余二，问物几何