Leetcode 2961. Double Modular Exponentiation

本文主要是介绍Leetcode 2961. Double Modular Exponentiation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• Leetcode 2961. Double Modular Exponentiation
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：2961. Double Modular Exponentiation

1. 解题思路

这一题思路上没啥难的，主要就是实现上需要取一个巧。

显然当指数非常大的时候直接求pow的话答案会非常大，因此需要对其特殊处理一下，即使用二分的方式对计算量进行缩减，然后每次都计算一个mod即可。

2. 代码实现

给出python代码实现如下：

class Solution:def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:@lru_cache(None)def power_mod(a, p, m):if p == 1:return a % mreturn power_mod(a, p//2, m) * power_mod(a, p-p//2, m) % mans = []for i, (a, b, c, d) in enumerate(variables):z = power_mod(a%10, b, 10)o = power_mod(z%d, c, d)if o == target:ans.append(i)return ans

提交代码评测得到：耗时72ms，占用内存17.2MB。

不过后来想到python自带了pow的mod功能，因此直接用python的内置pow函数反倒更简单一些：

class Solution:def getGoodIndices(self, variables: List[List[int]], target: int) -> List[int]:ans = []for i, (a, b, c, d) in enumerate(variables):z = pow(a, b, mod=10)o = pow(z, c, mod=d)if o == target:ans.append(i)return ans

提交代码评测得到：耗时71ms，占用内存16.3MB。

这篇关于Leetcode 2961. Double Modular Exponentiation的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---