1、 2002信息學(xué)冬令營 牛場圍欄解題報(bào)告 安徽 駱驥第4頁 共4頁牛場圍欄解題報(bào)告模型建立這是一道十分典型的數(shù)論題。稍做分析，不難將其抽象成如下的數(shù)學(xué)模型：N元一次多項(xiàng)式a1x1 + a2x2 + + anxn，已知其系數(shù)a1，a2，an，且ai與xi均為非負(fù)整數(shù) 為了簡便敘述，本文以下所討論的范圍均為非負(fù)整數(shù)。 為了簡便敘述，本文以下所討論的范圍均為非負(fù)整數(shù)。求該多項(xiàng)式所不能表示的最大的數(shù)Z，或指出所有數(shù)均可被表示亦或無法確定Z的最大值。初看上去，該多項(xiàng)式顯得很復(fù)雜，難以找出頭緒。因此，我們不妨先對(duì)較簡單的情況N=2進(jìn)行分析ax+by。引理1：若gcd (a,b) =1，|xy|0 (mod

2、 b)，則axay (mod b)證 明：如果結(jié)論不成立，則axay (mod b)， a | x - y |0 (mod b) gcd (a,b) = 1 | x - y |0 (mod b) 與題設(shè)矛盾 axay (mod b) 證畢。有了這個(gè)引理1，我們不難得到關(guān)于ax + by的如下結(jié)論：引理2：若gcd (a,b) = 1，則ax + by可表示大于ab的任何整數(shù)。證 明：不妨設(shè)a ab f (m mod a) k 0 任何大于ab的正整數(shù)均可被ax + by表示。證畢。根據(jù)引理2，如果a和b的最大公約數(shù)為1，則大于ab的所有整數(shù)都可以被ax + by表示，我們只要考察1, ab范圍

3、內(nèi)的整數(shù)即可。那么，如果a和b的最大公約數(shù)不為1，又會(huì)是怎樣一個(gè)情形呢？仔細(xì)分析，我們不難得到引理3。引理3：設(shè)t = gcd (a,b)，則ax + by可以表示大于lcm (a,b)的任何為t倍數(shù)的整數(shù)。證 明：不妨設(shè) a 1，則ax + by 不能表示的整數(shù)Z的最大值無法確定。通過上述分析，N = 2時(shí)的各種情況分析已經(jīng)初現(xiàn)端倪。對(duì)二元一次多項(xiàng)式ax + by：若a = 1 或 b = 1，則所有整數(shù)均可被表示；若gcd (a, b) 1，由推論1，ax+by不能表示的整數(shù)Z的最大值無法確定；否則gcd (a, b) = 1，根據(jù)引理2，只要考察1, ab內(nèi)的所有數(shù)，從中找出最大的無法被

4、表示的整數(shù)Z即可。這僅僅是N = 2時(shí)的簡單情況，若N 2呢？由于N = 2時(shí)，有引理3成立，我們不難做出如下類似的猜測和分析：定理*： 設(shè)t = gcd (a1, a2, , an) (n 1)則在有限的范圍內(nèi)必然存在整數(shù)M，a1x1 + a2x2 + + anxn可以表示所有大于M且為t倍數(shù)的整數(shù)。證 明：1）N = 2 時(shí)，由引理3，結(jié)論顯然是成立的；2）設(shè)N = k時(shí)結(jié)論成立，則N = k+1時(shí)結(jié)論亦成立：令t = gcd (a1, a2, , ak , ak+1)t = gcd (a1, a2, , ak)，根據(jù)假設(shè)N = k時(shí)結(jié)論成立，則有：a1x1 + a2x2 + +akxk

5、可表示大于M 的所有為t 倍數(shù)的整數(shù)。設(shè)P為大于M的質(zhì)數(shù)且gcd(P，ak+1) = 1，那么Pt可以被表示。對(duì)二元一次多項(xiàng)式Pt x+ ak+1x k+1， gcd (Pt, ak+1) = t，令M = lcm (Pt, ak+1)根據(jù)引理3，Pt x+ ak+1x k+1可以表示大于M的任何為t倍數(shù)的整數(shù)。 a1x1 + a2x2 + + ak+1xk+1可表示所有大于M且為t倍數(shù)的整數(shù)。 N = k+1時(shí)，結(jié)論成立。由(1)(2)得，定理*成立。證畢。同樣的，結(jié)合定理*與先前的推論1，我們不難得到另一個(gè)簡單的結(jié)論：推論2：若gcd (a1, a2, , an) 1，則a1x1 + a2

