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

原文链接：

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

例题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;
}

      

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