algorithm - 获取5 ^ 1234566789893943的最后1000个数字

我在一些网上论坛上看到了下面的采访问题。什么是解决这个问题的好办法？
获取5^12345667893943的最后1000位数字

最佳答案

简单算法：

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是幂。

关于algorithm - 获取5 ^ 1234566789893943的最后1000个数字，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24816776/