基于 GNU 扩展库实现快速幂的冷门技巧（附数据结构 rope 介绍）

__wenziyi__ · 2026-04-23 10:16:02 · 算法·理论

引子

在漫长的 OI 学习和追忆生涯中，我们经常会遇到如下类似题型或计算：对于给定整数 a、b、p，求

a^b \bmod p

这类题目要求实现指数幂取模运算，直接上手循环相乘的做法最容易想到，复杂度是 O(n) 级别的。但细细思忖一下，如果当其中的底数、指数、模数为较大整数时，直接暴力计算可能会出现数值溢出、时间复杂度过高等问题，有什么方法可以对算法进行优化呢？快速幂正是针对这类问题的高效算法求解。

常规解法需运用数学思维，结合递推、递归等手段手写快速幂。算法的优美的确精彩纷呈、叹为观止，但千篇一律的题解与文章却总会令人审美疲劳。为此，本文将带领你深度探索 OI 编程的未知领域，创新性地使用 GNU C++ 扩展库中的 __gnu_cxx::power 函数，通过自定义运算规则与单位元，在既能保证代码的时间复杂度，又能规避手写快速幂的繁琐的前提下，实现极简且高效的快速幂取模，一同感悟“科技”的强大力量。

算法解析

作为快速幂算法的延伸，还是先简要插入一段数学原理吧。毕竟，我们“科技与狠活”的底层逻辑正是基于以下算法步骤的实现，还是有必要了解的。下面速速提及一下（懂快速幂算法的大佬可以跳过此章节）。

快速幂核心思想

快速幂（二进制幂）的本质是将指数拆分为二进制形式，再通过平方倍增运算将乘法次数从 O(n) 降至 O(\log n)，避免暴力循环计算幂次。我们知道，对于任何整数，它都能被改写成 2 的幂之和形式。因此，我们可以把指数 b 拆成二进制，每次把指数折半，底数平方。

比如：当 b = 10 时，其二进制表示为 \tt 1010，即

10=2^3+2^1=8+2

那么：a^{10} = a^8 × a^2。

普通的乘法循环在计算 a^{10} 时需要进行 10 次运算，而我们应用快速幂算法，有了 a^1，则有

a^2 = a^1 \times a^1

a^4 = a^2 \times a^2

a^8 = a^4 \times a^4

你看，只需要 3 次平方（倍增），就得到了 a^8，然后我们把二进制数位为 \tt 1 的幂乘起来：

a^8 \times a^2

这里又进行 1 次运算。总共算下来我们只做了 4 次乘法，相较于普通幂的 10 次计算，已经有了很大的优化。并且这个简化是对数级的，总体时间复杂度为 O(\log n)，幂的形式越复杂，指数越大，快速幂的优势就更能体现。

另外提一下模运算的性质：

(a \times b) \bmod p=[(a \bmod p) \times (b \bmod p)] \bmod p

所以：

\begin{align*} a^b \bmod p & = \underbrace{a \times a \times a \times \cdots \times a}_{b \text{ 个 } a} \ \bmod p \\ & = [\underbrace{(a \bmod p) \times (a \bmod p) \times (a \bmod p) \times \cdots \times (a \bmod p)}_{b \text{ 个 } a \bmod p}] \bmod p \end{align*}

也就是说，在乘法取模的过程中，你进行若干次多余的取模运算也无妨，结果都是一致的，好处是可以避免数据溢出。

下面我们将代码运算逻辑应用到上面的例子中，假设此时输入的 a=2，p=9，并设最终结果为变量 ans。从递推的角度出发，显然，最开始有 ans=1。具体实践步骤见下：

第一步：指数 b 的二进制最后一位是 \tt 0（偶数），因此结果 ans 不变，将底数平方并取模（2^2 \bmod 9=4 \to a），指数折半（\lfloor 10 \div 2 \rfloor =5 \to b，等价于将 b 右移一位）。
第二步：现在指数 b（b=5）的二进制表示最后一位是 \tt 1（奇数），对结果 ans 进行如下变换：ans \gets ans \times a \bmod p，即 ans=1 \times 4 \bmod 9=4，将底数平方并取模（4^2 \bmod 9=7 \to a），指数折半（\lfloor 5 \div 2 \rfloor =2 \to b）。
第三步：现在指数 b（b=2）的二进制数码最后一位是 \tt 0（偶数），ans 不动，底数平方并取模（7^2 \bmod 9=4 \to a），指数折半（\lfloor 2 \div 2 \rfloor =1 \to b）。
第四步：现在指数 b（b=1）的二进制表示最后一位是 \tt 1（奇数），结果 ans 为 4 \times 4 \bmod 9=7，底数平方并取模（4^2 \bmod 9=7 \to a），指数折半（\lfloor 1 \div 2 \rfloor =0 \to b）。最后指数变为 0，退出循环。

