24

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

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 每件事似乎都是真的..但是我对某些值得到了否定的答案..由于这个问题，我无法找到正确的解决方案...请帮助您找到正确的位置Modulus

4

5 回答 5

41

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

(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; }
于 2012-09-05T08:18:59.693 回答
11

在@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需要做更多的工作，但这几乎没有必要。

于 2014-04-22T08:22:07.893 回答
5

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

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.

于 2012-09-05T07:44:52.033 回答
3

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

int modulo (int a, int b) { return a >= 0 ? a % b : ( b - abs ( a%b ) ) % b; }
于 2014-01-31T00:17:53.133 回答
1

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

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

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

于 2012-09-05T08:33:45.303 回答