双模幂运算

100155. 双模幂运算

给你一个下标从 0 开始的二维数组 variables ，其中 variables[i] = [a_i, b_i, c_i, m_i]，以及一个整数 target 。

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

0 <= i < variables.length
((a_i^b_i % 10)^c_i) % m_i == 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] == [a_i, b_i, c_i, m_i]
1 <= a_i, b_i, c_i, m_i <= 10³
0 <= target <= 10³

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: vector<int> getGoodIndices(vector<vector<int>>& variables, int target) { } };

rust 解法, 执行用时: 1 ms, 内存消耗: 2.1 MB, 提交时间: 2024-07-30 09:29:39

impl Solution {
    pub fn get_good_indices(variables: Vec<Vec<i32>>, target: i32) -> Vec<i32> {
        let pow = |mut x, mut n, m| {
            // 本题 m 很小，即使平方也不会超过 i32 范围，所以不需要用 i64
            let mut res = 1;
            while n > 0 {
                if n % 2 > 0 {
                    res = res * x % m;
                }
                x = x * x % m;
                n /= 2;
            }
            res
        };
        let check = |v: &Vec<_>| pow(pow(v[0], v[1], 10), v[2], v[3]) == target;
        variables.iter()
            .enumerate()
            .filter_map(|(i, v)| check(v).then_some(i as i32))
            .collect()
    }
}

javascript 解法, 执行用时: 62 ms, 内存消耗: 51.7 MB, 提交时间: 2024-07-30 09:29:20

/**
 * @param {number[][]} variables
 * @param {number} target
 * @return {number[]}
 */
var getGoodIndices = function(variables, target) {
    const ans = [];
    for (let i = 0; i < variables.length; i++) {
        const [a, b, c, m] = variables[i];
        if (pow(pow(a, b, 10), c, m) === target) {
            ans.push(i);
        }
    }
    return ans;
};

// 本题 mod 很小，即使平方也不会超过 MAX_SAFE_INTEGER 范围，所以不需要用 BigInt
function pow(x, n, mod) {
    let res = 1;
    while (n) {
        if (n % 2) {
            res = res * x % mod;
        }
        x = x * x % mod;
        n = Math.floor(n / 2);
    }
    return res;
}

golang 解法, 执行用时: 0 ms, 内存消耗: 2.8 MB, 提交时间: 2023-12-11 00:30:58

func getGoodIndices(variables [][]int, target int) (ans []int) {
	for i, v := range variables {
		if pow(pow(v[0], v[1], 10), v[2], v[3]) == target {
			ans = append(ans, i)
		}
	}
	return
}

func pow(x, n, mod int) int {
	res := 1
	for ; n > 0; n /= 2 {
		if n%2 > 0 {
			res = res * x % mod
		}
		x = x * x % mod
	}
	return res
}

cpp 解法, 执行用时: 12 ms, 内存消耗: 18.3 MB, 提交时间: 2023-12-11 00:30:43

class Solution {
    long long pow(long long x, int n, int m) {
        long long res = 1;
        for (; n; n /= 2) {
            if (n % 2) res = res * x % m;
            x = x * x % m;
        }
        return res;
    }

public:
    vector<int> getGoodIndices(vector<vector<int>> &variables, int target) {
        vector<int> ans;
        for (int i = 0; i < variables.size(); i++) {
            auto &v = variables[i];
            if (pow(pow(v[0], v[1], 10), v[2], v[3]) == target) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

java 解法, 执行用时: 1 ms, 内存消耗: 42.4 MB, 提交时间: 2023-12-11 00:30:25

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

    private long pow(long x, int n, int mod) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0)
                res = res * x % mod;
            x = x * x % mod;
        }
        return res;
    }
}

python3 解法, 执行用时: 48 ms, 内存消耗: 16.1 MB, 提交时间: 2023-12-11 00:29:59

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]

上一题

下一题

详情