快速幂

题目链接：https://www.luogu.com.cn/problem/P1226（洛谷）

http://ybt.ssoier.cn:8088/problem_show.php?pid=1326（一本通）

方法一：枚举

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int b, p, k;
 4 long long  ans=1;
 5 int main(){
 6     scanf("%d%d%d", &b, &p, &k);
 7     for(int i=1; i<=p; i++)
 8         ans=((ans%k)*(b%k))%k;
 9     printf("%d^%d mod %d=%lld", b, p, k, ans);
10     return 0;
11 }

方法二：归并

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int b, p, k;
 4 long long  quickPower(int a, int b, int k)//是求a的b次方
 5 {
 6     if(b==0)return 1%k;
 7     if(b==1)return a%k;
 8     long long y=quickPower(a, b/2, k)%k;
 9     if(b%2==0)
10         return (y*y)%k;
11     else
12         return ((y*y)%k*a)%k;
13 }
14 int main(){
15     scanf("%d%d%d", &b, &p, &k);
16     printf("%d^%d mod %d=%lld", b, p, k, quickPower(b, p, k));
17     return 0;
18 }

方法三：位运算

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int b, p, k;
 4 long long quickPower(int a, int b)//是求a的b次方
 5 {
 6     long long ans = 1, base = a;//ans为答案，base为a^(2^n)
 7     while(b > 0)//b是一个变化的二进制数，如果还没有用完
 8     {
 9         if(b & 1)//&是位运算，b&1表示b在二进制下最后一位是不是1，如果是：
10         {
11             ans *= base;//把ans乘上对应的a^(2^n)
12             ans %= k;
13         }
14         
15         base *= base;//base自乘，由a^(2^n)变成a^(2^(n+1))
16         base %= k;
17         b >>= 1;//位运算，b右移一位，如101变成10（把最右边的1移掉了），10010变成1001。现在b在二进制下最后一位是刚刚的倒数第二位。结合上面b & 1食用更佳
18     }
19     return ans%k;
20 }
21 int main(){
22     scanf("%d%d%d", &b, &p, &k);
23     printf("%d^%d mod %d=%d", b, p, k, quickPower(b, p));
24     return 0;
25 }