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 每件事似乎都是真的..但我得到了一些价值的否定答案..由于这个问题,我无法找到正确的解决方案...... Plz帮助保持正确的地方Modulus

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

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过,但是这是几乎从来没有必要的.

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.