如何在仅支持加法、乘法、比较与相等性操作的非零自然数类中实现模运算

首先得明确在这个不含0的自然数集里，我们的模运算规则要贴合约束：

• 若a < b，a % b = a（没法用b的正整数倍去“缩减”a，且余数必须是自然数）
• 若a == b，按照你提到的建议直接返回a本身
• 若a > b，我们要找到最大的k*b（k为自然数）使得k*b < a，再找到唯一的r < b满足k*b + r = a，这个r就是模运算的结果

具体实现 #

我们完全依赖Natural类提供的加法、比较、相等判断来实现，替换__mod__方法即可：

def __mod__(self, other):
    """
    Implement mod on Naturals without subtraction or division.
    @param other Natural the divisor (must be a Natural)
    """
    assert isinstance(other, Natural), "other must be a Natural"
    
    # 情况1：a小于b，余数就是a本身
    if self < other:
        return self
    
    # 情况2：a等于b，按建议返回原数值
    if self == other:
        return self
    
    # 情况3：a大于b，先找到小于a的最大b的倍数
    current_kb = other  # 从k=1开始，即1*b
    while True:
        next_kb = current_kb + other  # 计算(k+1)*b
        if next_kb == self:
            # a是b的整倍数，按规则返回a
            return self
        if next_kb < self:
            current_kb = next_kb
        else:
            # 现在current_kb < a < next_kb，反向找r使得current_kb + r = a
            r = Natural(1)
            while current_kb + r != self:
                r = r + Natural(1)
            return r

逻辑拆解 #

1. 小值判断：当a比b小时，直接返回a，比如3%5=3，完全符合模运算的直觉。
2. 相等判断：严格遵循你提到的评论建议，自然数对自身取模返回原数值。
3. 逼近最大倍数：通过不断累加b来靠近a，直到再累加一次就超过a，此时得到的current_kb就是小于a的最大b的倍数。
4. 反推余数：因为current_kb < a < current_kb + b，我们从1开始累加，直到current_kb + r等于a，这个r必然小于b，且是符合要求的自然数余数。

测试验证 #

运行你的测试代码：

if __name__ == "__main__":
    print(Natural(7) % Natural(2))  # 输出1，符合预期
    print(Natural(4) % Natural(2))  # 输出4，符合整倍数规则
    print(Natural(3) % Natural(5))  # 输出3
    print(Natural(5) % Natural(5))  # 输出5

内容的提问来源于stack exchange，提问作者Jasper