【蓝桥杯集训·每日一题】AcWing 3625. 幂次方

写在前面

本人CSDN博客主页：这里

一、题目

1、原题链接

3625. 幂次方

2、题目描述

对任意正整数 N，计算 X^Nmod233333 的值。

输入格式

共一行，两个整数 X 和 N。

输出格式

共一行，一个整数，表示 X^Nmod233333 的值。

数据范围

1≤X,N≤10⁹

输入样例：

2 5

输出样例：

32

二、解题报告

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;
}

三、知识风暴

快速幂

• 基本思想：利用倍增的思想。若要求a^k，则先将a的2的次方次的幂（指数从2⁰、2¹，...，2^logk）求出来，然后将k用二进制表示，则就写成了2的次方的和的形式，依次看k的每位二进制数，如果该位置为1，则需要将答案乘上a^{该位二进制的权重}，否则不需要操作答案，最终遍历完k的每位二进制数，得到的便是a^k。