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

简介: 文章目录一、题目1、原题链接2、题目描述二、解题报告1、思路分析2、时间复杂度3、代码详解三、知识风暴快速幂

一、题目

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。


目录
相关文章
|
6月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
109 0
|
6月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
83 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
83 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
89 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1007 印章
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1007 印章
63 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1006 拿金币
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1006 拿金币
66 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1004 无聊的逗
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1004 无聊的逗
92 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1003 礼物
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1003 礼物
92 0
|
6月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1001 跳马
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1001 跳马
66 0
|
6月前
|
移动开发 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-998 娜神平衡
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-998 娜神平衡
59 0
下一篇
无影云桌面