LeetCode题解-双模幂运算

心已赠人 2024-04-20 07:36 48阅读 0赞

⭐**简单说两句**⭐

> **✨ 正在努力的小新~**  
> **? 超级爱分享，分享各种有趣干货！**  
> **?? 提供：模拟面试 | 简历诊断 | 独家简历模板**  
> **? 感谢关注，关注了你就是我的超级粉丝啦！**  
> **? 以下内容仅对你可见~**
> 
> **作者：****后端小知识**，**CSDN后端领域新星创作者 |阿里云专家博主**
> 
> **CSDN**个人主页：[后端小知识][Link 1]
> 
> ?**GZH**：`后端小知识`
> 
> ?欢迎关注?点赞?收藏⭐️留言?

![056dd17dd0506591d04525f015765ab749e9f9f19dcaf6e0dcae5d77057d2392-15@3x][056dd17dd0506591d04525f015765ab749e9f9f19dcaf6e0dcae5d77057d2392-15_3x]

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

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

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

**温馨提示**

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

**免费题目链接在此???**：[双模幂运算][Link 2]

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

![image-20231210180650564][]

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

我们先看下数据范围，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;
        }

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

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

![抽象工厂  引导关注][199c21e10d589f1889bfb9e864daecc6.png]

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

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

**CSDN**个人主页：[后端小知识][Link 1]

?**GZH**：`后端小知识`

?欢迎关注?点赞?收藏⭐️留言?

[Link 1]: https://blog.csdn.net/m0_46833224
[056dd17dd0506591d04525f015765ab749e9f9f19dcaf6e0dcae5d77057d2392-15_3x]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/5b4b6807e2814c54a4b7023142ad09e6.png
[Link 2]: https://leetcode-cn.com/problems/double-modular-exponentiation/
[image-20231210180650564]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/ff15c14bf09140f1b46216895b26663f.png
[199c21e10d589f1889bfb9e864daecc6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/20/c9117468ab8d4ed4aa2243f755771919.png