冬令营解题报告牛场围栏

1、 2002信息学冬令营 牛场围栏解题报告 安徽 骆骥第4页 共4页牛场围栏解题报告模型建立这是一道十分典型的数论题。稍做分析，不难将其抽象成如下的数学模型：N元一次多项式a1x1 + a2x2 + + anxn，已知其系数a1，a2，an，且ai与xi均为非负整数 为了简便叙述，本文以下所讨论的范围均为非负整数。 为了简便叙述，本文以下所讨论的范围均为非负整数。求该多项式所不能表示的最大的数Z，或指出所有数均可被表示亦或无法确定Z的最大值。初看上去，该多项式显得很复杂，难以找出头绪。因此，我们不妨先对较简单的情况N=2进行分析ax+by。引理1：若gcd (a,b) =1，|xy|0 (mod

2、 b)，则axay (mod b)证 明：如果结论不成立，则axay (mod b)， a | x - y |0 (mod b) gcd (a,b) = 1 | x - y |0 (mod b) 与题设矛盾 axay (mod b) 证毕。有了这个引理1，我们不难得到关于ax + by的如下结论：引理2：若gcd (a,b) = 1，则ax + by可表示大于ab的任何整数。证 明：不妨设a ab f (m mod a) k 0 任何大于ab的正整数均可被ax + by表示。证毕。根据引理2，如果a和b的最大公约数为1，则大于ab的所有整数都可以被ax + by表示，我们只要考察1, ab范围

3、内的整数即可。那么，如果a和b的最大公约数不为1，又会是怎样一个情形呢？仔细分析，我们不难得到引理3。引理3：设t = gcd (a,b)，则ax + by可以表示大于lcm (a,b)的任何为t倍数的整数。证 明：不妨设 a 1，则ax + by 不能表示的整数Z的最大值无法确定。通过上述分析，N = 2时的各种情况分析已经初现端倪。对二元一次多项式ax + by：若a = 1 或 b = 1，则所有整数均可被表示；若gcd (a, b) 1，由推论1，ax+by不能表示的整数Z的最大值无法确定；否则gcd (a, b) = 1，根据引理2，只要考察1, ab内的所有数，从中找出最大的无法被

4、表示的整数Z即可。这仅仅是N = 2时的简单情况，若N 2呢？由于N = 2时，有引理3成立，我们不难做出如下类似的猜测和分析：定理*： 设t = gcd (a1, a2, , an) (n 1)则在有限的范围内必然存在整数M，a1x1 + a2x2 + + anxn可以表示所有大于M且为t倍数的整数。证 明：1）N = 2 时，由引理3，结论显然是成立的；2）设N = k时结论成立，则N = k+1时结论亦成立：令t = gcd (a1, a2, , ak , ak+1)t = gcd (a1, a2, , ak)，根据假设N = k时结论成立，则有：a1x1 + a2x2 + +akxk

5、可表示大于M 的所有为t 倍数的整数。设P为大于M的质数且gcd(P，ak+1) = 1，那么Pt可以被表示。对二元一次多项式Pt x+ ak+1x k+1， gcd (Pt, ak+1) = t，令M = lcm (Pt, ak+1)根据引理3，Pt x+ ak+1x k+1可以表示大于M的任何为t倍数的整数。 a1x1 + a2x2 + + ak+1xk+1可表示所有大于M且为t倍数的整数。 N = k+1时，结论成立。由(1)(2)得，定理*成立。证毕。同样的，结合定理*与先前的推论1，我们不难得到另一个简单的结论：推论2：若gcd (a1, a2, , an) 1，则a1x1 + a2

6、x2 + + anxn不能表示的正整数Z的最大值无法确定。至此，我们可以尝试对一般情况下的N进行分析，N元一次多项式a1x1 + a2x2 + + anxn：若ai = 1，则所有整数均可被表示；若gcd (a1, a2, , an) 1，由推论2，则a1x1 + a2x2 + + anxn不能表示的正整数Z的最大值无法确定；否则，gcd (a1, a2, , an) = 1，根据定理*，可以确定一个有限的区间：1,M，考察其中的所有数，找出不能被表示的最大整数Z。虽然M是存在的，但其值可能非常大，因此上述算法的效率无法保证。我们必须在先前分析的基础上，另辟蹊径。算法设计先前分析N = 2时，

7、我们将数按照余数分类，提出了“完全剩余系”的概念。不妨将这种分类思想应用在算法设计上：将N元一次多项式a1x1 + a2x2 + + anxn可以表示的所有整数按照mod a1的余数分类，依次记作集合B0，B1，Ba1-1。显然，如果M Bi，则M + a1Bi。换句话说，若M可以被表示，则所有大于M且mod a1与M同余的整数均可以被表示！因此，我们只要能求出每个集合Bi的最小元素MinBi就可以推算出最大的不能被表示的整数Z了。例如，a1 = 6，a2 = 7，a3 = 10，a4 = 11，按照mod 6的余数分类，可以得到：MinB0 = 6, MinB1 = 7, MinB2 = 1

8、4, MinB3 = 21, MinB4 = 10, MinB5 = 11。从MinBi中找出最大的数21，易知从21-a1= 15起，所有大于15的整数均可以被表示 由于21是 由于21是MinBi中最大的，所以21，20，19，18，17，16均可以被表示。而15与21 mod 6的余数相同，因此15无法被表示。那么，如何求MinBi的值呢？不妨将每个类看成一个点，构造一个有向图G(V,E,W)：Vs为虚拟的源点，有向边(Vs, ai mod a1)的权值为ai 。Vi 表示mod a1=i的一类，有向边(Vi, (i+aj) mod a1)的权值为aj 。S123054555S12305

9、4555不难证明，从Vs到Vi的最短路径就相当于MinBi的值。这样一来，将数论问题转化成图的模型，运行图论的经典算法即可解决。下面，让我们对本题的解法做个大致的小结：N元一次多项式a1x1 + a2x2 + + anxn：ai = 1，则所有整数均可被表示，输出 -1；gcd (a1, a2, , an) 1，由推论2，则a1x1 + a2x2 + + anxn不能表示的正整数Z的最大值无法确定，输出 -1；gcd (a1, a2, , an) = 1，构造相应的有向图G(V,E,W)，求从Vs到Vi的单源多汇最短路径。从而得到MinBi，输出MaxofMinBi a1。第1）步，线性查找，

10、时间复杂度为O(N)，空间复杂度为O(N)；第2）步，求N个数的最大公约数，时间复杂度为O(NlogN)，空间复杂度为O(N)；第3）步，求单源多汇最短路径，由于边可以临时构造，无须保存。所以，时间复杂度为O(a12)，空间复杂度为O(a1)。整体看来，该算法的时空复杂度都不高，完全可以在时限内解决问题。额外的结论：尽管运用上述算法可以完美的解决本题，然而，通过对上述算法的研究分析，我们不难得到以下两个额外的结论 根据对最短路算法的分析，可以得到这两个结论，限于篇幅，在这里就不赘述了。 根据对最短路算法的分析，可以得到这两个结论，限于篇幅，在这里就不赘述了。结论1：设amax= maxofai，amin = minofai。那么，定理*中的M可以设定为：M = amaxamin。结论2：设a1与a2为ai中最大的两个数。那么，定理*中的M可以设定为：M = a1a2。这两个结论将M限制在可以接受的一个范围内。因此，我们还可以用动态规划考察1,M内的所有数，求最大不能被表示的整数Z。时间复杂度为O(NM)，空间复杂度为O(M)。思考小结面对一个复杂的问题，无从入手时，不妨从简单的情形或例子去分析。在解决牛场围栏一题中，我们