【原子工具】快速幂 快速乘

题幂算.一切即1
阴阳迭变积微著，叠浪层峦瞬息功
莫道浮生千万事，元知万象一归宗

---

快速幂

原始快速幂（O(logn)）

二分递归形式

#include<bits/stdc++.h>
using namespace std;#define ll long long ll q_pow(ll base,ll exp)
{if(exp == 0) return 1;ll res = q_pow(base,exp/2);if(exp & 1) return res*res*base;return res*res;
}int main()
{ll a,b;cin >> a >> b; cout << q_pow(a,b);
}

非递归形式

#include<bits/stdc++.h>
using namespace std;#define ll long long ll q_pow(ll base,ll exp)
{ll res = 1;while(exp){if(exp & 1){res = res * base; }base = base * base;exp >>= 1;}return res;
}int main()
{ll a,b;cin >> a >> b; cout << q_pow(a,b);
}

模下意义的快速幂（O(logn)）

例题 ： 洛谷P1226

二分递归形式

#include<bits/stdc++.h>
using namespace std;#define ll long long ll q_pow(ll base,ll exp,ll digit)
{if(exp == 0) return 1;base %= digit;ll res = q_pow(base,exp/2,digit);if(exp & 1) return (res*res)%digit*base%digit;return res*res%digit;
}int main()
{ll a,b,c;cin >> a >> b >> c; cout << a << "^" << b << " mod " << c << "=" << q_pow(a,b,c);
}

非递归形式

#include<bits/stdc++.h>
using namespace std;#define ll long longll q_pow(ll base,ll exp,ll digit)//一般来说digit写成mod多一点个人习惯
{base %= digit;ll res = 1;while(exp){if(exp & 1){res = res * base % digit; }base = base % digit * base % digit;exp >>= 1;}return res;
}int main()
{ll a,b,c;cin >> a >> b >> c; cout << a << "^" << b << " mod " << c << "=" << q_pow(a,b,c);
}

快速乘

龟速乘（O(logn)

递归式

#include <bits/stdc++.h>
using namespace std;#define ll long long
const int mod = 500;ll q_mul(ll a, ll b)
{if (b == 0) return 0;ll res = q_mul(a, b / 2);if (b & 1) return (res + res + a) % mod;//龟速乘的目的就是为了处理大数相乘使用使用modreturn (res + res) % mod;
}int main()
{ll a, b;cin >> a >> b;cout << q_mul(a, b);
}

非递归式

#include <bits/stdc++.h>
using namespace std;#define ll long long
const int mod = 500;ll q_mul(ll a, ll b)
{a % mod;ll res = 0;while (b){if (b & 1){res = (res + a) % mod;}a = (a + a) % mod;b >>= 1;}return res;
}int main()
{ll a, b;cin >> a >> b;cout << q_mul(a, b);
}

快速乘（光速乘）（O(1)）

不是特别卡常数不建议使用，可能会有计算错误

#include <bits/stdc++.h>
using namespace std;#define ll long long
#define ld long double
const int mod = 1e5;ll q_mul(ll a, ll b)//非压行版
{ld temp = (ld)a * b / mod;ll q = (ll)temp * mod;return (a * b - q + mod) % mod;
}
ll q_mul(ll a, ll b)
{return (a * b - ((ll)((ld)a * b) / mod)*mod + mod) % mod;
}int main()
{ll a, b;cin >> a >> b;cout << q_mul(a, b);
}

记忆锚点 ：
q = (ld)a * b / mod
(a * b − ( ll)q * mod + mod) % mod

---

文献参考

【OI Wiki - 快速幂】
CSDN -【谈谈知识点】快速幂&龟速乘&快速乘

---

总结

阴阳二进制的火花在递归中迭变，模数宇宙的涟漪于位运算里震荡。代码中的每一个移位都是对混沌的降维打击，递归栈底的return 1如同宇宙大爆炸的奇点，从虚无中诞生万千可能。新手当知：算法修炼是铸剑过程，递归与迭代是阴阳双刃，调试时的报错声恰是淬火的嘶鸣。 无论指数如何膨胀，终将拆解为二进制的星辰；纵使乘数浩如烟海，亦可化作位运算的细沙。记住，你写的不是代码，而是将混沌世界重构成数学之美的炼金术。