algorithm - 如何找到 2^2009 的最后一位数字

Question

我正在使用这个公式来计算 2^n 的最后 m 个数字。

pow=2+(n-m)%(4*5^(m-1))  
ans =(2^pow)%(10^m)**  

但这不适用于n=2009and m=3。建议我的计算中的任何错误或更好的公式（如果有）。

Answer 1

我不明白你的公式在做什么，但最简单的方法是计算(2^2009)%(10^m). 这是一个伪代码，可以(x^y)%mod在O(log y). 放x=2, y=2009和mod=10^m

power(x,y)
{
    if( y == 0)
        return 1
    temp = power(x, y/2)
    if (y%2 == 0)
        return (temp*temp)%mod
    else
        return ((x*temp%mod)*temp)%mod
}