6、x2 + + anxn不能表示的正整數(shù)Z的最大值無法確定。至此，我們可以嘗試對(duì)一般情況下的N進(jìn)行分析，N元一次多項(xiàng)式a1x1 + a2x2 + + anxn：若ai = 1，則所有整數(shù)均可被表示；若gcd (a1, a2, , an) 1，由推論2，則a1x1 + a2x2 + + anxn不能表示的正整數(shù)Z的最大值無法確定；否則，gcd (a1, a2, , an) = 1，根據(jù)定理*，可以確定一個(gè)有限的區(qū)間：1,M，考察其中的所有數(shù)，找出不能被表示的最大整數(shù)Z。雖然M是存在的，但其值可能非常大，因此上述算法的效率無法保證。我們必須在先前分析的基礎(chǔ)上，另辟蹊徑。算法設(shè)計(jì)先前分析N = 2時(shí)，

7、我們將數(shù)按照余數(shù)分類，提出了“完全剩余系”的概念。不妨將這種分類思想應(yīng)用在算法設(shè)計(jì)上：將N元一次多項(xiàng)式a1x1 + a2x2 + + anxn可以表示的所有整數(shù)按照mod a1的余數(shù)分類，依次記作集合B0，B1，Ba1-1。顯然，如果M Bi，則M + a1Bi。換句話說，若M可以被表示，則所有大于M且mod a1與M同余的整數(shù)均可以被表示！因此，我們只要能求出每個(gè)集合Bi的最小元素MinBi就可以推算出最大的不能被表示的整數(shù)Z了。例如，a1 = 6，a2 = 7，a3 = 10，a4 = 11，按照mod 6的余數(shù)分類，可以得到：MinB0 = 6, MinB1 = 7, MinB2 = 1

8、4, MinB3 = 21, MinB4 = 10, MinB5 = 11。從MinBi中找出最大的數(shù)21，易知從21-a1= 15起，所有大于15的整數(shù)均可以被表示 由于21是 由于21是MinBi中最大的，所以21，20，19，18，17，16均可以被表示。而15與21 mod 6的余數(shù)相同，因此15無法被表示。那么，如何求MinBi的值呢？不妨將每個(gè)類看成一個(gè)點(diǎn)，構(gòu)造一個(gè)有向圖G(V,E,W)：Vs為虛擬的源點(diǎn)，有向邊(Vs, ai mod a1)的權(quán)值為ai 。Vi 表示mod a1=i的一類，有向邊(Vi, (i+aj) mod a1)的權(quán)值為aj 。S123054555S12305

9、4555不難證明，從Vs到Vi的最短路徑就相當(dāng)于MinBi的值。這樣一來，將數(shù)論問題轉(zhuǎn)化成圖的模型，運(yùn)行圖論的經(jīng)典算法即可解決。下面，讓我們對(duì)本題的解法做個(gè)大致的小結(jié)：N元一次多項(xiàng)式a1x1 + a2x2 + + anxn：ai = 1，則所有整數(shù)均可被表示，輸出 -1；gcd (a1, a2, , an) 1，由推論2，則a1x1 + a2x2 + + anxn不能表示的正整數(shù)Z的最大值無法確定，輸出 -1；gcd (a1, a2, , an) = 1，構(gòu)造相應(yīng)的有向圖G(V,E,W)，求從Vs到Vi的單源多匯最短路徑。從而得到MinBi，輸出MaxofMinBi a1。第1）步，線性查找，

10、時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(N)；第2）步，求N個(gè)數(shù)的最大公約數(shù)，時(shí)間復(fù)雜度為O(NlogN)，空間復(fù)雜度為O(N)；第3）步，求單源多匯最短路徑，由于邊可以臨時(shí)構(gòu)造，無須保存。所以，時(shí)間復(fù)雜度為O(a12)，空間復(fù)雜度為O(a1)。整體看來，該算法的時(shí)空復(fù)雜度都不高，完全可以在時(shí)限內(nèi)解決問題。額外的結(jié)論：盡管運(yùn)用上述算法可以完美的解決本題，然而，通過對(duì)上述算法的研究分析，我們不難得到以下兩個(gè)額外的結(jié)論 根據(jù)對(duì)最短路算法的分析，可以得到這兩個(gè)結(jié)論，限于篇幅，在這里就不贅述了。 根據(jù)對(duì)最短路算法的分析，可以得到這兩個(gè)結(jié)論，限于篇幅，在這里就不贅述了。結(jié)論1：設(shè)amax= maxofai，amin = minofai。那么，定理*中的M可以設(shè)定為：M = amaxamin。結(jié)論2：設(shè)a1與a2為ai中最大的兩個(gè)數(shù)。那么，定理*中的M可以設(shè)定為：M = a1a2。這兩個(gè)結(jié)論將M限制在可以接受的一個(gè)范圍內(nèi)。因此，我們還可以用動(dòng)態(tài)規(guī)劃考察1,M內(nèi)的所有數(shù)，求最大不能被表示的整數(shù)Z。時(shí)間復(fù)雜度為O(NM)，空間復(fù)雜度為O(M)。思考小結(jié)面對(duì)一個(gè)復(fù)雜的問題，無從入手時(shí)，不妨從簡單的情形或例子去分析。在解決牛場圍欄一題中，我們