最终返回 ans=7，便与理论数学计算结果 2^{10}=1024，1024 \bmod 9=7 一致啦～

代码实现

好吧，书归正传，其实我们的正文跟快速幂的数学原理并无直接联系，因为 GCC 内置的 __gnu_cxx::power 函数已经帮我们写好了。为了方便理解，本章节将以题目 P1226 【模板】快速幂为例题，先把完整 AC 代码提供给大家，接着我们再来逐条学习它的用法。

::::success[完整代码]{open}

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using __gnu_cxx::power;
typedef long long ll;
ll p;

// 需要定义一个仿函数类型才能正常使用
struct modmul_op
{
    inline const ll operator()(ll x,ll y) {return x*y%p;}
};

// 你需要对这个函数进行重载以返回单位元
inline ll identity_element(modmul_op) {return 1;}

int main()
{
    ll a,b;
    cin>>a>>b>>p;
    printf("%lld^%lld mod %lld=%lld",a,b,p,power(a,b,modmul_op{}));
    return 0;
}

评测 AC 记录：https://www.luogu.com.cn/record/264484274 ::::

头文件引入

#include <bits/std++.h>
#include <bits/extc++.h>

万能库就不用笔者赘述了。<bits/extc++.h> 是 GNU C++ 内置扩展库头文件，包含 __gnu_cxx 命名空间下所有的非标准扩展功能（比如这里的 __gnu_cxx::power 扩展快速幂函数）。但值得注意的是，这个头文件仅 GCC/G++ 编译器支持（MSVC 等编译器会报错），而标准 C++ 无此类函数。

类型与命名空间

using __gnu_cxx::power;

一定不要忘记此条指令，作用是把 GCC 扩展里 __gnu_cxx 命名空间下的 power 函数引入当前作用域。类似于 using namespace std，这样我们后续便可省略 __gnu_cxx::前缀直接写简化后的 power（其实是懒人专利）。

自定义模乘法仿函数

struct modmul_op
{
    inline const ll operator()(ll x, ll y) {return x*y%p;}
};

这是代码的核心自定义逻辑，需要先理解仿函数（Function Object）的概念：

仿函数是指‌重载了函数调用运算符 operator() 的类或结构体，使用方式和普通函数几乎一致。它使得一个对象能够像普通函数一样传参使用，因此也被称为“函数对象”。仿函数的优势之一是可以进行状态存储和封装状态（比如这里间接访问全局变量 p）。

上面这份代码片段中，我们就创建了一个函数对象，其中 modmul_op 是结构体类型，进行重载运算后，便可作为 GNU power 函数要求的运算载体。

等等，为啥感觉越来越复杂？那是因为 power 是一个通用快速幂模板，它不关心你做的是啥运算，只做一件事：

把一个东西，用二元操作 op 连续合并 n 次。

你给它：

初始元素 a；
运算次数 b；
一个二元运算 op(x,y)；
此运算的单位元 id（下一子目会有详解）。

它就会自动帮你完成：

\underbrace{a\ op\ a\ op\ a\ \dots\ op\ a}_{b\ 次}

换言之，__gnu_cxx::power 是一个通用快速幂的框架，只负责二进制拆分、倍增等代码实现过程，而具体运算法则需要我们自己去定义。当我们自定义模乘规则和单位元（下一子目中会详细讲解）后，它才能成为标准快速幂取模运算的模板函数。

inline const ll operator()(ll x, ll y)：

具体释义如下：

operator()：重载括号运算符，使 modmul_op 的实例可以像函数一样调用（比如 modmul_op()(2,3) 会返回计算结果 2*3%p）。
功能：封装“模乘法”操作——接收两个 64 位整数 x、y，并返回 (x \times y) \bmod p，定义快速幂过程中的乘法取模的核心运算规则。

