Question

2961. 双模幂运算

English Version

题目描述

给你一个下标从 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 ：
1) 对于下标 0 ，variables[0] = [2,3,3,10] ，(23 % 10)3 % 10 = 2 。
2) 对于下标 1 ，variables[1] = [3,3,3,1] ，(33 % 10)3 % 1 = 0 。
3) 对于下标 2 ，variables[2] = [6,1,1,4] ，(61 % 10)1 % 4 = 2 。
因此，返回 [0,2] 作为答案。

示例 2：

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

 

提示：

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

解法

方法一：模拟 + 快速幂

我们直接根据题目描述模拟即可。对于幂运算取模，我们可以使用快速幂来加速运算。

时间复杂度 $O(n \times \log M)$，其中 $n$ 为数组 $variables$ 的长度；而 $M$ 为 $b_i$ 和 $c_i$ 中的最大值，本题中 $M \le 10^3$。空间复杂度 $O(1)$。

class Solution:
  def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:
    return [
      i
      for i, (a, b, c, m) in enumerate(variables)
      if pow(pow(a, b, 10), c, m) == target
    ]

class Solution {
  public List<Integer> getGoodIndices(int[][] variables, int target) {
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < variables.length; ++i) {
      var e = variables[i];
      int a = e[0], b = e[1], c = e[2], m = e[3];
      if (qpow(qpow(a, b, 10), c, m) == target) {
        ans.add(i);
      }
    }
    return ans;
  }

  private int qpow(long a, int n, int mod) {
    long ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % mod;
      }
      a = a * a % mod;
    }
    return (int) ans;
  }
}

class Solution {
public:
  vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
    vector<int> ans;
    auto qpow = [&](long long a, int n, int mod) {
      long long ans = 1;
      for (; n; n >>= 1) {
        if (n & 1) {
          ans = ans * a % mod;
        }
        a = a * a % mod;
      }
      return (int) ans;
    };
    for (int i = 0; i < variables.size(); ++i) {
      auto e = variables[i];
      int a = e[0], b = e[1], c = e[2], m = e[3];
      if (qpow(qpow(a, b, 10), c, m) == target) {
        ans.push_back(i);
      }
    }
    return ans;
  }
};

func getGoodIndices(variables [][]int, target int) (ans []int) {
  qpow := func(a, n, mod int) int {
    ans := 1
    for ; n > 0; n >>= 1 {
      if n&1 == 1 {
        ans = ans * a % mod
      }
      a = a * a % mod
    }
    return ans
  }
  for i, e := range variables {
    a, b, c, m := e[0], e[1], e[2], e[3]
    if qpow(qpow(a, b, 10), c, m) == target {
      ans = append(ans, i)
    }
  }
  return
}

function getGoodIndices(variables: number[][], target: number): number[] {
  const qpow = (a: number, n: number, mod: number) => {
    let ans = 1;
    for (; n; n >>= 1) {
      if (n & 1) {
        ans = Number((BigInt(ans) * BigInt(a)) % BigInt(mod));
      }
      a = Number((BigInt(a) * BigInt(a)) % BigInt(mod));
    }
    return ans;
  };
  const ans: number[] = [];
  for (let i = 0; i < variables.length; ++i) {
    const [a, b, c, m] = variables[i];
    if (qpow(qpow(a, b, 10), c, m) === target) {
      ans.push(i);
    }
  }
  return ans;
}