1

LeetCode题解-双模幂运算

 2 months ago
source link: https://blog.51cto.com/u_15061012/10520505
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

LeetCode题解-双模幂运算

精选 原创

⭐简单说两句⭐

✨ 正在努力的小新~
💖 超级爱分享，分享各种有趣干货！
👩💻 提供：模拟面试 | 简历诊断 | 独家简历模板
🌈 感谢关注，关注了你就是我的超级粉丝啦！
🔒 以下内容仅对你可见~

作者：后端小知识，后端领域新星创作者 |阿里云专家博主

个人主页：后端小知识

🔎GZH：后端小知识

🎉欢迎关注🔎点赞👍收藏⭐️留言📝

LeetCode题解-双模幂运算_leetcode

亲爱的朋友们，欢迎来到今天的LeetCode题解环节！🎉

前几天，我向学弟学妹们分享了一个关于快速幂的知识点。巧的是，今天在解答LeetCode题目时，我发现了一个可以用快速幂技巧来解决的问题！🔍

亲爱的朋友们，让我们一起来看看这道题目吧！

温馨提示

为了让大家更方便地尝试和提交代码，我特意为大家提供了题目的链接，是不是很贴心呢？😋

免费题目链接在此🎉🎉🎉： 双模幂运算

为了方便大家查看，我已经将题目截图附在下方，希望对你们有所帮助！😁😁😁

LeetCode题解-双模幂运算_个人主页_02

这个题描述得非常清楚，我们直接按照要求来做就是

我们先看下数据范围，10^3方内，直接算出结果最后来求余是不行的，因为int，long根本装不下

那怎么做呢？用大数？其实不用，我们只需要用到同余定理（小学知识，忘了的记得补下哟）就行了😎

求幂次还可以直接用快速幂来做，快速幂之前讲过，这里就不多唠叨了

ok , 简单题直接上AC的代码😎

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

其中快速幂的模板（同余版）求 （a^b）%m

int quick(long long a,long long b,int m){
        long long res=1;
        while(b){
            if(b&1) res=(res*a)%m;
            a=(a*a)%m;
            b>>=1;
        }
        return res%m;
    }

好了，今天的题解分享到这里就结束咯，今天这个主要是模板题，友友们尽量吧模板记住，在做题直接写就行勒，不然在做题时还得现推，多麻烦，是吧😵💫

【都看到这了，点点赞点点关注呗，爱你们】😚😚

LeetCode题解-双模幂运算_个人主页_03

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK