题解分享
题解分享简介
快速幂 - 题解
```
/*
思路：
思路一：
1 (a.b)%c = ((a%c)*(b%c))%c
2 pow(3,10)=pow(pow(3,2),5)=pow(9*3,4)=pow(pow(27,2),2)
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll function_Modexpfast ( ll a , ll b , ll c ) {
a = a % c;
ll result = 1; //记录a的b次方
while ( b != 0 ) { //循环操作 b&1
if ( b % 2 == 1 ) { // 每次对b除以2 奇数时则是result记录时。
result = (result * a) % c; //奇数时 a的b次方= a*a * a的b－1次方
}
a = (a * a) % c;
b = b >> 1; //向右移动一位 就是除以2
}
cout << result << endl;
return result;
}
int main()
{
int n;
cin >> n;
for ( int i = 1; i <= n; i++ ) {
ll a, b, c;
cin >> a >> b >> c;
function_Modexpfast(a , b , c);
}
return 0;
}
```
查看全文
0
0
0
5
快速幂 - 题解
```
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef pair<int,int> aII;
using ll = long long;
using ULL = unsigned long long;
const int N = 1e6+5;
inline ll qmi(ll a, ll b, ll p) {
ll res = 1 % p;
for (; b; b >>= 1) {
if (b&1) res = res * a % p;
a = a * a % p;
}
return res;
}
inline void solve() {
ll a, b, p;
cin >> a >> b >> p;
cout << qmi(a, b, p) << endl;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//int _ = 1;
int _; cin >> _;
while (_--) solve();
return 0;
}
```
查看全文
0
0
0
3
快速幂 - 题解
```cpp
// https://dashoj.com/p/97
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
int main() {
cin >> n;
for (ll i = 0; i < n; i++) {
ll a, k, p, result = 1;
cin >> a >> k >> p;
a = a % p;
while (k) {
if (k % 2) result = (result * a) % p;
k /= 2;
a = (a * a) % p;
}
cout << result << endl;
}
return 0;
}
```
查看全文
0
0
0
2
快速幂 - 题解
```
def quick_pow_mod_iterative(a, b, p):
result = 1
base = a % p
while b > 0:
if b % 2 == 1: # b 是奇数
result = (result * base) % p
base = (base * base) % p
b //= 2
return result
n = int(input())
for _ in range(n):
a, k, p = map(int, input().split())
result = quick_pow_mod_iterative(a, k, p)
print(result)
```
查看全文
0
0
0
3
快速幂 - 题解
include
using namespace std;
```
long long a ,k ,p;
//mypow 只是一个自定义名字
long long myPow( long long a , long long k , long long p) {
long long res=1;
while (k){
if(k&1)
res=res*a%p;
k >>=1;/相当于指数除以2
a = a*a%p;
}
return res;
}
int main(){
int n;
cin >>n;
while (n--) {
long long a,k ,p;
cin >>a>>k >>p;
cout << myPow(a,k,p) << '\n';
}
return 0;
```
}
查看全文
0
0
0
1
快速幂 - 题解
拓展: 如果 $k$ 可以为负数, 即 $a^{-|k|}$ (这样写是为了方便看(因为严格来讲k现在是负数)) 那么可以先求 $a^{|k|}$ 然后 返回 $1/a^{|k|}$ (注: 返回值为double), 特判 k 为负数的情况. (可以试试力扣pow(x, y)这题)❤️
```cpp
#include <iostream>
using namespace std;
using ll = long long;
ll myPow(ll a, ll k, ll p) {
ll res = 1;
while (k) {
if (k & 1)
res = res * a % p;
k >>= 1;
a = a * a % p;
}
return res;
}
int main() {
int n;
cin >> n;
while (n--) {
ll a, k, p;
cin >> a >> k >> p;
cout << myPow(a, k, p) << '\n';
}
return 0;
}
```
查看全文
0
0
0
1
