题目

给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [ai, bi, ci, mi]，以及一个整数 target 。

如果满足以下公式，则下标 i 是 好下标：

0 <= i < variables.length ((ai^bi % 10)^ci) % mi == target 返回一个由 好下标 组成的数组，顺序不限 。

示例 1：

• 输入：variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
• 输出：[0,2]
• 解释：对于 variables 数组中的每个下标 i ：
• 1. 对于下标 0 ，variables[0] = [2,3,3,10] ，(2³ % 10)³ % 10 = 2 。
• 2. 对于下标 1 ，variables[1] = [3,3,3,1] ，(3³ % 10)³ % 1 = 0 。
• 3. 对于下标 2 ，variables[2] = [6,1,1,4] ，(6¹ % 10)¹ % 4 = 2 。
• 因此，返回 [0,2] 作为答案。

示例 2：

• 输入：variables = [[39,3,1000,1000]], target = 17
• 输出：[]
• 解释：对于 variables 数组中的每个下标 i ：
• 1. 对于下标 0 ，variables[0] = [39,3,1000,1000] ，(39¹ % 10)¹⁰⁰⁰ % 1000 = 1 。
• 因此，返回 [] 作为答案。

提示：

• 1 <= variables.length <= 100
• variables[i] == [ai, bi, ci, mi]
• 1 <= ai, bi, ci, mi <= 10³
• 0 <= target <= 10³

思路

//分治即可 时间复杂度：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;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现