C++ 中的负数模数

Modulus with negative numbers in C++

提问by nitish712

I have been writing a program for the following recurrence relation:

我一直在为以下递归关系编写程序：

An = 5An-1 - 2An-2  - An-3 + An-4

The output should be the Answer modulus 10^9 + 7.. I wrote a brute force approach for this one as follows...

输出应该是答案模数 10^9 + 7.. 我为这个写了一个蛮力方法如下......

long long int t1=5, t2=9, t3=11, t4=13, sum;
while(i--)
{
    sum=((5*t4) - 2*t3 - t2 +t1)%MOD;
    t1=t2;
    t2=t3;
    t3=t4;
    t4=sum;
}
printf("%lld\n", sum);

where MOD= 10^9 +7Every thing seems to be true.. but i am getting negative answer for some values.. and due to this problem, I am unable to find the correct solution... Plz help about the right place to keep the Modulus

其中，MOD= 10^9 +7每一件事情似乎是真的..但我得到否定的答案对一些价值观..而且由于这个问题，我无法找到正确的解决办法... PLZ有关的权利的地方有助于保持Modulus

回答by sellibitze

The thing is that the % operator isn't the "modulo operator" but the "division remainder" operator with the following equality

问题是 % 运算符不是“模运算符”，而是具有以下等式的“除法余数”运算符

(a/b)*b + a%b == a    (for b!=0)

So, if in case your integer division rounds towards zero (which is mandated since C99 and C++11, I think), -5/4 will be -1 and we have

因此，如果您的整数除法向零舍入（我认为自 C99 和 C++11 起强制要求），-5/4 将是 -1，我们有

(-5/4)*4 + -5%4 == -5
  -1  *4    -1  == -5

In order to get a positive result (for the modulo operation) you need to add the divisor in case the remainder was negative or do something like this:

为了获得正结果（对于模运算），您需要添加除数以防余数为负或执行以下操作：

long mod(long a, long b)
{ return (a%b+b)%b; }

回答by Evgeni Sergeev

Using %a second time in @sellibitze's and @liquidblueocean's answers probably won't be as slow as %tends to be in general, because it boils down to either one subtraction of bor none. Actually, let me just check that...

使用%在@ sellibitze的第二次和@ liquidblueocean的答案可能不会有够慢的%往往是一般，因为它归结为任何一个减法b或无。实际上，让我检查一下......

int main(int argc, char **argv) {
    int a = argc;    //Various tricks to prevent the
    int b = 7;       //compiler from optimising things out.
    int c[10];       //Using g++ 4.8.1
    for (int i = 0; i < 1000111000; ++i)
        c[a % b] = 3;
        //c[a < b ? a : a-b] = 3;
    return a;
}

Alternatively commenting the line with %or the other line, we get:

或者用%或另一行注释该行，我们得到：

• With %: 14 seconds

• With ?: 7 seconds

• 有%: 14 秒

• 与?: 7 秒

So %is not as optimised as I suspected. Probably because that optimisation would add overhead.

所以%并不像我怀疑的那样优化。可能是因为这种优化会增加开销。

Therefore, it's better to not use %twice, for performance reasons.

因此，%出于性能原因，最好不要使用两次。

Instead, as this answersuggests and explains, do this:

相反，正如此答案所建议和解释的那样，请执行以下操作：

int mod(int k, int n) {
    return ((k %= n) < 0) ? k+n : k;
}

It takes a bit more work if you want it to work properly for negative ntoo, but that's almost never necessary.

如果您也希望它对负数n也能正常工作，则需要做更多的工作，但这几乎从来没有必要。

回答by rasmus

Just replace %by a function that handles negative values:

只需替换%为处理负值的函数：

long long int mod(long long int a, long long int b) {
    long long int ret = a % b;
    if (ret < 0)
        ret += b;
    return ret;
}

EDIT: Changed the data type to long long int.

编辑：将数据类型更改为long long int.

回答by G Huxley

All answers currently here that have a once-off addition in their formula are wrong when abs(a) > b. Use this or similar:

当 abs(a) > b 时，目前这里所有在公式中一次性添加的答案都是错误的。使用这个或类似的：

int modulo (int a, int b) { return a >= 0 ? a % b : ( b - abs ( a%b ) ) % b; }

回答by Michael Anderson

As others have said %is just a remainder operator rather than mod. However, the mod/remainder operation distributes correctly through recurrence relations like this, so if you just adjust your final solution to be positive, like this,

正如其他人所说，%它只是一个余数运算符而不是mod. 然而，mod/remainder 操作通过像这样的递推关系正确分布，所以如果你只是调整你的最终解决方案为正，像这样，

if (sum < 0) { sum = sum + MOD; }

then you should get the right answer. The advantage of doing it this way is that you introduce one less function call and/or branch per loop iteration. (Which may or may not matter depending on how clever your compiler is).

那么你应该得到正确的答案。这样做的好处是每次循环迭代引入一个更少的函数调用和/或分支。（这可能重要也可能不重要，这取决于您的编译器有多聪明）。