双模幂运算Java
文章发布较早，内容可能过时，阅读注意甄别。
# 题目
给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [ai, bi, ci, mi]，以及一个整数 target 。
如果满足以下公式，则下标 i 是 好下标：
0 <= i < variables.length ((aibi % 10)ci) % mi == target 返回一个由 好下标 组成的数组，顺序不限 。
示例 1：
- 输入：variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
- 输出：[0,2]
- 解释：对于 variables 数组中的每个下标 i ：
- 对于下标 0 ，variables[0] = [2,3,3,10] ，(23 % 10)3 % 10 = 2 。
- 对于下标 1 ，variables[1] = [3,3,3,1] ，(33 % 10)3 % 1 = 0 。
- 对于下标 2 ，variables[2] = [6,1,1,4] ，(61 % 10)1 % 4 = 2 。
- 因此，返回 [0,2] 作为答案。
示例 2：
- 输入：variables = [[39,3,1000,1000]], target = 17
- 输出：[]
- 解释：对于 variables 数组中的每个下标 i ：
- 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(391 % 10)1000 % 1000 = 1 。
- 因此，返回 [] 作为答案。
提示：
- 1 <= variables.length <= 100
- variables[i] == [ai, bi, ci, mi]
- 1 <= ai, bi, ci, mi <= 103
- 0 <= target <= 103
# 思路
//分治即可 时间复杂度：O(nlogV) Vmax = 1000
# 解法
class Solution {
//分治即可 时间复杂度：O(nlogV) Vmax = 1000
public List<Integer> getGoodIndices(int[][] variables, int target) {
List<Integer> ans = new ArrayList<>();
for(int i = 0, n = variables.length; i < n; i++)
{
int a = variables[i][0], b = variables[i][1], c = variables[i][2], m = variables[i][3];
if(func(func(a, b, 10), c, m) == target) ans.add(i);
}
return ans;
}
public int func(int a, int b, int x)
{
if(b < 2) return b == 0 ? 1 % x : a % x;
int d = b >> 1, f = b & 1;
int aa = (a * a) % x;
return (func(aa, d, x) * func(a, f, x)) % x;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 总结
- 分析出几种情况，然后分别对各个情况实现
