Skip to content

2961. Double Modular Exponentiation 👍

  • Time: $O(n(\log b + \log c))$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
    vector<int> ans;
    for (int i = 0; i < variables.size(); ++i) {
      const int a = variables[i][0];
      const int b = variables[i][1];
      const int c = variables[i][2];
      const int m = variables[i][3];
      if (modPow(modPow(a, b, 10), c, m) == target)
        ans.push_back(i);
    }
    return ans;
  }

 private:
  long modPow(long x, long n, int mod) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x % mod, (n - 1), mod) % mod;
    return modPow(x * x % mod, (n / 2), mod) % mod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public List<Integer> getGoodIndices(int[][] variables, int target) {
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < variables.length; ++i) {
      final int a = variables[i][0];
      final int b = variables[i][1];
      final int c = variables[i][2];
      final int m = variables[i][3];
      if (modPow(modPow(a, b, 10), c, m) == target)
        ans.add(i);
    }
    return ans;
  }

  private long modPow(long x, long n, int mod) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x % mod, (n - 1), mod) % mod;
    return modPow(x * x % mod, (n / 2), mod) % mod;
  }
}

1
2
3
4
5
6
7
8
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]