一、题目
1、原题链接
3625. 幂次方
2、题目描述
对任意正整数 N，计算 XNmod233333 的值。
输入格式
共一行，两个整数 X 和 N。
输出格式
共一行，一个整数，表示 XNmod233333 的值。
数据范围
1≤X,N≤109
输入样例：
2 5
1
输出样例：
32
1
二、解题报告
1、思路分析
（1）快速幂模板题。
（2）套用模板即可。
2、时间复杂度
时间复杂度O(logN)
3、代码详解
#include <iostream>
using namespace std;
typedef long long LL;
//快速幂模板，返回a^k%p的结果
int qmi(int a,int k,int p){
LL res=1%p; //注意%p
while(k){
if(k&1) res=res*a%p; //注意%p
k>>=1;
a=(LL)a*a%p; //注意%p
}
return res;
}
int x,n;
int main(){
cin>>x>>n;
cout<<qmi(x,n,233333);
return 0;
}
三、知识风暴
快速幂
基本思想：利用倍增的思想。若要求ak，则先将a的2的次方次的幂（指数从20、21，…，2logk）求出来，然后将k用二进制表示，则就写成了2的次方的和的形式，依次看k的每位二进制数，如果该位置为1，则需要将答案乘上a该位二进制的权重，否则不需要操作答案，最终遍历完k的每位二进制数，得到的便是ak。
