Question

2961. Double Modular Exponentiation

中文文档

Description

You are given a 0-indexed 2D array variables where variables[i] = [ai, bi, ci, mi], and an integer target.

An index i is good if the following formula holds:

• 0 <= i < variables.length
• ((aibi % 10)ci) % mi == target

Return _an array consisting of good indices in any order_.

 

Example 1:

Input: variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2
Output: [0,2]
Explanation: For each index i in the variables array:
1) For the index 0, variables[0] = [2,3,3,10], (23 % 10)3 % 10 = 2.
2) For the index 1, variables[1] = [3,3,3,1], (33 % 10)3 % 1 = 0.
3) For the index 2, variables[2] = [6,1,1,4], (61 % 10)1 % 4 = 2.
Therefore we return [0,2] as the answer.

Example 2:

Input: variables = [[39,3,1000,1000]], target = 17
Output: []
Explanation: For each index i in the variables array:
1) For the index 0, variables[0] = [39,3,1000,1000], (393 % 10)1000 % 1000 = 1.
Therefore we return [] as the answer.

 

Constraints:

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

Solutions

Solution 1: Simulation + Fast Power

We can directly simulate according to the problem description. For the power operation modulo, we can use the fast power method to speed up the calculation.

The time complexity is $O(n \times \log M)$, where $n$ is the length of the array $variables$; and $M$ is the maximum value in $b_i$ and $c_i$, in this problem $M \le 10^3$. The space complexity is $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;
}