具体数学-第8课（取整进阶）

原文链接：

今天主要讲了取整与递归式的结合，还有取模的相关知识。

例题1

给出下列递归式：
$egin{array}{l}{K_0}{ m{ = }}1\{K_{n + 1}} = 1 + min (2{K_{leftlfloor {n/2} ight floor }},3{K_{leftlfloor {n/3} ight floor }}),n ge 0end{array}$
现在不要求你求解，要你证明：
${K_n} ge n$
首先想到的就是数学归纳法，假设对于任意 $k le n$ ，都有 ${K_k} ge k$ ，那么：
$egin{array}{l}{K_{n + 1}} = 1 + min (2{K_{leftlfloor {n/2} ight floor }},3{K_{leftlfloor {n/3} ight floor }})\ ge 1 + min (2leftlfloor {frac{n}{2}} ight floor ,3leftlfloor {frac{n}{3}} ight floor )end{array}$
如果 $n = 2k$ ，那么 ${K_{n + 1}} ge 1 + n$ 。
如果 $n = 2k + 1$ ，那么 ${K_{n + 1}} ge n$ ，这时不成立。

所以数学归纳法无法证明，今后我们会用其他方法来证明这个式子。

约瑟夫环新解

还记得约瑟夫环问题吗？详见第一节课。

这里我们继续推广到一般情况，如果有 $n$ 个人，每隔 $q$ 个人踢掉一个人，最后剩下的是几号？

初始编号为 $1 ldots n$ ，现在考虑一种新的编号方式。

第一个人不会被踢掉，编号加 $1$ ，变成 $n+1$ ，然后第二个人编号变为 $n+2$ ，直到第 $q$ 个人，他被踢掉了。

然后第 $q+1$ 个人编号继续加 $1$ ，变成了 $n+q$ ，依次下去。

考虑当前踢到的人编号为 $kq$ ，那么此时已经踢掉了 $k$ 个人，所以接下去的人新的编号为 $n + k(q - 1) + 1 ldots$ 。

所以编号为 $kq+d$ 的人编号变成了 $n + k(q - 1) + d$ ，其中 $1 le d < q$ 。

直到最后，可以发现活下来的人编号为 $qn$ ，问题是怎么根据这个编号推出他原来的编号？

以 $n=10$ ， $q=3$ 为例，下图就是每个人新的编号：

令
$N = n + k(q - 1) + d$
所以他上一次的编号是
$kq + d = kq + N - n - k(q - 1) = k + N - n$
因为
$k = frac{ {N - n - d}}{ {q - 1}} = leftlfloor {frac{ {N - n - 1}}{ {q - 1}}} ight floor$
所以上一次编号可以写为
$leftlfloor {frac{ {N - n - 1}}{ {q - 1}}} ight floor + N - n$

因此最后存活的人编号可以用如下的算法计算：

        N = qn
while N > n:
    N = k + N - n
ans = N

其中 $k = leftlfloor {frac{ {N - n - 1}}{ {q - 1}}} ight floor$

如果我们用 $D = qn + 1 - N$ 替代 $N$ ，将会进一步简化算法：
$egin{array}{l}D = qn + 1 - N\ = qn + 1 - left( {leftlfloor {frac{ {(qn + 1 - D) - n - 1}}{ {q - 1}}} ight floor + qn + 1 - D - n} ight)\ = n + D - leftlfloor {frac{ {(q - 1)n - D}}{ {q - 1}}} ight floor \ = D - leftlfloor {frac{ { - D}}{ {q - 1}}} ight floor \ = D + leftlceil {frac{D}{ {q - 1}}} ight ceil \ = leftlceil {frac{q}{ {q - 1}}D} ight ceil end{array}$

算法伪代码如下：

        D = 1
while D <= (q-1)n:
    D = k
ans = qn + 1 - D

其中 $k = leftlceil {frac{q}{ {q - 1}}D} ight ceil$

模的性质

定义与性质

模定义如下：
$xmod y = x - yleftlfloor {frac{x}{y}} ight floor$
特别的
$xmod 0 = x$

与此类似，定义一个与模类似的运算：
$x{ m{ mumble }}y = yleftlceil {frac{x}{y}} ight ceil - x$
形象理解如下图所示：

圆的周长是 $y$ ，一共走过的路长（红色+绿色部分）是 $x$ ，所以 $xmod y$ 就是绿色部分， $x{ m{ mumble }}y$ 就是一圈长度减去绿色部分。

模有一些性质：
$c(xmod y) = (cx)mod (cy)$

应用

考虑如下问题，怎么平均分配 $n$ 个东西给 $m$ 个人？

很容易想到，首先分给每个人 $leftlfloor {frac{n}{m}} ight floor$ 个东西，剩下 $nmod m$ 件东西分给前 $nmod m$ 个人，一人多一件就行。

概括起来就是，前 $nmod m$ 个人，每人 $leftlceil {frac{n}{m}} ight ceil$ 件，剩下的人，每人 $leftlfloor {frac{n}{m}} ight floor$ 件。

那有没有办法统一表示呢？有的，每个人分到的件数为
$leftlceil {frac{ {n - k + 1}}{m}} ight ceil ,1 le k le m$

为什么呢？假设
$n = qm + r,0 le r < m$
那么
$egin{array}{l}leftlceil {frac{ {n - k + 1}}{m}} ight ceil = leftlceil {frac{ {qm + r - k + 1}}{m}} ight ceil \ = q + leftlceil {frac{ {r - k + 1}}{m}} ight ceil end{array}$
当 $1 le k le r$ 时，
$leftlceil {frac{ {r - k + 1}}{m}} ight ceil = 1$
当 $r < k le m$ 时，
$leftlceil {frac{ {r - k + 1}}{m}} ight ceil = 0$

得证，因此可以得到如下等式：
$n = leftlceil {frac{n}{m}} ight ceil + leftlceil {frac{ {n - 1}}{m}} ight ceil + cdots + leftlceil {frac{ {n - m + 1}}{m}} ight ceil$

由 $n = leftlfloor {frac{n}{2}} ight floor + leftlceil {frac{n}{2}} ight ceil$
可以进一步将其转换为下取整形式：
$n = leftlfloor {frac{n}{m}} ight floor + leftlfloor {frac{ {n + 1}}{m}} ight floor + cdots + leftlfloor {frac{ {n + m - 1}}{m}} ight floor$

令 $n = leftlfloor {mx} ight floor$
我们得到了一个令人惊奇的等式：
$leftlfloor {mx} ight floor = leftlfloor x ight floor + leftlfloor {x + frac{1}{m}} ight floor + cdots + leftlfloor {x + frac{ {m - 1}}{m}} ight floor$

HDU3089

最后用今天介绍的约瑟夫环算法来解决一道经典的ACM题！题目链接：杭电3089。

C++代码如下：

        #include<bits/stdc++.h>
using namespace std;

typedef long long LL;

LL Ceil(LL x, LL y) {
    if (x % y == 0) return x / y;
    return x / y + 1;
}

LL J(LL n, LL q) {
    LL D = 1, end = (q - 1) * n;
    while (D <= end) {
        D = Ceil(q * D, q - 1);
    }
    return q * n + 1 - D;
}

int main() {
    LL n, q;
    while (~scanf("%lld%lld", &n, &q)) {
        printf("%lld
", J(n, q));
    }
    return 0;
}

比网上各种快速算法还要快哦，理论时间复杂度是 $log n$ 的。