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 次幂。

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

显然，一些基础数学可能会有所帮助，比如 "last digit" 东西：

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.

Answer 2

正如我在评论中提到的，这与智能算法确实没有太大关系。使用一些初等数论可以完全减少这个问题。这将产生一个 O(1) 算法。

中国余数定理说，如果我们知道一些数字 x modulo 2 和 modulo 5，我们就知道它 modulo 10。所以找到 a^b^ c modulo 10 可以简化为找到 a^b^c modulo 2 和 a^b^c modulo 5。费马小定理说对于任何素数 p，如果p不整除a，则a^(p-1)=1(modp)，所以a^n=a^(nmod(p-1))(mod）。如果 p 确实整除 a，那么显然对于任何 n > 0，a^n = 0 (mod p)。注意对于任何 n>0，x^n = x (mod 2)，所以 a ^b^c = a (mod 2).

剩下的就是求a^b^c mod 5，归结为求b^c mod 4。不幸的是，既不能用中国余数定理，也不能用费马小定理定理在这里。但是，mod4 b只有4种可能，所以我们可以分别查看。如果我们从 b = 0 (mod 4) 或 b = 1 (mod 4) 开始，那么当然 b^c = b (mod 4)。如果我们有 b = 2 (mod 4) 那么很容易看出 b^c = 2 (mod 4) 如果 c = 1，并且 b^c = 0 (mod 4) 如果 c > 1。如果 b = 3 (mod 4) 那么如果 c 是偶数则 b^c = 3，如果 c 是奇数则 b^c = 1。这给了我们 b^c (mod 4) 对于任何 b 和 c，然后给了我们 a^b^c (mod 5)，所有这些都在常数时间内。

最后有了a^b^c = a (mod 2)我们可以用中国余数定理求出a^b^c (mod 10)。这需要 (x (mod 2), y (mod 5)) 和 z (mod 10) 之间的映射。中国余数定理只告诉我们这个映射是双射的，并没有告诉我们如何找到它。然而，只有 10 个选项，所以这很容易在一张纸上或使用一个小程序完成。一旦我们找到这个映射，我们只需将它存储在一个数组中，我们就可以在 O(1) 中完成整个计算。

顺便说一句，这将是我的算法在 python 中的实现：

# this table only  needs to be calculated once
# can also be hard-coded
mod2mod5_to_mod10 = [[0 for i in range(5)] for j in range(2)]
for i in range(10):
    mod2mod5_to_mod10[i % 2][i % 5] = i

[a,b,c] = [int(input()) for i in range(3)]

if a % 5 == 0:
    abcmod5 = 0
else:
    bmod4 = b % 4
    if bmod4  == 0 or bmod4 == 1:
        bcmod4 = bmod4 
    elif bmod4 == 2:
        if c == 1:
            bcmod4 = 2
        else:
            bcmod4 = 0
    else:
        if c % 2 == 0:
            bcmod4 = 1
        else:
            bcmod4 = 3

    abcmod5 = ((a % 5)**bcmod4) % 5

abcmod2 = a % 2

abcmod10 = mod2mod5_to_mod10[abcmod2][abcmod5]

print(abcmod10)

a^b^c 的最后一位

last digit of a^b^c

math

exponentiation