快速幂与龟速乘
一、快速幂
1.算法原理
求 \(a^b\bmod p\) 的结果。
我们可以构造如下算法：
\[a^b \bmod p=\begin{cases}(a^{\frac b 2})^2 \bmod p&\texttt{b is even}\\a(a^{\frac{b-1}2})^2 \bmod p&\texttt{b is odd}\end{cases} \]为了更好地理解，我们举个栗子
以\(5^{23}\)为例：（先把取模省略掉）
- \(5^{23} = (5^{11})^2 ×5\)
- \(5^{11} = (5^5)^2 × 5\)
- \(5^5 = 5 ^ 2 × 5\)
- \(5^2 = 5 × 5\)
再将式子从下往上递归即可
2.代码
递归版：
long long ksm(long long a,long long b,long long p){
if(p == 0) return 1;
if(p == 1) return x;
long long t = ksm(x,p/2);
if(p & 1)return (t * t % p) * x % p;
else return t * t % p;
}
循环版（更常用）：
long long ksm(long long a,long long b,long long p){
long long res = 1,tmp = a;
while(b){
if(b&1) res = res * tmp % p;
tmp = tmp * tmp % p;
}
return res;
}
3.时间复杂度：\(O(log_b)\)
很显然每次 \(b\) 会减半
二、龟速乘
求 \(ab\bmod p\) 的结果。
\(a,b,p\) 都是 \(10^{18}\) 级别。
我们可以构造类似的算法（就是把乘法改成加法即可）
code:
long long ksm(long long a,long long b,long long p){
long long res = 0,tmp = a;
while(b){
if(b&1) res = (res + tmp) % p;
tmp = (tmp + tmp) % p;
}
return res;
}
时间复杂度 \(O(\log b)\)。
三、更加快速的乘法
当然还有一种算法：
\[a×b\bmod p = a×b - \lfloor\frac{a×b}p\rfloor × p \]我们不妨令\(x = a × b,y = \lfloor\frac{a×b}p\rfloor × p\)：
\[a×b\bmod p = x - y \]又因为\(x - y = a×b\bmod p< p < 2^{64}\)
\[a×b\bmod p = x - y = (x-y)\bmod 2^{64} \]我们先用longdouble对\(\frac{a×b}p\)进行计算，再下取整由于精度误差算出来的值可能会小1，但是在模\(p\)意义下完全没有影响
我们再使用unsigned long long计算\(x\)和\(y\)(unsigned long long自然溢出即对\(2^{64}\)取模)
最后是代码：
typedef unsigned long long ull;
typedef long long ll;
ull ksm(ull a,ull b,ull p){
//a %= p,b %= p;
ull x = a * b, y = (ull)((long double)a * b / p) * p;
ll res = (ll) (x % p) - (ll)(y % p);
return res + (res < 0 ? p : 0);
}