C++中负数取模问题

Question

我一直在编写一个计算以下递归关系的程序：

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

输出应为答案模 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);

当 MOD= 10^9 +7 时，一切看起来都是正确的...但我在某些值上得到了负数的答案...由于这个问题，我无法找到正确的解决方案...请帮忙确定在何处放置模数才是正确的。

- nitish712

---

你不应该使用 unsigned long long 类型来存储 sum 吗？ - Alex1985

@Alex1985 如果%运算符始终返回正值，那么它不会产生任何影响，但由于有时会给出负结果，因此应使用有符号变量。 - Brian L

@Hurkyl- 你是对的。评论已删除。 - Michael Anderson

ANSI C或ISO C是否规定-5％10应该是什么？负数的模运算，C和Ruby之间的模运算符（％）行为不同的原因是什么？ - phuclv

Answer 1

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

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

所以，如果你的整数除法向零舍入（这是自C99和C++11以来强制执行的规定），-5/4将为-1，我们有

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

为了得到一个正的结果（对于模运算），如果余数是负数，你需要加上除数或者做这样的操作：

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

- sellibitze

Answer 2

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

如果我们注释掉使用 % 或者另一行的话，我们得到：

• 使用 %：14秒

• 使用 ?：7秒

所以，我之前认为 % 是优化过的，但实际上不是。可能是因为这种优化会增加额外的开销。

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

相反，正如 这个答案 所建议和解释的那样，可以这样做：

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

如果你想让它对负数 n 也正常工作，那就需要做 更多的工作, 但这几乎从不必要。

- Evgeni Sergeev

Answer 3

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

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

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

- rasmus

Answer 4

目前所有在公式中有一次性加法的答案，在abs(a) > b时都是错误的。请使用以下或类似方法：

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

- G Huxley

Answer 5

正如其他人所说，% 只是一个余数运算符，而不是 mod。然而，模/余数操作通过像这样的递归关系正确地分配，因此如果您只是调整最终解决方案为正数，例如：

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

那么你应该得到正确的答案。这种方法的优点是，每个循环迭代引入的函数调用和/或分支少了一个。 （这可能取决于您的编译器有多聪明）。

- Michael Anderson

---

如果使用模数矩阵指数运算而不是直接使用递归关系（复杂度为O(N)），则可以在O(log(N))时间内解决此问题。 - Michael Anderson