题目描述
对任意正整数 $N$,计算 $X^{N} \mod \ 233333$ 的值。
输入格式
共一行,两个整数 $X$ 和 $N$。
输出格式
共一行,一个整数,表示 $X^{N} \mod \ 233333$ 的值。
数据范围
$1≤X,N≤10^9$
输入样例:
2 5
输出样例:
32
算法1
(暴力) $O(k)$
这题的数据有到$10^9$,直接暴力肯定是会$TLE$的,但我还是写了,过了$6$个数据,不错不错
时间复杂度
参考文献
C++ 代码
long long _pow(int a,int k){ // 算乘方
long long res = 1;
while(k --) res = res * a % 233333;
return res;
}
int main(){
int x,n;
scanf("%d%d",&x,&n);
printf("%lld\n",_pow(x,n) % 233333);
return 0;
}
算法2
(快速幂) $O(log \ k)$
暴力是不可行的,所以我们要用快速幂来解决这道问题。
然后我们就可以把快速幂的模板粘过来改一下就AC啦~
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
long long qmi(int a,int k,int p){ // 快速幂
int res = 1;
while(k){
if(k & 1) res = (long long) res * a % p;
k >>= 1;
a = (long long) a * a % p;
}
return res;
}
int main(){
int x,n;
scanf("%d%d",&x,&n);
printf("%lld\n",qmi(x,n,233333));
return 0;
}
额,可能有点小问题,这里快速幂的时间复杂度不是O(logk)嘛……
哦哦,我忘记改时间复杂度了
改好了