-
Notifications
You must be signed in to change notification settings - Fork 0
/
2961. 双模幂运算.cpp
42 lines (31 loc) · 994 Bytes
/
2961. 双模幂运算.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
vector<int> getGoodIndices(vector<vector<int>>& variables, int target) {
vector<int> ans;
for (int i = 0; i < variables.size(); i++) {
long long first = variables[i][0];
long long second = variables[i][1];
long long third = variables[i][2];
long long fourth = variables[i][3];
long long x = modExp(first, second, 10);
long long y = modExp(x, third, fourth);
if (y == target) {
ans.push_back(i);
}
}
return ans;
}
private:
long long modExp(long long base, long long exp, long long mod) {
long long result = 1;
base = base % mod;
while (exp > 0) {
if (exp % 2 == 1) {
result = (result * base) % mod;
}
exp = exp >> 1;
base = (base * base) % mod;
}
return result;
}
};