模运算 - 竞赛编程

Question

我看到很多竞赛程序员在C++中使用((a + b) % d + d) % d编写代码。为什么他们不只是使用(a + b) % d呢？括号内的+d有何用处？它与负数有关吗？

谢谢

- ijkl26

---

"这与负数有关吗？" 你尝试过在两种方法中使用负数并比较得到的答案吗？ - Welbog

哦，现在我明白了。当我试图自己想出答案时，我不够专注，抱歉。非常感谢 :) - ijkl26

你确定它不是 ((a + b) % d + d) % d 吗？ - Mark Dickinson

不，就像我上次看到的那样，但可能是由于特定的问题输入限制。你的版本更通用，对吧？谢谢，我编辑了问题。 - ijkl26

Answer 1

是的，你说得对。在C++11之前，负数取模运算符%的行为是由实现决定的，但受到一些限制。将d添加到左操作数可以帮助解决这个问题，只要该操作数中的其他项总和大于或等于-d，但通常情况下并非如此。（对于负a的情况，-a / d倍的d可能是你特定情况下更好的加法常数。）

- Bathsheba

Answer 2

是的，它与负数有关。在某些条件下，它可以防止结果为负数。在这种情况下，当b变量为负时，b % d的结果也为负。这个结果永远不可能大于d，所以将d加到这个结果上可以强制使结果为正。

下面的代码是Java代码，但原理相同：

int a = 13;
int b = -23;
int d = 31;

int result1 = (a + b % d + d) % d;
int result2 = (a + b % d) % d;

System.out.println(result1);
System.out.println(result2);

它会输出以下内容：

21
-10

- MC Emperor

Answer 3

为了避免整数溢出并始终保持数字为正，我们使用模算术。竞技程序员倾向于在a为负数时使用(a+b)%b而不是a%b。

a%b = (a+b)%b
(a+b)%b = a%b + b%b = a%b + 0 = a%b

如果 a=-2 且 b=5，那么 a%b = 3

- Ishpreet