Leetcode—2961.双模幂运算【中等】

2023-12-13 03:39:17

2023每日刷题(五十六)

Leetcode—2961.双模幂运算

在这里插入图片描述

实现代码

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

运行结果

在这里插入图片描述

快速幂实现代码

关于快速幂如果不理解,可以看我之前的这篇Leetcode—50.Pow(x,n)【中等】

class Solution {
public:
    long long pow(long long x, int b, int mod) {
        if(b == 1) {
            return x % mod;
        }
        long long res = pow(x, b / 2, mod);
        if(b % 2) {
            return (res % mod) * (res % mod) * x % mod;
        } else {
            return (res % mod) * (res % mod) % mod;
        }
    }
    vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
        vector<int> ans;
        int i = 0;
        for(auto e: variables) {
            if(pow(pow(e[0], e[1], 10), e[2], e[3]) == target) {
                ans.push_back(i);
            } 
            i++;
        }
        return ans;
    }
};

运行结果

在这里插入图片描述

快速幂非递归法实现代码

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

运行结果

在这里插入图片描述

之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!

文章来源:https://blog.csdn.net/qq_44631615/article/details/134928252
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。