对于给定的数组[x1，x2，x3，…，xn]，计算幂的累积：x1^（x2^（x3^（…^xn））的最后一位（十进制）数字。
例如，对于数组[3，4，2]，您的代码应该返回1，因为3^（4^2）=3^16=43046721。
结果的增长得快得令人难以置信。例如，9^（9^9）有超过3.69亿个数字。你计算的lastDigit必须有效地处理这些数字。
我们假设0^0=1，并且空列表的lastDigit等于1。
算法实现：
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Numerics;
5 namespace Solution
6 {
7 public class Calculator
8 {
9 public static int LastDigit(int[] array)
10 {
11 BigInteger t = 1;
12 var arr = array.Reverse().ToList();
13
14 foreach(var x in arr)
15 {
16 if(t < 4)
17 t = BigInteger.Pow(x,int.Parse(t.ToString()));
18 else
19 {
20 int exponent = int.Parse(BigInteger.ModPow(t,1,4).ToString()) + 4;
21 t = BigInteger.Pow(x,exponent);
22 }
23 }
24
25 return (int)BigInteger.ModPow(t,1,10);
26 }
27 }
28 }
算法详解：
1 public static int LastDigit(int[] array)
2 {
3 BigInteger t = 1; // 初始化变量t为1，用于存储计算结果
4 var arr = array.Reverse().ToList(); // 将输入数组倒序并转换为列表
5
6 foreach(var x in arr) // 对列表中的每个元素进行循环遍历
7 {
8 if(t < 4) // 如果t小于4
9 t = BigInteger.Pow(x, int.Parse(t.ToString())); // 使用x的t次方更新t
10 else // 如果t大于等于4
11 {
12 int exponent = int.Parse(BigInteger.ModPow(t, 1, 4).ToString()) + 4; // 计算指数值，将t对4取模后加上4
13 t = BigInteger.Pow(x, exponent); // 使用x的exponent次方更新t
14 }
15 }
16
17 return (int)BigInteger.ModPow(t, 1, 10); // 返回t对10取模的结果作为最后一位数字
18 }
在代码中，判断 if(t < 4) 的目的是为了处理指数较小的情况。当指数较小（小于4）时，直接使用 BigInteger.Pow(x, int.Parse(t.ToString())) 计算 x 的指数结果，并将结果赋给变量 t。
这是因为指数较小的情况下，计算结果不会非常大，可以直接使用 BigInteger.Pow 方法进行计算。这种情况下，不需要进行额外的处理，直接将计算结果赋给 t 即可。
而当指数较大（大于等于4）时，为了避免计算结果过大导致性能问题，代码使用了一种降幂优化策略。在这种情况下，通过计算 t 的模 4 的结果（BigInteger.ModPow(t, 1, 4)），并加上4，得到一个新的指数值 exponent。然后使用 BigInteger.Pow(x, exponent) 计算 x 的新指数结果，并将结果赋给 t。
因此，if(t < 4) 分支用于处理指数较小的情况，而 else 分支用于处理指数较大的情况，并进行了一种优化策略来避免计算结果过大。这样可以在不牺牲性能的情况下，处理更大的指数值。
让我们通过一个示例来解释这个降幂计算过程。
假设我们有以下输入数据：
- `x = 2`：底数为2。
- `t = 10`：指数为10。
根据代码逻辑，我们首先检查指数是否大于等于4。在这种情况下，指数为10大于4，因此我们需要执行优化策略。
1. 计算 `t` 对 4 取模的结果：
- `t_mod4 = t % 4 = 10 % 4 = 2`
这里我们使用 `%` 运算符来计算 `t` 对 4 取模的结果，得到 `2`。
2. 将 `t_mod4` 加上 4，得到新的指数值 `exponent`：
- `exponent = t_mod4 + 4 = 2 + 4 = 6`
这里我们将 `t_mod4` 的结果 `2` 加上 4，得到新的指数值 `6`。
3. 计算 `x` 的新指数结果：
- `new_t = BigInteger.Pow(x, exponent) = BigInteger.Pow(2, 6) = 64`
这里我们使用 `BigInteger.Pow` 方法计算 `x` 的新指数结果，即将底数 `2` 的指数值设为 `6`，得到 `64`。
4. 将新的指数结果赋给 `t`：
- `t = new_t = 64`
我们将计算得到的新指数结果 `64` 赋给变量 `t`。
最后，我们得到的结果是 `t = 64`。这个结果将在后续的代码中继续使用，进行其他的计算或操作。
这就是当指数较大时，代码使用的优化策略的步骤。通过对指数取模并加上一个固定值，我们得到一个较小的指数值，以避免计算结果过大导致性能问题。
测试用例：
1 namespace Solution {
2 using NUnit.Framework;
3 using System;
4
5 public struct LDCase {
6 public int[] test;
7 public int expect;
8 public LDCase(int[] t, int e) {
9 test = t;
10 expect = e;
11 }
12 }
13
14 [TestFixture]
15 public class SolutionTest {
16 private static int CalculateLD(int[] array) {
17 int ans = 1;
18 for(int i=array.Length-1; i>=0;i--) {
19 int exp = ans;
20 if(ans >= 4) {
21 exp = ans%4+4;
22 }
23 int b = array[i]%4+4;
24 if(i == 0) {
25 b = array[i]%10;
26 }
27 else if(array[i] < 4) {
28 b = array[i];
29 }
30 ans = (int)(Math.Pow(b, exp));
31 }
32 return ans%10;
33 }
34
35 [Test]
36 public void SampleTest() {
37 LDCase[] allCases = new LDCase[] {
38 new LDCase(new int[0], 1),
39 new LDCase(new int[] {0,0}, 1),
40 new LDCase(new int[] {0,0,0}, 0),
41 new LDCase(new int[] {1,2}, 1),
42 new LDCase(new int[] {3,3,1}, 7),
43 new LDCase(new int[] {3,3,2}, 3),
44 new LDCase(new int[] {3,5,3}, 3),
45 new LDCase(new int[] {3,4,5}, 1),
46 new LDCase(new int[] {4,3,6}, 4),
47 new LDCase(new int[] {7,6,1}, 9),
48 new LDCase(new int[] {7,6,2}, 1),
49 new LDCase(new int[] {7,6,21}, 1),
50 new LDCase(new int[] {12,30,21}, 6),
51 new LDCase(new int[] {2,0,1}, 1),
52 new LDCase(new int[] {2,2,2,0}, 4),
53 new LDCase(new int[] {2,2,101,2},6),
54 new LDCase(new int[] {4,0}, 1),
55 new LDCase(new int[] {3,0,0}, 3),
56 new LDCase(new int[] {2,2,1}, 4),
57 new LDCase(new int[] {2,2,1,2}, 4),
58 new LDCase(new int[] {3,3,0,0}, 7),
59 new LDCase(new int[] {3,4,0}, 3),
60 new LDCase(new int[] {3,2,1,4,4},9),
61 new LDCase(new int[] {5,0}, 1),
62 new LDCase(new int[] {2,3,2}, 2),
63 new LDCase(new int[] {82242,254719,736371}, 8),
64 new LDCase(new int[] {937640,767456,981242}, 0),
65 new LDCase(new int[] {123232,694022,140249}, 6),
66 new LDCase(new int[] {499942,898102,846073}, 6),
67 new LDCase(new int[] {837142,918895,51096}, 2),
68 new LDCase(new int[] {625703,43898,614961,448629}, 1),
69 new LDCase(new int[] {2147483647,2147483647,2147483647,2147483647}, 3)
70 };
71 for(int i=0; i<allCases.Length;i++) {
72 string msg = $"Incorrect answer for array=[{string.Join(", ", allCases[i].test)}]";
73 Assert.AreEqual(allCases[i].expect, Calculator.LastDigit(allCases[i].test), msg);
74 }
75 }
76
77 [Test]
78 public void RandomTest() {
79 Random rnd = new Random();
80
81 for(int i=0; i<100;i++) {
82 int size = rnd.Next(1,20);
83 int[] array1 = new int[size];
84 int[] array2 = new int[size];
85 int[] array3 = new int[size];
86 for(var j=0; j<size;j++) {
87 var rand1 = rnd.Next(0,1000000);
88 var rand2 = rnd.Next(0,3);
89 var rand3 = rnd.Next(0,2);
90 if(j == 0) {
91 rand1++; rand2++; rand3++;
92 }
93 array1[j] = rand1;
94 array2[j] = rand2;
95 array3[j] = rand3;
96 }
97
98 string msg1 = $"Incorrect answer for array=[{string.Join(", ", array1)}]";
99 int expect1 = SolutionTest.CalculateLD(array1);
100 Assert.AreEqual(expect1, Calculator.LastDigit(array1), msg1);
101
102 string msg2 = $"Incorrect answer for array=[{string.Join(", ", array2)}]";
103 int expect2 = SolutionTest.CalculateLD(array2);
104 Assert.AreEqual(expect2, Calculator.LastDigit(array2), msg2);
105
106 string msg3 = $"Incorrect answer for array=[{string.Join(", ", array3)}]";
107 int expect3 = SolutionTest.CalculateLD(array3);
108 Assert.AreEqual(expect3, Calculator.LastDigit(array3), msg3);
109 }
110 }
111 }
112 }
标签：10,LDCase,降幂,c#,Pow,复杂度,BigInteger,int,new From： https://www.cnblogs.com/lan80/p/17661381.html