模运算的属性

Question

我有计算和S =(a*x + b*y + c)%N.是的,它看起来像一个二次方程但不是因为x和y有一些属性,必须使用一些递归关系计算.因为总和超过了无符号long long的限制,我想知道如何使用模运算的属性来计算总和,这些属性允许写入类似的总和(我说的是因为我不记得确切这些属性如何):( a*x)%N +(b*y)%N + c%N,因此避免超过无符号长long的限制.

提前感谢您的关注!:)

Answer 1

a % N = x意味着对于某些整数0 <= x < N和m:m * N + x = a.

你可以简单地推断,然后,如果a % N = x和b % N = y再

(a + b) % N =
= (m * N + x + l * N + y) % N =
= ((m + l) * N + x + y) % N =
= (x + y) % N =
= (a % N + b % N) % N.

我们知道 0 < x + y < 2N,这就是你需要保留余数计算的原因.这表明可以分割求和并分别计算余数然后加上它们,但不要忘记得到总和的余数.

对于乘法:

(a * b) % N =
= ((m * N + x) * (l * N + y)) % N =
= ((m * l + x * l + m * y) * N + x * y) % N =
= (x * y) % N =
= ((a % N) * (b % N)) % N.

因此,您也可以对产品进行相同的操作.

可以使用一些抽象代数(余数形成因子环Z/nZ)在更一般的设置中简单地导出这些属性.

Answer 2

如果需要,您可以进一步理解这个想法:

S = ( (a%N)*(x%N)+(b%N)*(y%N)+c%N )%N

Answer 3

您可以按照建议将模数应用于总和的每个项; 但即便如此,在总结它们之后,你必须再次应用模数来得到你的最终结果.

Answer 4

这个怎么样:

   int x = (7 + 7 + 7) % 10;

   int y = (7 % 10 + 7 % 10 + 7 % 10) % 10;