math - a^b^c 的最后一位

Question

我被这个问题困住了:

Given a, b and c three natural numbers (such that 1<= a, b, c <= 10^9), you are supposed to find the last digit of the number a^b^c."

我首先想到的是 O(log n) 算法，用于在 n 次幂时提高 a。

   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 .