algorithm - 2^2009 の下一桁を見つける方法

Question

この式を使用して、2^n の最後の m 桁を計算していました。

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

しかし、これは と では機能しませn=2009ん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
}