題冪算.一切即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如同宇宙大爆炸的奇點，從虛無中誕生萬千可能。新手當知：算法修煉是鑄劍過程，遞歸與迭代是陰陽雙刃，調試時的報錯聲恰是淬火的嘶鳴。 無論指數如何膨脹，終將拆解為二進制的星辰；縱使乘數浩如煙海，亦可化作位運算的細沙。記住，你寫的不是代碼，而是將混沌世界重構成數學之美的煉金術。