软讯网络 > 软件时空 > 软件相关 > 最小正剩余
【标 题】：最小正剩余
【关键字】：
【来 源】：http://www.cublog.cn/u/20/showart.php?id=147763
最小正剩余
Z/(m) = {0,1,...,m-1}.其中 0, 1,..., m-1称为模 m 的最小非负剩余。最小非负剩余与带余除法有关。带余除法告诉我们，任意 m,n in Z，存在 q,r in Z 使得
n = mq + r, 其中 0<=r<|m|
我只关心 m>0 的情况，所以
n = mq + r, 其中 0<=r<m
q=[n/m]。按照数学上的传统记号，[x]表示不超过 x 的整数集中最大元，也就是计算机文献中常见的``向下取整''。
给定了 n,m 后，用 c 语言可以很容易地求出 q,r.
q = n/m
r = n%m
有时候，我们想用 1,2,...,m 作为 Z/(m) 的代表元，这组代表元称为最小正剩余。可以得到相应的带余除法：
n = mq'+r', 0<r<=m
当 n>＝m 时，
q' = [(n-1)/m]
r' = ((n-1) mod m) + 1
在 c 语言里，q', r' 可以表示为：
q' = (n-1)/m
r' = ((n-1) % m)+1
在以前的一个帖子里，我们讨论了 Josephus 问题。利用最小正剩余的表达式，可以得到一个相对清晰的公式：
记 Next 为 N，则
- N <= r，则
J(n, m) = qm + N - N > r
J(n,m) = (N-r-1)/(m-1) + N-r
这个实际上就是 yuxh 给出的公式，只是推导的方法略有不同。
【相关文章】
没有相关文章
|