^ b ^ c的最后一位数字

Question

我一直坚持这个问题:

给定a,b和c三个自然数(例如1 <= a,b,c <= 10 ^ 9),你应该找到数字a ^ b ^ c的最后一位数."

我首先想到的是用于提高功率n的O(log n)算法.

   int acc=1; //accumulator
   while(n>0) {
        if(n%2==1)
            acc*=a;
        a=a*a;
        n/=2;
    }

显然,一些基本的数学可能会有所帮助,比如"最后一位数"的东西:

Last_digit(2^n) = Last_digit(2^(n%4))

其中n%4是除法的剩余部分n/4

简而言之,我试图将这些结合起来,但我无法顺利进行.

一些帮助真的会被贬低.

Answer 1

问题是b^c可能非常大.因此,您希望在使用标准模幂运算之前减少它.

您可以注释,a^(b^c) MOD 10最多可以有10个不同的值.

由于鸽笼原则,p对于某些人来说会有一些这样的原因r:

a^r MOD 10 = a^(p+r) MOD 10
p <= 10
r <= 10

这意味着任何q:

a^r MOD 10 = a^r*a^p MOD 10
           = (a^r*a^p)*a^p MOD 10
           = ...
           = a^(r+q*p) MOD 10

对于任何人n = s+r+q*p,s < p你有:

a^n MOD 10 = a^s*a^(r+q*p) MOD 10
           = a^s*a^r MOD 10 
           = a^((n-r) MOD p)*a^r MOD 10

您只需替换n= (b^c)上一个等式即可.

你只计算(b^c-r) MOD p其中,p <= 10这是很容易做到,然后计算a^((b^c-r) MOD p)*a^r MOD 10.