2

我在SRM 573 的解决方案中看到了这个功能：

long modPow(long x, long y)
{
    //Caculates x raised to the y-power modulo MOD
    //in O(log(y)) time by using  repeated squaring
    long r = 1;
    while(y > 0){
        if( (y&1) != 0) {
            r = (r * x) % MOD;
        }
        x = (x * x)%MOD;
        y >>= 1;
    }
    return r;
}

但是我对这个函数感到困惑，无法计算 ; 的模值x^y%MOD。
为什么x = (x * x)%MOD;需要在函数中？
这对我来说没有意义。

4

4 回答 4

1

tl; dr：这是一种优化。

假设 x 为 2，MOD 为 3。请注意，x 的唯一用途是将 r 乘以 x。

现在想象我们平方 x。x*x = 4。现在，r*4 % 3 将等于 1, 2, 3, 4, 5... 因为 r = 1, 2, 3, 4, 5... 哦！这与 x 为 1 相同。事实上，如果将 x 设置为 x*x %3 而不仅仅是 x*x，您将得到相同的结果。

但是下一步呢？4*4 = 16, %3 = 1. 1*1 = 1, %3 also = 1. 因此，无论我们是否提前或延迟或从不修改操作，我们都会陷入相同的残差。

于 2013-03-27T02:32:17.597 回答
1
于 2013-03-27T03:34:53.037 回答
0

暂时忘掉模部分，问问自己，“我怎样才能有效地计算 na 正整数的 x^n？” 您可以通过一次乘法计算 x^2：x * x。您可以通过两次乘法计算 x^3：x^3 = x * x^2。您可以通过两次乘法计算 x^4：x^4 = x^2^2 = x^2 * x^2。你可以用这个递归来计算 x^n：

For even n = 2*m, x^n = (x^2)^m.

For odd n = 2*m + 1, x^n = x * (x^m)^2.

所以，我们得到 x^10 为：

x^10 = (x^2)^5
     = x^2 * (x^4)*2

计算 x^2、x^4、x^8、x^10，进行 4 次乘法运算。

请注意，这是一个很好的通用方法，但不能保证它是最有效的。例如，试试 x^15。这个方法给你 x * (x^2)^7 = x * x^2 * (x^2)^6 = x * x^2 ^ (x^4)^3 = x ^ x^2 * x^ 4 * (x^4)^2。您计算 x^2、x^4、x^8，然后是 x * x^2 * x^4 * x^8，进行 6 次乘法运算。更快的是

y = x^3 = x * x^2, 2 multiplications.
x^15 = y^5 = y * (y^2)^2, 3 more multiplications,
This is a total of 5 multiplications.

实际上，对于指数 n，将加法链定义为从 1 开始到 n 结束的数字序列，其中列表中的每个数字是序列中前两个数字的总和（您可以重复）。

15 的算法给出

1、2、3、6、7、14、15。

较短的是

1、2、3、6、12、15。

事实证明，要找到以目标数字结尾的最短加法链在计算上是很困难的。

于 2013-03-27T04:22:12.007 回答
0

详细说明@jwpat7 的答案，让我们想想为什么

(x % MOD)*(x % MOD) ≡ (x*x) % MOD.

我们总是可以写x为x = n*MOD + r一些自然n和rwith r < MOD（如果这也x < MOD暗示x = rand n = 0）。

现在，我们总是得到x % MOD = (n*MOD + r) % MOD = r，因此我们得到

(x % MOD)*(x % MOD) = r * r.

另一方面，考虑(x*x) % MOD评估结果：

x*x = (n*MOD + r)*(n*MOD +r) = n*n*MOD*MOD + 2*n*r*MOD + r*r，因此我们得到(x*x) % MOD = (n*n*MOD*MOD + 2*n*r*MOD + r*r) % MOD = r*r

这就是为什么 Patashu 说无论你早晚应用模运算符都没有关系，因为余数r实际上是与模运算相关的所有内容，也是唯一延续到下一次迭代的东西。

于 2013-03-27T03:44:41.950 回答