$$\huge\color{green}{幂次方——快速幂模板}$$
$$\large\color{blue}{简单讲解!}$$
题目大意
给定任意正整数$n$,求$x^n\mod 233333$的值。
相关算法
快速幂
能在对数时间复杂度内完成特殊的乘方计算。
数学基础
$x^a·x^b=x^{a+b}$:底数相同的数字相乘,指数相加。
快速幂原理
将原来的指数进行二进制拆分,对指数的二进制下的每一位进行增量式计算,得出结果。
时间复杂度
快速幂是对数级别的,时间复杂度最差为$O(log_2{n})$左右。
正确代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;//较高精度的浮点数
typedef pair<int,int> PII;
typedef pair<string,int> PSI;
const ll MOD=233333;
ll quickpow (ll a,ll k)
{
ll cnt=1;
while(k)
{
if (k&1)
cnt=cnt*a%MOD;
a=a*a%MOD;
k>>=1;
}
return cnt%MOD;
}
int main ()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ll x,n;
cin>>x>>n;
cout<<quickpow(x,n);
return 0;
}
// freopen(“.in”,”r”,stdin);
// freopen(“.out”,”w”,stdout);
这是神魔
文件输入输出,$OI$比赛模板
不用给予理睬