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

原文链接：

具体数学-第8课 - WeiYang Bloggodweiyang.com

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

例题1

给出下列递归式：

现在不要求你求解，要你证明：

首先想到的就是数学归纳法，假设对于任意

，都有

，那么：

如果

，那么

。 如果

，那么

，这时不成立。

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

约瑟夫环新解

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

这里我们继续推广到一般情况，如果有

个人，每隔

个人踢掉一个人，最后剩下的是几号？

初始编号为

，现在考虑一种新的编号方式。

第一个人不会被踢掉，编号加

，变成

，然后第二个人编号变为

，直到第

个人，他被踢掉了。

然后第

个人编号继续加

，变成了

，依次下去。

考虑当前踢到的人编号为

，那么此时已经踢掉了

个人，所以接下去的人新的编号为

。

所以编号为

的人编号变成了

，其中

。

直到最后，可以发现活下来的人编号为

，问题是怎么根据这个编号推出他原来的编号？

以

，

为例，下图就是每个人新的编号：

令

所以他上一次的编号是

因为

所以上一次编号可以写为

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

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

其中

如果我们用

替代

，将会进一步简化算法：

算法伪代码如下：

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

其中

模的性质

定义与性质

模定义如下：

特别的

与此类似，定义一个与模类似的运算：

形象理解如下图所示：

圆的周长是

，一共走过的路长（红色+绿色部分）是

，所以

就是绿色部分，

就是一圈长度减去绿色部分。

模有一些性质：

应用

考虑如下问题，怎么平均分配

个东西给

个人？

很容易想到，首先分给每个人

个东西，剩下

件东西分给前

个人，一人多一件就行。

概括起来就是，前

个人，每人

件，剩下的人，每人

件。

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

为什么呢？假设

那么

当

时，

当

时，

得证，因此可以得到如下等式：

由

可以进一步将其转换为下取整形式：

令

我们得到了一个令人惊奇的等式：

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\n", J(n, q));
    }
    return 0;
}

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

的。