单位元重载函数

inline ll identity_element(modmul_op) {return 1;}

这是适配 __gnu_cxx::power 函数的关键，需要先理解单位元（幺元）的概念：

单位元：在一个带运算的集合中，如果存在一个元素 e，使得其与集合中的任意元素 w 进行二元运算后，结果仍为 w，则称 e 为该集合关于该二元运算的单位元。

对于普通乘法运算来说，单位元是使得任意实数 w 满足 w \times e = w 的数 e，解方程可得 e=1，故乘法的单位元是 1。

__gnu_cxx::power 是通用型快速幂函数，可以支持任意二元运算的 “快速幂”（比如模乘、普通乘、矩阵乘法、甚至加法）。因此在我们自定义二元运算时，GNU power 函数需要知道当前运算的单位元。

在这里，单位元就相当于是一个初始值。当指数 b=0 时，快速幂的返回结果便是这个原始数值（数学上 a^0=1，对应乘法单位元）。

函数重载规则：identity_element 的参数是 modmul_op 类型（仅用于标识仿函数类型，无实际传参需求），返回数值 1，相当于告诉 power 函数：我定义的是模数乘法，初始值（单位元）为 1。

::::warning[注意] __gnu_cxx::power 函数必须通过该函数获取运算单位元，无此函数则代码无法被成功编译。 ::::

主函数

int main()
{
    ll a,b;
    cin>>a>>b>>p;
    printf("%lld^%lld mod %lld=%lld",a,b,p,power(a,b,modmul_op{}));
    return 0;
}

下面重点介绍一下 power 函数的用法：

power(a,b,modmul_op{})：调用 GNU 扩展的快速幂 power 函数，返回值就是最终运算结果，以下是参数说明：

第一个参数 a：快速幂的底数。
第二个参数 b：快速幂的指数（运算次数）。
第三个参数 modmul_op{}：创建一个 modmul_op 类型的临时对象，这相当于告诉 power 函数内部：“用这个仿函数定义的运算（模乘法）来执行快速幂，而不是普通乘法”。

到这里，我们的代码分析就算告一段落了。笔者承认纯概念确实有点抽象，如果你想要有更深刻的理解，详实的底层逻辑与运行示例展示（以样例输入 2 10 9 为例）可以返回上一章节查阅。

::::info[代码注意事项]{open}

编译器兼容性：代码依赖 GCC 的 __gnu_cxx 扩展，仅能在 GCC/G++ 下运行，MSVC、Clang 等无 GNU 扩展的情况下会报错（但 CCF 的竞赛是可以用嘀啦～）。
数据类型与溢出问题：题目中 a,b < 2^{31}，long long 的范围是 [-2^{63},2^{63}-1]，a \times b 的最大值是 (2^{31}-1) \times (2^{31}-1) ≈ 2^{62}，未超出 long long 范围，因此 a \times b \bmod p 不会溢出；一般情况下，若数据更大，可以改用 __int128（如 return((__int128)x*y)%p;）。
边界情况：题目保证 a+b>0，所以我们无需处理 0^0；若 b=0，power 会返回单位元 1，符合 a^0=1 的数学定义。
用法相关：仿函数 modmul_op 封装了模乘规则，identity_element 提供运算的单位元，是适配通用快速幂 power 函数的两个关键。若没有这两点，power 函数就不知道你究竟要做什么运算，自然也就无法正常使用啦！
时间复杂度：power 函数应用快速幂算法可以将 O(n) 的复杂度降为 O(\log n)。
其他拓展：除了本文主要介绍的模乘型快速幂，__gnu_cxx::power 函数还可以支持任意符合二元运算倍增规则的“快速幂”（其中一个更为典型的例子便是矩阵快速幂），只要你正确定义二元运算规则和单位元，它就可以为你所用，助你荡平四方。 ::::

::::success[power 函数的简便用法] 上文介绍了快速幂函数 power 的通用用法。但其实，power 在某些特定情况下还有一个简化版的使用方法，就是单独计算幂次 a^b，食用方式如下：

int a,b;
cin>>a>>b;
cout<<__gnu_cxx::power(a,b); // 输出 a^b

这样就不用重载仿函数和单位元啦，且复杂度依然是 O(\log n) 的，比 std::pow 函数还要快出一大截子呢！ ::::

