获取5 ^ 1234566789893943的最后1000位数字

Question

我在一些在线论坛上看到了以下面试问题.对此有什么好的解决方案？

获取5 ^ 1234566789893943的最后1000位数字

Answer 1

简单的算法:

1. Maintain a 1000-digits array which will have the answer at the end
2. Implement a multiplication routine like you do in school. It is O(d^2).
3. Use modular exponentiation by squaring.

迭代取幂:

array ans;
int a = 5;

while (p > 0) {

    if (p&1) {

       ans = multiply(ans, a)
    }

    p = p>>1;

    ans = multiply(ans, ans);
}

multiply: multiplies two large number using the school method and return last 1000 digits.

时间复杂度: O(d ^ 2*logp)其中d是所需的最后一位数,p是幂.

Answer 2

这个问题的一个典型解决方案是使用模运算和求幂,通过平方来计算5^1234566789893943除以的余数10^1000.但是在你的情况下,这仍然不够好,因为它需要大约1000*log(1234566789893943)操作并且这不是太多,但我将提出一种更通用的方法,它可以用于更大的指数值.

你将不得不使用更复杂的数论.你可以使用欧拉定理来更有效地得到5^1234566789893943模数的余数2^1000.表示这一点r.很明显可以5^1234566789893943被整除5^1000.

之后你需要找到一个数字d 5^1000*d = r(modulo 2^1000).要解决这个等式,你应该计算5^1000(modulo 2^1000).之后剩下的就是做除以模2 ^ 1000的除法.再次使用欧拉定理,这可以有效地完成.用那个x^(phi(2^1000)-1)*x =1(modulo 2^1000).这种方法更快,是唯一可行的解​​决方案.