一、题目
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。