例题1

给出下列递归式：
<!–swig3–>
现在不要求你求解，要你证明：
<!–swig4–>
首先想到的就是数学归纳法，假设对于任意$k \le n$，都有${K_k} \ge k$，那么：
<!–swig7–>
如果$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$为例，下图就是每个人新的编号：

令
<!–swig31–>
所以他上一次的编号是
<!–swig32–>
因为
<!–swig33–>
所以上一次编号可以写为
<!–swig34–>

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

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

其中$k = \left\lfloor {\frac{ {N - n - 1}}{ {q - 1}}} \right\rfloor $

如果我们用$D = qn + 1 - N$替代$N$，将会进一步简化算法：
<!–swig38–>

算法伪代码如下：

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

其中$k = \left\lceil {\frac{q}{ {q - 1}}D} \right\rceil $

模的性质

定义与性质

模定义如下：
<!–swig40–>
特别的
<!–swig41–>

与此类似，定义一个与模类似的运算：
<!–swig42–>
形象理解如下图所示：

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

模有一些性质：
<!–swig47–>

应用

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

很容易想到，首先分给每个人$\left\lfloor {\frac{n}{m}} \right\rfloor $个东西，剩下$n\bmod m$件东西分给前$n\bmod m$个人，一人多一件就行。

概括起来就是，前$n\bmod m$个人，每人$\left\lceil {\frac{n}{m}} \right\rceil $件，剩下的人，每人$\left\lfloor {\frac{n}{m}} \right\rfloor $件。

那有没有办法统一表示呢？有的，每个人分到的件数为
<!–swig56–>

为什么呢？假设
<!–swig57–>
那么
<!–swig58–>
当$1 \le k \le r$时，
<!–swig60–>
当$r < k \le m$时，
<!–swig62–>

得证，因此可以得到如下等式：
<!–swig63–>

由$n = \left\lfloor {\frac{n}{2}} \right\rfloor + \left\lceil {\frac{n}{2}} \right\rceil $
可以进一步将其转换为下取整形式：
<!–swig65–>

令$n = \left\lfloor {mx} \right\rfloor $
我们得到了一个令人惊奇的等式：
<!–swig67–>

HDU3089

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

C++代码如下：

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

typedef long long LL;

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

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