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

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;}
};