如何找到的2 ^ 2009的最后一位数字 [英] How to find the last digits of 2^2009

问题描述

我是用这个公式来计算2的n次方最后m个位数。

I was using this formula to calculate last m digits of 2^n.

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

但是，这是不工作的 N = 2009年和 M = 3 。 推荐在我的计算或任何错误更好的公式是否存在。

But this is not working for n=2009 and m=3. Suggest any error in my calculation or a better formula if there is.

推荐答案

我不明白你的公式是这样做的，但最简单的方法是计算（2 ^ 2009）％（10 ^ M）。这里是一个伪code找到（X ^ Y）％MOD 在 O（日志Y）。把 X = 2，Y = 2009 和模= 10 ^ M

I don't understand what your formula is doing, but the simplest way is to calculate (2^2009)%(10^m) . Here is a pseudo code to find (x^y)%mod in O(log y). Put x=2, y=2009 and 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
}

这篇关于如何找到的2 ^ 2009的最后一位数字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！