LeetCode——2961. 双模幂运算

通过万岁！！！

题目：给你一个n*4的二维数组variables以及一个目标值target，然后让你找到一些下标。其标准是variables[] $variables[0]^{variables[1]}\%10)^{variables[2]})\%variables[3]==target$ 。
思路1：首先的思路就是直接便利二维数组计算出来，但是计算的过程中我们可以发现variables[i]的值最大是1000，也就是说计算结果太大了。这就要求我们想办法简化这个计算，题目中其实给我们提示了，就是对10取余。这个信息告诉我们，其实我们每次只需要得到余数就好了。举个例子，比如我们要计算 $variables[0]^{variables[1]}\%10$ ，其实我们循环variables[1]次，每次都让“余数”*variables[0]，然后再对10取余即可。
思路2：我们可以看到，其实在getRemainder主要的功能就是variables[0]进行了variables[1]次相乘，这里我们可以利用一下分治的思想。每次把variables[1]/2进行递归即可，值得注意的是，如果variables[1]%2=1，则表示不能完全分成两份，记得在乘一个variables[0]。
技巧：数学、分治

java代码——思路1

class Solution {public List<Integer> getGoodIndices(int[][] variables, int target) {List<Integer> ret = new ArrayList<>();for (int i = 0; i < variables.length; i++) {int temp = getRemainder(variables[i][0], variables[i][1], 10);if (getRemainder(temp, variables[i][2], variables[i][3]) == target) {ret.add(i);}}return ret;}/*** 获取a^b%val的结果** @param a* @param b* @param val* @return*/private int getRemainder(int a, int b, int val) {int ret = a % val;for (int i = 1; i < b; i++) {ret *= a;ret %= val;}return ret;}
}

java代码——思路2

class Solution {public List<Integer> getGoodIndices(int[][] variables, int target) {List<Integer> ret = new ArrayList<>();for (int i = 0; i < variables.length; i++) {int temp = getRemainder(variables[i][0], variables[i][1], 10);if (getRemainder(temp, variables[i][2], variables[i][3]) == target) {ret.add(i);}}return ret;}/*** 获取a^b%val的结果** @param a* @param b* @param val* @return*/private int getRemainder(int a, int b, int val) {if (b == 1) {return a % val;}int branch = getRemainder(a, b / 2, val);if (b % 2 == 0) {return branch * branch % val;} else {return branch * branch * a % val;}}
}