第3章整值函數

（IntegerFunctions）鞠成東E-mail：juchd@M.P.：152046793362023/2/323.4‘MOD’:TheBinaryOperation

‘MOD’:二元運算2023/2/33MOD:二元運算在正整數m除正整數n時，商可以用取整符號表示為，而余數則記成“nmodm”：也就是可將“余數”的計算推廣到負整數，乃至任意實數上：因此mod是一個二元運算，其中后面的數稱為模數，前面的數至今尚沒有命名。2023/2/34MOD的直觀理解和例子當x、y為正實數時，如何直觀理解xmody的意義？假設有一個周長為y的圓，如果從某個點O開始在圓上繞著移動大小為x的距離，則結束點就是xmody。而且移動過程中掃過O的次數為。如何理解當x或y是負數時的xmody？先來看一些例子：2023/2/35負整數模下的MOD可以看到，如果模數y取不同的符號，xmody的符號也不相同，但是值均在0和模數y之間：若y=0怎么辦？有人提出，為保持連續性而定義：，可以證明：但是上面的定義實際用處不大。為保持完整性，CM中定義，也就是說xmody與x之差總為y的倍數。如何證明?2023/2/36實數模下的MOD如果將x分為整數部分和小數部分：，可以發現，小數部分能夠表示成xmod1，即

注意：mod的運算優先級比+/-高。能否對上取整函數定義類似mod的運算？G-K-P給出了一個mumble的名字：

看看mumble在圓周模型下的意義：在繞著圓周前進距離x后，為了再次到起始點還需要前進的距離。2023/2/37MOD的分配律分配律是mod運算的重要法則。對所有實數c、x和y有如果約定mod的優先級比乘法低，則右邊可以移去圓括號。分配律的正確性可由定義驗證：

容易驗證模數為零時也成立。2023/2/38均勻分組問題下面討論常遇到的實際問題：n個東西分到規模盡可能均等的m組。例如將n行文字排成m列，為整齊起見，列的長度依次遞減，任意兩列行數之差不超過1。例如37行排成5列，顯然右邊更美觀：2023/2/39分組問題的要求附加要求：按列優先的順序排列各行文字：先放第1列，再放第2列、第3列等等，才符合閱讀習慣。如果按行優先排列各行文字，能夠得到右邊的排列結果（每列的行數是正確的），但是各行文字的順序不對。（列1將包含行1、6、11、···、36而不是正確的行1、2、3、···、8。）如果n不是m的倍數，每個較長的列應該包含行，而每個較短的列應該包含行；較長的列有nmodm個，而較短的列有nmumblem個。2023/2/310分組問題的解決思路下面用“東西”和“組”來代替“行”和“列”，即可得到對一般化問題的解決方法。按照剛才的思路，首先，第1組應包含件東西。然后，接著要處理的問題就是把剩下的東西再“均勻地”分到m–1組里面。很好，我們很容易想到這帶有“遞歸”的色彩。因此后面的分配也同樣每次僅考慮剩下的“第1組”。重復下列過程：把余下的n’

=n

-個東西放入m’=m

-1個其他組中，直到m=0為止。2023/2/311分組問題的例子例如對n

=314和m

=6，我們得到的分配方案如下：顯然符合要求。也就是說，盡管模數一直在變，但是仍然取得了規模“平均”的分組方案。2023/2/312MOD分組方法的正確性分析假設n

=qm

+r，其中q

=，r

=nmodm。如果r

=0，先把q件東西放入第1組，再用n‘

=n

-q替換n，剩下的n’

=

qm‘件東西放入余下的m’

=m

–1組……此后的分配也是每次放入q個東西。結果正確。如果r>0，先把=q

+1件東西放入第1組，再用n’

=n

–q

–1替換n，剩下n’

=qm’+r–1件東西放入其余m’

=m

–1組。對n’和m’，可驗證新的余數為r’

=r

–1，但是q未變。依次分配，可得到包含q+1件東西的r個組，以及包含q個東西的m

–r個組。結果也正確。怎樣快速計算第k組中有多少件東西？

提示：按照k與r的大小關系分情況討論。2023/2/313MOD表示下的分組過程根據我們得到的在k上的直接計算公式，可以用下面的等式表示出將n劃分成以大小遞減、且基本上均勻的m個部分的過程：

事實上我們在前面已經遇到過m＝2的情形：2023/2/314遞增次序下的分組如果希望分組的規模是遞增的，也就是說小組在大組之前，可以用相同的方法完成，只是在第一組中放入件東西。相應地，可以得到相同形式的等式如下問題：如何證明下式成立？2023/2/315在實數上的推廣來看一個讓人驚訝的美妙等式。如果用替換前面的n，我們會得到一個關于所有實數x的等式：驚訝不？我們知道，實數的下取整是它的整數近似值，等式左邊只有一個近似值，卻恰好等于右邊好多個近似值之和。如果粗略地假設約為x

-1/2，則左邊約為mx

-1/2，右邊約為(x-1/2)+(x-1/2+1/m)+···+(x-1/2+(m-1)/m)，兩邊的粗略近似值恰好相等。2023/2/316在實數上的推廣之證明回憶前面學到的知識（？），我們可以移去下取整符號內部的下取整符號。這樣就證明了前面的等式：2023/2/3173.5Floor/CeilingSums

下取整/上取整的求和2023/2/318下取整/上取整的求和前一節已經看到，對涉及取整符號的求和，有時可以得到封閉形式解（當然，解有可能用取整符號表示）：本節將探討若干情形下、涉及取整的求和問題。對涉及取整符號的大多數求和問題，一般的計算技巧是引入新的變量，以此去掉取整符號，并將取整求和轉化為普通的求和問題。右側的求和問題有沒有封閉形式解？2023/2/319平方根取整求和：方法1直接從含有取整符號的式子無法入手，讓我們嘗試引入新的變量。方法1：首先引入變量，然后得到2023/2/320平方根取整求和：方法1兩個求和的分項都是依賴于n的。n的值決定了求和上下界，設有，此時第1個求和變為2023/2/321平方根取整求和：方法1對第2個求和項