一个巨大数字的最后一位

Question

我正在 Codewars 中解决 Last digit of a huge number。

我设法找到了计算 odd number ^ odd number 和 odd number ^ even number 的方法。但是我陷入了 even ^ even/odd 因为数字和它的幂 mod 之间的关系并不明显。

这是我设法得到的：

lastDigit :: [Integer] -> Integer
lastDigit = (`rem` 10) . go
  where
    go [] = 1
    go [x] = x
    go (x : y : r)
      | odd x && odd y = x ^ (go (y : r) `rem` (x + 1))
      | odd x && even y = x ^ (foldMod y (go r) (x + 1))
      | otherwise = -- any hint?

foldMod :: Integer -> Integer -> Integer -> Integer
foldMod _ 0 _ = 1
foldMod base 1 modulo = base `rem` modulo
foldMod base power modulo = (base * foldMod base (power -1) modulo) `rem` modulo

任何人都可以给出一些关于如何处理偶数情况的提示吗？

Answer 1

我建议重新考虑您的方法，并从更通用的函数开始。具体来说，你能计算

powMod :: Integer -> [Integer] -> Integer

其中 powMod base exponents 计算问题 mod base 中描述的指数塔？请注意，当您递归时，您将使用不同的 base 进行递归——因为各种第一指数的循环长度不一定都是 base 的约数。例如，在基数 10 中，任何第一个指数的最后一位为 7 个周期，每四个周期一次，而不是每十个周期一次；权力的最后一位是这样的：

x               0 1 2 3 4 5 6 7
7^x `mod` 10    1 7 9 3 1 7 9 3

您还需要注意在最终达到的循环中第一个指数不是它本身的情况；例如，在基数 4 中，我们有：

x              0 1 2 3 4 5 6 7
2^x `mod` 4    1 2 0 0 0 0 0 0

所以你不能只看x `mod` 1并从中推断出2^x `mod` 4是什么，即使循环长度是1. （还有其他例子，比如2^x `mod` 12，其中循环比1长，但仍然没有原来的2。）

Answer 2

您无需计算整个数字即可知道最后一位数字，有快速和较慢的方法可以计算最后一位数字而无需担心所有其他数字。

一种简单的方法，可以在 O(log b) 时间内计算出 a^b是通过使用以下等价物：

(a×b) mod m = ((a mod m) × (b mod m)) mod m.

这意味着我们每次都可以计算最后一位数字并使用它。因此这意味着只要我们能表示到81的所有数字，我们就可以计算出 a^b mod m powMod m a b:

powMod :: Int -> Int -> Int -> Int
powMod m = go
    where go _ 0 = 1
          go a b | even n = r
                 | otherwise = (x * r) `mod` m
              where r = go ((a*a) `mod` m) (div b 2) `mod` m

如果我们假设我们可以在常数时间内计算 modulo、除以二、检查值是否为偶数等，则运行时间为 O(log b).

但我们甚至可以通过寻找周期来更快地完成这项工作。想象一下，我们要计算 7 的幂，那么 7^0 就是 1，7^1 就是 7，7^2 mod 10 = 9，等等。我们可以用乘法来做一个 table：

× │  0 1 2 3 4 5 6 7 8 9
──┼─────────────────────
0 │  0 0 0 0 0 0 0 0 0 0
1 │    1 2 3 4 5 6 7 8 9
2 │      4 6 8 0 2 4 8 6
3 │        9 2 5 8 1 4 7
4 │          6 0 4 8 2 6
5 │            5 0 5 0 5
6 │              6 2 8 4
7 │                9 6 3
8 |                  4 2
9 |                    1

如果我们因此查看 7 的幂的最后一位，我们会看到：

power  │     │  last digit
──────────────────────────
 0     │     │           1
 1     │ 7*1 │           7
 2     │ 7*7 │           9
 3     │ 7*9 │           3
 4     │ 7*3 │           1

这就意味着有一个循环，确实，每次乘以7之后，我们就进入下一个状态，从而得到下图：

1  →  7  →  9  →  3
 ↖_______________/

这意味着循环的长度为四。因此，这意味着如果我们必须计算 7 的 374 次方，那么我们知道这是 93 个长度为 4 的循环，因此没有影响，还有两个额外的移动，因此我们知道 7³⁹³ 是 9，无需计算这个数字。由于此类循环的最大长度为 10，因此可以在常数时间内完成确定十进制数的最后一位。

一个巨大数字的最后一位

Last digit of a huge number

haskell

modulo