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

模的性质

定义与性质

模定义如下：

特别的

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

形象理解如下图所示：

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

模有一些性质：

应用

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

很容易想到，首先分给每个人 个东西，剩下 件东西分给前 个人，一人多一件就行。

概括起来就是，前 个人，每人 件，剩下的人，每人 件。

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

为什么呢？假设

那么

当 时，

当 时，

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

由

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

令

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

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

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