Description:

Define a function that takes in two non-negative integers a and b and returns the last decimal digit of a^b. Note that a and b may be very large!

For example, the last decimal digit of 9^7 is 9, since 9^7 = 4782969. The last decimal digit of (2^200)^(2^300), which has over 10^92 decimal digits, is 6. Also, please take 0^0 to be 1.

You may assume that the input will always be valid.

Examples

last_digit("4", "1")            # returns 4
last_digit("4", "2")            # returns 6
last_digit("9", "7")            # returns 9    
last_digit("10","10000000000")  # returns 0

Remarks

JavaScript, C++, R, PureScript

Since these languages don’t have native arbitrarily large integers, your arguments are going to be strings representing non-negative integers instead.

Test Cases:

test_that("Fixed tests", {
  expect_equal(last_digit("4", "1"), 4)
  expect_equal(last_digit("4", "2"), 6)
  expect_equal(last_digit("9", "7"), 9)
  expect_equal(last_digit("9", "0"), 1)
  expect_equal(last_digit("10", "10000000000"), 0)
  expect_equal(last_digit("4200574979866020043461928", "0"), 1)
  expect_equal(last_digit("1606938044258990275541962092341162602522202993782792835301376", "2037035976334486086268445688409378161051468393665936250636140449354381299763336706183397376"), 6)
  expect_equal(last_digit("3715290469715693021198967285016729344580685479654510946723", "68819615221552997273737174557165657483427362207517952651"), 7)
})

test_that("Random tests", {
  solution = function(s1, s2) {
    if (s2 == "0") return(1)
    n1 = as.numeric(substr(s1 , nchar(s1), nchar(s1)))
    n2 = as.numeric(substr(s2 , nchar(s2)-1, nchar(s2)))
    d = if (n1 < 2 | n1 == 5 | n1 == 6) 1 else if (n1 == 4 | n1 == 9) 2 else 4
    n2 = n2 %% d
    if (n2 == 0) n2 = d
    n1^n2 %% 10
  }

  for (i in 1:30) {
    for (j in 1:20) {
      num = c("0", "1", "2", "3", "4", "5", "6", "7", "8", "9")
      s1 = paste(sample(num, sample(ceiling(i / 2):i, 1), replace=TRUE), collapse="")
      s2 = paste(sample(num, sample(ceiling(i / 2):i, 1), replace=TRUE), collapse="")
      while (nchar(s1) > 1 & substr(s1, 1, 1) == "0") s1 = substr(s1, 2, nchar(s1))
      while (nchar(s2) > 1 & substr(s2, 1, 1) == "0") s2 = substr(s2, 2, nchar(s2))
      result = solution(s1, s2)
      expect_equal(last_digit(s1, s2), result)
    }
  }
})

我的思路

程式碼的整體思路爲：

首先，將底數縮減。a^b中的a其實可以縮減爲它的最後一位數的b次方，因此我們使用tail函數獲取最後一位數，當然，其實可以直接用substr函數。
接着，由於一個數的所有的b次方的最後一個數存在一定的規律，因此我們先用一個while回圈獲取所有可能的最後一位數，並存放到num.list中去。
最後，有了num.list，當b=1時，取其中的第一個數作爲最後一位數，b=2,3,...同理，如此回圈遍歷整個num.list，也就是說可以根據b除以num.list的長度的餘數判斷最後一位數是哪個。這裏有一個很麻煩的問題，就是b太大了，而R語言最多隻能顯示22位的數位，因此得想辦法將其縮減，而我無意間發現無論b有多長，a^b的最後一位數都只與b的後面兩位左右的數位有關，因此我使用substr函數提取最後的兩位。

我的程式碼

last_digit <- function(s1, s2) {
  
if(s2=="0") return(1)
num <- as.integer(tail(unlist(strsplit(s1,"")), 1))
num.list <- c(num)
k <- 2
while(!((num**k)%%10 %in% num.list)){num.list=c(num.list,(num**k)%%10); k=k+1}
num.list[(as.integer(substr(s2,nchar(s2)-3,nchar(s2)))-1) %% length(num.list) + 1]
}

補充

如何處理超長的數位？我這有兩位外國網友問的相關問題及解決方案的鏈接：鏈接1 鏈接2

主要還是幾個包的使用方法：

gmp包：The gmp package R bindings to the venerable GMP (GNU Multi-precision library). This must go back 20 years because i used it in University. This Library’s motto is 「Arithmetic Without Limits,」 which is a credible claim–integers, rationals, floats, whatever, right up to the limits of the RAM on your box.

> library(gmp)
> j <- 111111111
> k <- as.bigz(j)
> mul.bigz(k, k)
[1] "12345678987654321"

Brobdingang包：The Brobdingnag package uses natural logs to store the values; (like Rmpfr, implemented using R’s new class structure). I’m always impressed by anyone whose work requires numbers of this scale.

library(Brobdingnag)

googol <- as.brob(1e100)

The Rmpfr package: R bindings which interface to both gmp (above) and MPFR, (MPFR is in turn a contemporary implementation of gmp. I have used the Python bindings (‘bigfloat’) and can recommend it highly. This might be your best option of the three, given its scope, given that it appears to be the most actively maintained, and and finally given what appears to be the most thorough documentation.

R語言Codewars刷題實戰——Last digit of a large number(5kyu)