如此，我们就巧妙地动用了一点点“黑科技”，运用 GNU 扩展的 __gnu_cxx::power 函数，只需定义数学中的基础运算，便成功避免手写快速幂逻辑与复杂循环。看到这儿是不是感觉小有成就呢？“且将新火试新茶，诗酒趁年华”，如果你真心对此感兴趣的话，那就赶紧去动手试试吧！

后记：数据结构 `__gnu_cxx::rope`

除了前文介绍的 power 函数，GNU 扩展 __gnu_cxx 命名空间内还有许多标准 C++ 所没有的专属黑科技，而且都可以在 NOI Linux 2.0 环境下完成编译。作为文末彩蛋，在这里给大家总结其中一个非常实用的数据结构 rope 的功用。

rope 是基于平衡树实现的块状链表容器，其核心设计目标是解决传统线性容器（如 std::string、std::vector）在处理大规模数据时的性能瓶颈。从底层实现看，rope 会将数据分割为多个固定大小的块（通常为几百字节），每个块独立存储并通过平衡树维护块间的顺序关系。这种设计使得 rope 直接复制的复杂度为 O(1)，随机访问、插入、删除等操作的时间复杂度均为分摊 O(\log n)，远优于 string 等的 O(n) 复杂度。

前置内容

#include <ext/rope>
using namespace __gnu_cxx;

这部分的初始化内容和前面 power 的方法一致，你也可以选择使用 <bits/extc++.h> 这个万能拓展头文件。

基本操作

rope<int> a;：创建一个空 rope。
crope a;：rope<char> a; 的另一种写法。
rope<int> a(n);：创建一个长度为 n 的新 rope。
a.push_back(x)：在容器末尾插入 x，均摊 O(1)。
a.append(x)：等价于 a.push_back(x)。
a[x]：访问下标为 x 的元素，复杂度 O(\log n)。
a.at(x)：访问下标为 x 的元素，自带越界检查。
a.size()：获取当前容器的长度。
a.empty()：判断当前容器是否为空。
a.clear()：清空当前容器。
a.insert(pos,x)：在下标 pos 处插入元素 x，复杂度 O(\log n)。
a.erase(pos,len)：从 pos 位置开始往后删除 len 个元素，复杂度 O(\log n)。
a.substr(pos,len)：返回从 pos 位置连续 len 个长度的新 rope。
a.replace(pos,x)：把 pos 位置的元素替换为 x。
a.copy(pos,len,arr)：把从 pos 位置开始连续 len 个元素的内容复制到 arr。

rope 适合处理大规模序列的区间插入、删除、截取，部分时候甚至可以代替可持久化操作，具体可参见下方例子。

rope<int> a[105];

a[0].push_back(1);
a[0].push_back(2);
a[0].push_back(3);  // a[0]: [1,2,3]

a[1] = a[0];      // 版本 1 = 版本 0，O(1) 复杂度
a[1].insert(1,9);   // 改版本 1 → [1,9,2,3]

a[2] = a[1];      // 版本 2 = 版本 1
a[2].erase(0,1);    // 改版本 2 → [9,2,3]

// 三个版本完全独立
for(auto x:a[0]) cout<<x<<" ";
cout<<endl;
// 输出 1 2 3

for(auto x:a[1]) cout<<x<<" ";
cout<<endl;
// 输出 1 9 2 3

for(auto x:a[2]) cout<<x<<" ";
cout<<endl;
// 输出 9 2 3

介绍完了基本用法，那我们就再来点练习吧。P1383 和 P6166 就是两道不错的题目，大家可以尝试使用 rope 去解决它们。笔者找了几篇较为优秀的题解，可以分别参考这里和这里。

声明：由于作者才疏学浅，本文部分资料来源于网络或 AI，但均已经由本人亲手校对。

完结撒花！创作不易，走前 \color{#0aa}\cancel{\ \ \ \textrm{\textit{\textbf{{\Large\color{#0af}点 }}}}^\textrm{\textit{\textbf{{\small\color{#e99100}个}}}}_\textrm{\textit{\textbf{\large\color{#778891}赞}}}\textrm{\textit{\textbf{\LARGE\color{#9c1}呗}}}\circlearrowleft\ \ }。