快速幂算法
备考笔记
发布于2025年3月3日 00:14
阅读数 46
long long EXP(long long x, long long n)
{
long long ans=1;
while(n > 0)
{
if(n % 2 == 1) // 如果 n 是奇数,则把当前的 x 乘到 ans 上
{
ans = (ans * x)%233333;
}
x = (x * x)%233333; // 计算 x 的下一个平方值
n /= 2; // 将 n 右移一位,相当于除以 2
}
return ans;
}
登录后发布评论
可以看为,底数和指数在做等效变换,比如2^100,x变为4,n变为50,4^50,最后会变为,(2^100)^1