快速幂

title: 快速幂
date: 2022-11-16 05:45:26
tags: 算法

本文章遵守知识共享协议 CC-BY-NC-SA ，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

快速幂

前置知识

• 位运算

讲解

快速幂是一种快速进行幂运算的算法

不使用快速幂的幂运算代码：

int pow(int a,int p){
    int ans = a;
    for(int i=1;i<=p;i++)
        ans*=a;
    return ans;
}

容易看出，该代码的时间复杂度为 O(p) ，而优化方法则是使用二进制的方法，枚举二进制每一位。

int pow(int a,int p){
 int ans = 1,base = a;
    while(p){
        if(p&1)
            ans*=base;
        p>>=1;
        base*=base;
    }
    return ans;
}

因为此算法枚举 p 的每一位二进制位，所以时间复杂度为 O(log p)。
所以效率优于普通快速幂

关于取模

取模可以在这些地方进行：

int pow(int a,int p,int mod){
 int ans = 1,base = a;
    while(p){
        if(p&1)
            ans=(ans*base)%mod; // 这里
        p>>=1;
        base=(base*base)%mod; // 这里
    }
    return ans%mod; // 这里
}

例题

P1226-【模板】快速幂||取余运算

纯板子，直接打就行。

一定！一定！！一定！！！要开 long long !（我不说是谁 CSP-S 2022 没开 long long 导致挂掉的）